# What is the remainder of $3^{13} \div 25$ by hand using Euler's theorem?

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?

• $\!\!\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\ \$ Nov 20, 2018 at 16:57

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}$$.
• 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} Nov 20, 2018 at 16:07