+26367 Find the remainder when 100^100 is divided by 7
\(\begin{array}{|rcll|} \hline && 100^{100} \pmod{7} \quad & |\quad \boxed{ 100 \equiv 2 \pmod {7} } \\ &\equiv & 2^{100} \pmod{7} \quad & |\quad \text{because } gcd(2,7) = 1\ : \\ && & |\quad 2^{\phi(7)} \equiv 1 \pmod {7} \quad \phi(7) = 6 \quad \phi() \text{ is the Euler's totient function}\\ && & |\quad \boxed{2^{6} \equiv 1 \pmod {7}} \\ &\equiv &2^{100} \pmod{7} \quad & | \quad 100 = 6\cdot 16 +4 \\ &\equiv &2^{6\cdot 16 +4} \pmod{7} \\ &\equiv & (2^{6} )^{16}\cdot 2^4 \pmod{7} \\ &\equiv & 1^{16}\cdot 2^4 \pmod{7} \\ &\equiv & 2^4 \pmod{7} \\ &\equiv & 16 \pmod{7} \\ &\equiv & 2 \pmod{7} \\ \hline \end{array}\)
