Find the remainder when 100^100 is divided by 7
100100(mod7)|100≡2(mod7)≡2100(mod7)|because gcd(2,7)=1 :|2ϕ(7)≡1(mod7)ϕ(7)=6ϕ() is the Euler's totient function|26≡1(mod7)≡2100(mod7)|100=6⋅16+4≡26⋅16+4(mod7)≡(26)16⋅24(mod7)≡116⋅24(mod7)≡24(mod7)≡16(mod7)≡2(mod7)
