1
$\begingroup$

Use Fermat's Little Theorem to prove that

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

  • 0
    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}$2012-11-11
  • 3
    More hint: $n^{23}=n^{20}\cdot n^3=(n^{10})^2\cdot n^3$.2012-11-11
  • 2
    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.2012-11-11
  • 0
    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!2012-11-11

2 Answers 2

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)$.

  • 2
    @lhf: are you talking about $n^{20}\equiv n^{10}\equiv 1\pmod{11}$? I fixed that immediately after posting. :-)2012-11-11
  • 0
    @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$.2012-11-11
  • 0
    ok, sorry for the noise.2012-11-11
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}$$