What is the remainder of ${{6457}^{76}}^{57}$ modulo $23$?

Question

What is the remainder when ${{6457}^{76}}^{57}$ is divided by $23$?

---

How to solve it by Euler's theorem or Chinese theorem?

Answer 1

By Euler's Theorem, $\varphi(23)=22$ and applying Fermat's Theorem $1\equiv 6457^{\varphi(23)} \pmod{23}$

$10 \equiv 76 \pmod{\varphi{(23)}}$

$7 \equiv 57 \pmod{\varphi({\varphi{(23)}})}$

$10 \equiv 10^{7} \pmod{\varphi{(23)}}$

So we know that $6457^{76^{57}}\equiv 6457^{10} \pmod{23}$

$17\equiv 6457 \pmod{23}$

Thus $4\equiv 6457^{76^{57}} \pmod{23}\equiv 6457^{10} \pmod{23} \equiv 17^{10} \pmod{23}$

Answer 2

$6457\equiv-6\pmod{23}$

$\implies6457^{76^{57}}\equiv(-6)^{76^{57}}\pmod{23}\equiv6^{76^{57}}$

Now we need $76^{57}\pmod{\phi(23)}$

As $(22,76)=2,$ let us find $76^{57-1}\pmod{22/2}$

Now $76\equiv-1\pmod{11}\implies76^{56}\equiv(-1)^{56}\equiv1$

$76^{57}=76\cdot76^{56}\equiv1\cdot76\pmod{11\cdot76}\equiv76\pmod{22}\equiv10$

$\implies6^{76^{57}}\equiv6^{10}\pmod{23}$

Answer 3

Observe that:

$6457^{{76}^{57}}\bmod{23}=$

$(6457\bmod{23})^{{76}^{57}}\bmod{23}=$

$17^{{76}^{57}}\bmod{23}$

---

Since $\gcd(17,23)=1$, by Euler's theorem, $17^{\phi(23)}\bmod{23}=1$.

Since $23$ is prime, $\phi(23)=23-1=22$.

Therefore $17^{22}\bmod{23}=1$.

---

There exists a positive integer $n$ such that:

$76^{57}=$

$22n+(76^{57}\bmod{22})=$

$22n+((76\bmod{22})^{57}\bmod{22})=$

$22n+(10^{57}\bmod{22})$

---

Therefore:

$17^{76^{57}}\bmod{23}=$

$17^{22n+(10^{57}\bmod{22})}\bmod{23}=$

$17^{22n}\cdot17^{(10^{57}\bmod{22})}\bmod{23}=$

$(17^{22})^{n}\cdot17^{(10^{57}\bmod{22})}\bmod{23}=$

$(\color\red{17^{22}\bmod{23}})^{n}\cdot17^{(10^{57}\bmod{22})}\bmod{23}=$

$\color\red{1}^{n}\cdot17^{(10^{57}\bmod{22})}\bmod{23}=$

$17^{(10^{57}\bmod{22})}\bmod{23}$

---

Let's prove by induction that if $n$ is odd then $10^{n}\bmod{22}=10$:

First, show that this is true for $n=1$:

$10^{1}\bmod{22}=10$

Second, assume that this is true for $n=2k+1$:

$10^{2k+1}\bmod{22}=10$

Third, prove that this is true for $n=2k+3$:

$10^{2k+3}\bmod{22}=$

$10^{2k+2+1}\bmod{22}=$

$10^{2+2k+1}\bmod{22}=$

$10^2(10^{2k+1})\bmod{22}=$

$10^2(\color\red{10^{2k+1}\bmod{22}})\bmod{22}=$

$10^2(\color\red{10})\bmod{22}=$

$1000\bmod{22}=$

$10$

Therefore, since $57$ is odd, $10^{57}\bmod{22}=10$.

---

From all of the above, we can conclude:

$6457^{76^{57}}\bmod{23}=$

$17^{76^{57}}\bmod{23}=$

$17^{(76^{57}\bmod{22})}\bmod{23}=$

$17^{(10^{57}\bmod{22})}\bmod{23}=$

$17^{10}\bmod{23}$

---

So we only need to calculate $17^{10}\bmod{23}$, which is pretty easy:

$17^{2}\bmod{23}=13\implies$

$17^{4}\bmod{23}=13^{2}\bmod{23}=8\implies$

$17^{8}\bmod{23}=8^{2}\bmod{23}=18$

---

Therefore:

$17^{10}\bmod{23}=$

$17^{2+8}\bmod{23}=$

$(17^{2}\cdot17^{8})\bmod{23}=$

$((17^{2}\bmod{23})\cdot(17^{8}\bmod{23}))\bmod{23}=$

$(13\cdot18)\bmod{23}=$

$4$

Answer 4

$\ \ \ ca\bmod cn\,=\, c\,(a\bmod n)\ $ as we explained here, hence

$ 76^{\large 57}\!\bmod 22\, =\, 2\,(38\cdot 76^{\large 56}\bmod 11)\, =\, 2\,(5(-1)^{\large 56}) = 10\ $ so $\ \color{#c00}{76^{\large 57}\! =10\! +\! 22k}$

${\rm mod}\,\ 23\!:\,\ 6457^{\large{ 76^{\Large 57}}}\!\!\! \equiv17^{\large \color{#c00}{76^{\Large 57}}}\!\!\!\equiv17^{\large\color{#c00}{ 10+22k}}\equiv 17^{\large 10}{\underbrace{(17^{\large 22})^{\large k}\equiv 1^{\large k}}_{\rm Fermat}}17^{\large 10}\equiv \color{#0a0}{17^{{\large 10}}}\ $