# Proof using Fermat's Little Theorem

Use Fermat's Little Theorem to prove that

$11|(9n^{23}-5n^{13}+7n^3)$

-
What have you tried so far? –  Harald Hanche-Olsen Nov 11 '12 at 12:58
we know that $n^{10} = 1 mod 11$ and now I'm trying to get what is $n^{23}$ and the other powers congruent to from $n^{10}$ –  MinaHany Nov 11 '12 at 13:00
More hint: $n^{23}=n^{20}\cdot n^3=(n^{10})^2\cdot n^3$. –  Harald Hanche-Olsen Nov 11 '12 at 13:02
Also notice $n^{10}$ is congruent to $1$ mod $11$ iff $11$ does not divide $n$. But if $11$ divides $n$ then the problem is even easier. –  Seth Nov 11 '12 at 13:02
Ahh yes, I don't know how I didn't see it. $9n^{23}$ is congruent to $9n^3$ and so on for all the others. Thanks Harald! –  MinaHany Nov 11 '12 at 13:06

$n^{23}\equiv n^{13}\equiv n^3\pmod{11}$ so we get that $$9n^{23}-5n^{13}+7n^3\equiv11n^3\equiv0\pmod{11}$$ Thus, $11|(9n^{23}-5n^{13}+7n^3)$.
@lhf: are you talking about $n^{20}\equiv n^{10}\equiv 1\pmod{11}$? I fixed that immediately after posting. :-) –  robjohn Nov 11 '12 at 13:24
@lhf: Even for $n\equiv0$, Fermat's little theorem still gives $n^{23} = (n^{11})^2\cdot n \equiv n^2\cdot n = n^3$. –  Henning Makholm Nov 11 '12 at 13:25
If modular arithmetic is unfamiliar then one may use that $\rm\:11\mid \color{#C00}{n-n^{11}}\:$ by little Fermat, hence
$$\rm 11\mid7n^3\! - 5n^{13}\! + 9 n^{23}\, =\ (7n^2\! + 2n^{12}) (\color{#C00}{n-n^{11}}) + 11 n^{23}$$