+0

# Math Problem

0
152
1

Find the remainder when 100^100 is divided by 7

Guest May 12, 2017
Sort:

#1
+18827
0

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}$$

heureka  May 12, 2017
edited by heureka  May 12, 2017
edited by heureka  May 12, 2017

### 20 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details