# How to solve and see resolution of $13^{53} \pmod 7$ using Fermat little Theorem?

How to solve and see resolution of $13^{53} \pmod 7$ using Fermat little Theorem? Using Fermat's Little Theorem, I know it gives me 6 as an answer to this problem..., but why? How is the resolution? Thanks,

-

## migrated from mathematica.stackexchange.comSep 25 '12 at 19:14

This question came from our site for users of Mathematica.

Are you sure it is related somehow to Mathematica programming ? Hint : for odd numbers it is always 6. – Artes Sep 25 '12 at 18:45
I mean $13^k \mod 7 = 6$ for all odd $k$. – Artes Sep 25 '12 at 18:56
Ok, thank you.. But why?.. I mean, which theorem says so..? – Leandro Ariel Altamirano Sep 25 '12 at 18:59
If this were a Mathematica question the answer should be Mod[13^53, 7] – belisarius has settled Sep 25 '12 at 19:03
@LeandroArielAltamirano Write $13^k$ as $(7+6)^k$ and then look at the terms... there's only one term that's not a power of $7$. Now look at that term for odd and even $k$. That should give you a clue... You can further expand that term as $(7-a)^k$ where you'll have to figure out what $a$ is, apply the same logic and you'll see that it boils down to either $-1\, \text{mod}\, 7$ or $1\, \text{mod}\, 7$, depending on whether $k$ is odd or even, giving you $6$ and $1$ respectively. – ℛ.ℳ Sep 25 '12 at 19:05

Fermat's Little Theorem says $x^7\equiv x\pmod{7}$. When $x\not\equiv0\pmod{7}$, we can divide by $x$ to get $$x^6\equiv1\pmod{7}$$ In the case of $13^{53}$, we get that $13^{53}=13^{6\cdot8+5}=\left(13^6\right)^8\cdot13^5\equiv1^8\cdot(-1)^5\equiv-1\pmod{7}$ since $13^6\equiv1\pmod{7}$ and $13\equiv-1\pmod{7}$.

Of course, since $13\equiv-1\pmod{7}$, we get that $13^{53}\equiv(-1)^{53}\equiv-1\pmod{7}$.

In any case, $13^{53}\equiv-1\equiv6\pmod{7}$.

-
Ohh..., I want to be like you when I grow Up... Thank You! – Leandro Ariel Altamirano Sep 25 '12 at 19:58
@Leandro: You mean you want to be a mean square with a big bushy beard? :-) – Asaf Karagila Sep 25 '12 at 23:07
@AsafKaragila: only if I haven't trimmed in a long time :-p – robjohn Sep 25 '12 at 23:11