Use Fermat's Little Theorem to prove $24^{31} \equiv 23^{32} \mod{19}$

Question

I'm trying to prove $24^{31} \equiv_{19} 23^{32}$.

All I have so far is that this is equivalent to $23^5 \equiv_{19} 24^6$ by multiplying both sides by $24^623^5$. I can see that there seems to be some trick about the fact that the bases and the exponents are each off from the other by 1, but I'm not seeing how to exploit that since I still don't want to have to compute $(23+1)^6$ in pretty much any way.

I searched around for any extra information and I saw one person on YouTube use a principle that you can divide an exponent's base by the module and take the remainder. So for instance, if I'm understanding the principle, it would say that since 24's remainder on division by 19 is 5, and 23's remainder after division by 19 is 4, then this problem reduces to $5^6 \equiv_{19} 4^5$. But I've never seen this principle until watching that YouTube video, so is this legit?

Answer 1

Your principle is legit. In general, if $a_1\equiv b_1\text{ mod } p$ and $a_2\equiv b_2\text{ mod }p$, then $a_1a_2\equiv b_1b_2\text{ mod }p$. One way to see this is to write $b_1 = a_1+m_1p$ and $b_2 = a_2+m_2p$ (with $m_1,m_2\in\mathbb{Z}$), and note that $$ b_1b_2 = (a_1+m_1p)(a_2+m_2p) = a_1a_2 + p(m_1a_2+m_2a_1) + p^2(m_1m_2). $$ Note that the last two terms vanish mod $p$.

Answer 2

Fermat's little theorem gives $a^{p-1}\equiv 1\pmod{p}$ provided that $p\nmid a$, hence: $$ 23^{32}\equiv 4^{32-18} \equiv 4^{14} \equiv 2^{28} \equiv 2^{10} \equiv 1024 \equiv 17\pmod{19} $$ as well as: $$ 24^{31} \equiv 5^{31-18} \equiv 5^{13} \equiv 5\cdot 25^6 \equiv 5\cdot 6^6\equiv 5\cdot 36^3\equiv 5\cdot(-2)^3\equiv -40\equiv 17\pmod{19}.$$

Answer 3

As $24\equiv 5$ and $23\equiv 4\mod 19$, this amounts to proving $$5^{31}\equiv 4^{32}\mod 19.$$

Furthermore, $5$ and $4$ are inverse to each other modulo 19, so multiplying both sides bt $4^{31}$, it is equivalent to $$4^{63}=2^{126}=(2^{18})^7\equiv 1\mod 19,$$ which is true by Little Fermat.

Answer 4

Using equivalences mod $19$ for $24$ and $23$ and mod $\phi(19)=18$ for $31$ and $32$, we have

$$\begin{align} 24^{31}\equiv23^{32}\pmod{19}&\iff5^{-5}\equiv(-15)^{-4}\pmod{19}\\ &\iff3^4\equiv5\pmod{19}\\ &\iff81-5\equiv0\pmod{19}\\ &\iff19\mid76 \end{align}$$