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$
2
  • $\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, 2018 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, 2018 at 17:45

2 Answers 2

Reset to default
3
$\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$
9
  • $\begingroup$ Alright, I was thinking of this, but are negative exponents allow in modular arithmetic? $\endgroup$
    – J. Doe Hue
    Dec 10, 2018 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, 2018 at 17:43
  • $\begingroup$ $15^{-1} \bmod{53}$ is well-defined since $\gcd(15, 53) = 1$. $\endgroup$
    – Zach Langley
    Dec 10, 2018 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, 2018 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, 2018 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$
3
  • $\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, 2018 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, 2018 at 20:01
  • $\begingroup$ Same answer. Different explanation how to come by it. $\endgroup$
    – fleablood
    Dec 10, 2018 at 20:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .