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?
Best Answer
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}$.