Proving congruence $24^{31}\equiv 23^{32}\pmod {19}$

Question

The task is to prove $24^{31}\equiv 23^{32}\pmod {19}$.

I'm trying to use Fermat's little Theorem and so far I only found that $24^{31}\equiv 19\pmod{19}$. Would proving that $17\mid23^{32}$ prove the congruence?

We also know that $24^{18} \equiv 1\pmod {19}$ but I don't think that's any help.

Answer 1

In order to prove $a \equiv b$ mod $c$ we must show that $c|b-a$, i.e., here we need to show that $24^{31}-23^{32}$ is divisible by $19$. Observe that $24^{31}\equiv 17$ mod $19$ and $23^{32}\equiv 17$ mod $19$. Now if $l=aq+r$ and $m=ap+r$ then $l-m=a(q-p)$ which is divisible by $a$.

Answer 2

$$23^{32} = {{23^2}^2}^2 * {{23^2}^2}^2 \pmod {19}$$ $$23^2 = 529 \equiv 16 \pmod {19}$$ $$(16 \pmod {19})^2 \equiv 9 \pmod {19}$$ $$(9 \pmod {19})^2 \equiv 6 \pmod {19}$$ $$6 \pmod {19} * 6 \pmod {19} \equiv 17$$

So $23^{32} \equiv (17 \pmod {19})$

A similar method will deduce that $24^{31}$ is equivalent to $(17 \pmod {19})$

Note: $a \pmod b * a \pmod b = a^2 \pmod b$

Answer 3

As $\displaystyle24\equiv5\pmod{19},23\equiv4$ and $31\equiv13\pmod{\phi(19)}$

the problem immediately reduces to $$5^{13}\equiv4^{14}\pmod{19}$$

Now $\displaystyle4=2^2,4^{14}=2^{28}\equiv2^{10}\pmod{19}$

Again, $\displaystyle2^5=32\equiv-6\pmod{19}\implies2^{10}\equiv(-6)^2\equiv-2\ \ \ \ (1)$

$\displaystyle5^3=125\equiv-8\pmod{19} \implies5^6\equiv(-8)^2\equiv7\implies5^{12}\equiv7^2\equiv-8$

$\displaystyle5^{13}\equiv5\cdot(-8)\pmod{19}\equiv-2\ \ \ \ (2)$

Compare $(1),(2)$

Answer 4

There is usually a way to do this kind of thing with a small amount of calculation - though it may be quite hard to find the "easy" way!

By Fermat we have $2^{18}\equiv1\pmod{19}$; you can also check without too much trouble that $2^9\equiv-1\pmod{19}$; then we have $$24^{31}\equiv24^{13}\equiv8^{13}3^{13}\equiv8^{13}(-16)^{13}\equiv-2^{91}\equiv-2$$ and $$23^{32}\equiv23^{14}\equiv4^{14}\equiv2^{28}\equiv2^{10}\equiv-2\ .$$