Find remainder when 777777 is divided by 16.
777=48×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