Prove that $24^{31}$ is congruent to $23^{32}$ mod 19.

Question

According to my knowledge, to prove that $24^{31}$ is congruent to $23^{32}$ mod 19, we must show that both numbers are divisible by 19 i.e. their remainders must be equal with mod 19. Please correct me if I'm wrong.

So, I was able to reduce $23^{32}$ and find its mod 19, which is 17 but I am having a bit of problem with $24^{31}$ since 31 is a prime number and I do not know how to break it down. Please help me with that.

Answer 1

After some calculation you have \begin{align*} 24 &\equiv 5 \bmod 19 \\ 24^2 &\equiv 25 \equiv 6 \bmod 19 \\ 24^4 &\equiv 36 \equiv -2 \bmod 19 \\ 24^8 & \equiv 4 \bmod 19 \\ 24^{16} & \equiv 16 \equiv -3 \bmod 19 \end{align*}

Now multiply: $$24^{31} \equiv 5\cdot 6 \cdot (-2) \cdot 4 \cdot -3 \equiv (30) \cdot (24) \equiv 11 \cdot 5 \equiv 55 \equiv 17 \bmod 19$$

Answer 2

With perhaps a little less arithmetic, $2^2=4\equiv23\pmod{19}$, and $4\times5=20\equiv1\pmod{19}$, so $24\equiv5\equiv4^{-1}\equiv2^{-2}\pmod{19}$. By Fermat's little theorem, $$23^{32}=2^{2\times32}=2^{64}\equiv2^{64-7\times18}\equiv2^{-62}\equiv2^{-2\times31}\equiv24^{31}\pmod{19}$$

Answer 3

$ 24 \equiv 5 \bmod 19 $

$ 23 \equiv 4 \bmod 19 $

$ 5 \cdot 4 \equiv 1 \bmod 19 $

$ 5^{-31} 4^{32} \equiv 4^{31} 4^{32} \equiv 4^{63} \equiv 4^9 = 2^{18} \equiv 1 \bmod 19 $