Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,

share|cite|improve this question

migrated from Sep 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] – Dr. belisarius 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
up vote 7 down vote accepted

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

share|cite|improve this answer
Ohh..., I want to be like you when I grow Up... Thank You! – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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