Sunday, May 15, 2016

elementary number theory - Find remainder when $777^{777}$ is divided by $16$


Find remainder when $777^{777}$ is divided by $16$.



$777=48\times 16+9$. Then $777\equiv 9 \pmod{16}$.


Also by Fermat's theorem, $777^{16-1}\equiv 1 \pmod{16}$ i.e $777^{15}\equiv 1 \pmod{16}$.


Also $777=51\times 15+4$. Therefore,



$777^{777}=777^{51\times 15+4}={(777^{15})}^{51}\cdot777^4\equiv 1^{15}\cdot 9^4 \pmod{16}$ leading to $ 81\cdot81 \pmod{16} \equiv 1 \pmod{16}$.


But answer given for this question is $9$. Please suggest.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...