# I am stuck on Fermat's Little Theorem. I know how to apply it, but does it apply here $15^{48}$ mod $53$.

I can't seem to figure out this problem. I can factor to reduce the number, but this is too time consuming. Isn't FLT suppose to help here?

Can someone provide clarification please?

FLT problem

• Thank you! This is what I needed. I wasn't sure if I should stop or keep going with the repeated square method. – J. Doe Hue Dec 10 '18 at 17:41
• I don't see how your hint helps. Can you explicitly state what you are trying to show please? – J. Doe Hue Dec 10 '18 at 17:45

Since $$15^{48}$$ is nearly $$15^{52}$$, we can write

\begin{align} 15^{48} &\equiv 15^{52} \cdot 15^{-4} &\pmod{53}\\ &= 15^{-4}, &\pmod{53} \end{align} using Fermat's little theorem.

With the extended Euclidean algorithm, one can compute $$15^{-1} = -7$$, and so \begin{align} 15^{-4} &\equiv (-7)^4 &\pmod{53}\\ &\equiv 49^2 &\pmod{53}\\ &\equiv (-4)^2 &\pmod{53}\\ &\equiv 16. &\pmod{53} \end{align}

• Alright, I was thinking of this, but are negative exponents allow in modular arithmetic? – J. Doe Hue Dec 10 '18 at 17:40
• I just tried to solvee the 15^-4 (mod 53) and I get a decimal. I assume that 15^48 is the final answer, right? – J. Doe Hue Dec 10 '18 at 17:43
• $15^{-1} \bmod{53}$ is well-defined since $\gcd(15, 53) = 1$. – Zach Langley Dec 10 '18 at 17:43
• @J.DoeHue, yes, they are, provided the number being negatively exponentiated is relatively prime to the modulus (which is the certainly the case here, in part since $53$ is a prime number). – Barry Cipra Dec 10 '18 at 17:44
• @J.DoeHue Besides the extended Euclidean algorithm, below are a couple other ways to invert $15$, the first being Gauss's algorithm $$\bmod 53\!:\,\ \dfrac{1}{15}\equiv \dfrac{3}{45}\equiv \dfrac{56}{-8}\equiv -7$$ $$\bmod 53\!:\,\ \dfrac{1}{15}\equiv \dfrac{54}{3\cdot 5}\equiv \dfrac{18}5\equiv \dfrac{-35}5\equiv -7$$ – Bill Dubuque Dec 10 '18 at 18:05

$$15^{48}*15^{4} = 15^{52}\equiv 1\pmod {53}$$ by FLT.

As $$53$$ is prime all terms have a multiplicative inverses and $$\mathbb Z/53\mathbb Z$$ is a field. So if we can know what $$15^{-1}\pmod {53}$$ is (i.e. then $$x$$ so that $$15\equiv 1 \pmod{53}$$) is then $$15^{48} \equiv (15^{-1})^4=(15^4)^{-1} \pmod {53}$$.

$$15^4 \equiv 225^2 \equiv 13^2 \equiv 169\equiv 10\pmod {53}$$.

So what is $$10^{-1}\pmod{53}$$ so that $$10^{-1}*10\equiv 1 \pmod{53}$$?

Well. $$53*3= 159$$ so $$10*16 = 159 + 1\equiv 1\pmod{53}$$.

So $$10^{-1}\equiv 16\pmod {53}$$ and $$15^{48} \equiv 16\pmod {53}$$.

And we can verify this as $$16*15^4 \equiv 30^4 =810000\equiv 1 \equiv 15^{52}$$ and as $$\gcd(15, 53)=1$$ then means $$16\equiv 15^{48}\pmod {53}$$.

• Thank you for your answer. This is the solution that I was searching for, I just didn't understand how to put together the concepts. – J. Doe Hue Dec 10 '18 at 18:36
• @J.DoeHue This is the same as Zach's prior answer except for order, i.e. here $(15^4)^{-1}$ vs. $(15^{-1})^4$ there. – Bill Dubuque Dec 10 '18 at 20:01
• Same answer. Different explanation how to come by it. – fleablood Dec 10 '18 at 20:26