1
$\begingroup$

Well, I know how to solve this problem by using some basic stuff:

$3^3 \equiv 2 \rightarrow 3^{12} \equiv 2^4 \rightarrow 3^{13} \equiv 48\equiv 23\pmod{25}$

But what I'm trying to do is to solve this ONLY using Euler's theorem. What I tried was (all congruences are in mod 25):

$\phi(25)=20, \space \rightarrow 3^{13}\equiv3^{13\mod{\phi(25)}}\equiv3^{13\mod20}$ which still gives me $3^{13}$ and there's no way I could calculate that. So I tried to raise both sides of the starting equation to the power of two so I get something easier to calculate:

$3^{26}\equiv x^2 \equiv 3^{26\mod20}\equiv3^6$ and then $3^6\equiv(3^{3})^2\equiv27^2\equiv2^2\equiv4$ therefore $x^2=4 \rightarrow x=2,-2$, hence $3^{13} \equiv 2$ or $3^{13}\equiv23$ (And we know that the correct answer is 23)

We can verify which one of $2$ and $23$ is the correct answer using Euler's theorem $a^{\phi(n)}\equiv1\pmod{n}$ but I'm trying to find a shorter, possibly smarter answer which DOES use Euler's theorem. Any thoughts?

$\endgroup$
1
  • $\begingroup$ $\!\!\bmod 25\!:\ 3^{\large 20}\equiv 1\,\Rightarrow\,3^{\large 10}\equiv \pm1,\,$ must be $-1$ to be correct $\!\bmod 5.\ $ Equivalently, check your $2$ cases $\!\bmod 5\ \ $ $\endgroup$ Nov 20, 2018 at 16:57

1 Answer 1

1
$\begingroup$

You've already used Euler's theorem to show that $3^{13}\equiv2\pmod{25}$ or $3^{13}\equiv23\pmod{25}$, as $$(3^{13})^2\equiv3^{26}\equiv3^{26\mod{\phi(25)}}\equiv3^{26\mod{20}}\equiv3^6\equiv4\pmod{25}.$$ You can use Euler's theorem mod $5$ to finish the proof; you know that $$3^{13}\equiv3^{13\mod{\phi(5)}}\equiv3^{13\mod{4}}\equiv3^1\pmod{5},$$ and hence $3^{13}\equiv23\pmod{25}$.

$\endgroup$
2
  • 1
    $\begingroup$ I don't understand the second part, $3^{13}\equiv23\pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23} $\endgroup$ Nov 20, 2018 at 16:07
  • $\begingroup$ I was assuming the work you showed in your question already; let me expand my answer to clarify this. $\endgroup$
    – Servaes
    Nov 20, 2018 at 16:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .