+0  
 
0
285
1
avatar

Find the remainder when 100^100 is divided by 7

Guest May 12, 2017
 #1
avatar+20573 
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}\)

 

 

laugh

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

12 Online Users

avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.