0

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

Key Flex
  • 9,417
  • 7
  • 16
  • 34
J. Doe Hue
  • 23
  • 5

2 Answers2

3

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}

Zach Langley
  • 1,367
  • 12
  • 19
  • 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 I've expanded my answer. – Zach Langley Dec 10 '18 at 17:46
  • Alright, I think I understand now. Thanks. I'll try it out to see how it works. So 15-1 = -7 is like saying 15 inverse = -7 in modulo 53? Is this correct? – J. Doe Hue Dec 10 '18 at 17:51
  • @J.DoeHue Yes, it means that $15 \cdot (-7) \equiv 1 \pmod{53}$; i.e., they are multiplicative inverses. – Zach Langley Dec 10 '18 at 18:01
  • OMG! Thanks a ton. This is what I need to find, but couldn't else where. – J. Doe Hue Dec 10 '18 at 18:05
  • 2
    @J.DoeHue Besides the [extended Euclidean algorithm,](https://math.stackexchange.com/a/163118/242) below are a couple other ways to invert $15$, the first being [Gauss's algorithm](https://math.stackexchange.com/a/174687/242) $$\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
0

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

fleablood
  • 1
  • 5
  • 42
  • 130