3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – latenight_help Apr 4 '14 at 7:55
  • $\begingroup$ @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 $\endgroup$ – wanderer Apr 4 '14 at 13:32
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.