0
$\begingroup$

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

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

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}

$\endgroup$
  • $\begingroup$ Alright, I was thinking of this, but are negative exponents allow in modular arithmetic? $\endgroup$ – J. Doe Hue Dec 10 '18 at 17:40
  • $\begingroup$ 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? $\endgroup$ – J. Doe Hue Dec 10 '18 at 17:43
  • $\begingroup$ $15^{-1} \bmod{53}$ is well-defined since $\gcd(15, 53) = 1$. $\endgroup$ – Zach Langley Dec 10 '18 at 17:43
  • $\begingroup$ @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). $\endgroup$ – Barry Cipra Dec 10 '18 at 17:44
  • 2
    $\begingroup$ @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$$ $\endgroup$ – Bill Dubuque Dec 10 '18 at 18:05
0
$\begingroup$

$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}$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – J. Doe Hue Dec 10 '18 at 18:36
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Dec 10 '18 at 20:01
  • $\begingroup$ Same answer. Different explanation how to come by it. $\endgroup$ – fleablood Dec 10 '18 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.