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

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.

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

• I got to the same answer, however I'm having difficulty proving that $19 \mid a-b$ because they're so large. Any hints? Because $l$ and $m$ in your answer completely omit $b$? – latenight_help Apr 4 '14 at 7:55
• @latenight_help that's what i proved...since given numbers are so big...so all you need to see is that whether they leave same remainder on being divided by $19$...so don't worry about $24^{31}$ etc...just see their remainders – wanderer Apr 4 '14 at 13:32

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

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

• $7^2\equiv 11\pmod{19}$, not $-3$ – ccorn Apr 4 '14 at 6:38
• @ccorn, thanks for the observation. I felt a mistake but could not pinpoint & rectify – lab bhattacharjee Apr 4 '14 at 6:54

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

$24 = 4^{-1} (mod 19)$

$23 = 4 (mod 19)$

$23^{32} 24^{-31} = 4^{32} (4^{-1})^{-31} = 4^{32} 4^{31} = 4^{63} = 2^{126} = 2^{7*18} = (2^{18})^7 = 1^7 = 1 (mod 19)$