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
-
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}$.
-
2@AsafKaragila: only if I haven't trimmed in a long time :-p – 2012-09-25