# Find remainder when $777^{777}$ is divided by $16$ [duplicate]

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.

• You can't use Fermat here - $16$ is not prime. You have to use Euler's theorem: en.wikipedia.org/wiki/Euler's_theorem Jun 28, 2015 at 13:04
• Oops, you were faster, shall I mark you or delete my answer?: ) Jun 28, 2015 at 13:05
• @Wojowu Oh sorry, yes I was wrong. Please suggest solution for me. Jun 28, 2015 at 13:05
• math.stackexchange.com/questions/623008/… Jun 28, 2015 at 13:06
• @Atvin Feel free to leave it as it stands. Jun 28, 2015 at 13:06

Alternative to other answers: Note that $9^2=81\equiv 1\pmod{16}$, so $777^{777}\equiv 9^{777}=9\cdot(9^2)^{388}\equiv 9\pmod{16}$.

• Nice alternate solution, +1 :) Jun 28, 2015 at 13:11

Since $9$ is coprime to $16$, you know that $$9^{\varphi(16)}\equiv 1\pmod{16}$$ where $\varphi$ is Euler's totient function. Your method is good, but $\phi(16)\ne 16-1$, so you got the answer wrong.

• Yes, I was wrong. Jun 28, 2015 at 13:14

Fermat's theorem will only work with primes.($16$ is not a prime)

But, it can be solved by the general formula, using Euler's theorem.

Since $gcd(9,16)=1, 9^{\phi(16)} \equiv 1 (mod 16)$. Since $16=2^4, \phi(16)=8$.

Therefore, $9^8 \equiv 1 (mod 16)$, and we have $777^{777} \equiv 9^{777} \equiv 9^9 \equiv 9*9^8 \equiv 9 (mod 16)$.

• $777^{777} \equiv 9^{777}$ please explain this step. Jun 28, 2015 at 13:13
• You already did this step in your solution, $777=48$x$16+9$, therefore, it is equivalent with $9$ modulo $16$ Jun 28, 2015 at 13:15
• Ok, I understand Jun 28, 2015 at 13:17
• It doesn't matter, because $777$ and $9$ are in the same equivalent class, they count as the same number, when working modulo $16$, can't explain it any longer :) Jun 28, 2015 at 13:18
• $9^{777}≡9^9$ I am unable to understand. Did you use 777=96x8+9 ? Jun 28, 2015 at 13:28

Hint: $9^2~=~81~=~5\cdot16+1$.