Use Fermat's Little Theorem to prove that
$11|(9n^{23}-5n^{13}+7n^3)$
Asked
Active
Viewed 482 times
1
-
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}$ – DewinDell Nov 11 '12 at 13:00
-
3More hint: $n^{23}=n^{20}\cdot n^3=(n^{10})^2\cdot n^3$. – Harald Hanche-Olsen Nov 11 '12 at 13:02
-
2Also 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! – DewinDell Nov 11 '12 at 13:06
2 Answers
11
$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)$.
robjohn
- 345,667
-
2@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$. – hmakholm left over Monica Nov 11 '12 at 13:25
-
1
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}$$
Bill Dubuque
- 272,048