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,
How to solve and see resolution of $13^{53} \pmod 7$ using Fermat little Theorem?
2
$\begingroup$
elementary-number-theory
-
3Are you sure it is related somehow to `Mathematica` programming ? Hint : for odd numbers it is always 6. – 2012-09-25
-
0I mean $13^k \mod 7 = 6$ for all odd $k$. – 2012-09-25
-
0Ok, thank you.. But why?.. I mean, which theorem says so..? – 2012-09-25
-
0If this _were_ a Mathematica question the answer should be `Mod[13^53, 7]` – 2012-09-25
-
0$13 \times 6 \mod 7 = 1$ and $13 \times 1 \mod 7 = 6$. You should complete the rest to prove this theorem. – 2012-09-25
-
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. – 2012-09-25
-
0I meant a _multiple_ of 7 in the first line above... – 2012-09-25
1 Answers
7
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}$.
-
0Ohh..., I want to be like you when I grow Up... Thank You! – 2012-09-25
-
1@Leandro: You mean you want to be a mean square with a big bushy beard? :-) – 2012-09-25
-
2@AsafKaragila: only if I haven't trimmed in a long time :-p – 2012-09-25