Krdytkyu

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 48equiv 23pmod{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^{13mod{phi(25)}}equiv3^{13mod20}$
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^{26mod20}equiv3^6$ and then $3^6equiv(3^{3})^2equiv27^2equiv2^2equiv4$ 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)}equiv1pmod{n}$ but I'm trying to find a shorter, possibly smarter answer which DOES use Euler's theorem. Any thoughts?

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