3
$\begingroup$

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.

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

4 Answers 4

5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Nice alternate solution, +1 :) $\endgroup$
    – Atvin
    Jun 28, 2015 at 13:11
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, I was wrong. $\endgroup$
    – math131
    Jun 28, 2015 at 13:14
1
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ $777^{777} \equiv 9^{777}$ please explain this step. $\endgroup$
    – math131
    Jun 28, 2015 at 13:13
  • $\begingroup$ You already did this step in your solution, $777=48$x$16+9$, therefore, it is equivalent with $9$ modulo $16$ $\endgroup$
    – Atvin
    Jun 28, 2015 at 13:15
  • $\begingroup$ Ok, I understand $\endgroup$
    – math131
    Jun 28, 2015 at 13:17
  • $\begingroup$ 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 :) $\endgroup$
    – Atvin
    Jun 28, 2015 at 13:18
  • $\begingroup$ $9^{777}≡9^9$ I am unable to understand. Did you use 777=96x8+9 ? $\endgroup$
    – math131
    Jun 28, 2015 at 13:28
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .