Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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|improve this question
3  
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 Sep 25 '12 at 19:03
1  
@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
show 2 more comments

migrated from mathematica.stackexchange.com Sep 25 '12 at 19:14

1 Answer

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|improve this answer
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
1  
@AsafKaragila: only if I haven't trimmed in a long time :-p – robjohn♦ Sep 25 '12 at 23:11

Your Answer

 
discard

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.