2.1: Problem 23: Prove that \(n^{13} - n\) is divisible by \(2,3,5,7\) and \(13\) for any integer \(n\).

Proof

We will show that \(n^{13}-n\) is divisible by each of \(2,3,5,7\) and \(13\) for any integer \(n\). First, we will show that \(n^{13} \equiv n \pmod{2}\). Since we’re working module \(2\), then we have two residue classes to check.

  • If \(n = 0\), then \(0^{13} \equiv 0 \pmod{2}\)
  • If \(n = 1\), then \(1^{13} \equiv 1 \pmod{2}\)

From this we see that

$$ \begin{align*} n^{13} \equiv n \pmod{2} \end{align*} $$

Next, Next, we want to show \(n^{13} \equiv n \pmod{3}\). We can use Fermat’s theorem since \(3\) is prime to see that

$$ \begin{align*} n^{2} \equiv 1 \pmod{3} \\ (n^{2})^6 \equiv 1^6 \pmod{3} \\ n^{12} \cdot n \equiv n \pmod{3} \\ n^{13} \equiv n \pmod{3} \end{align*} $$

Therefore, \(n^{13}-n\) is divisible by \(3\). Next, we want to show that \(n^{13} \equiv n \pmod{5}\). To do so, we can also use Fermat’s theorem to see that

$$ \begin{align*} n^{4} &\equiv 1 \pmod{5} \\ (n^{4})^3 &\equiv (1)^3 \pmod{5} \\ n^{12} \cdot n &\equiv 1 \cdot n \pmod{5} \\ n^{13} &\equiv n \pmod{5} \\ \end{align*} $$

Therefore, \(n^{13}-n\) is divisible by \(5\). Next, we want to show that \(n^{13} \equiv n \pmod{7}\). We can use Fermat’s theorem again to see that

$$ \begin{align*} n^{6} &\equiv 1 \pmod{7} \\ (n^{6})^2 &\equiv (1)^2 \pmod{7} \\ n^{12} \cdot n &\equiv 1 \cdot n \pmod{7} \\ n^{13} &\equiv n \pmod{7} \\ \end{align*} $$

Therefore, \(n^{13}-n\) is divisible by \(7\). Finally, we want to show that \(n^{13} \equiv n \pmod{13}\). By Fermat’s theorem

$$ \begin{align*} n^{12} \equiv 1 \pmod{13} \\ n^{13} \equiv n \pmod{13} \end{align*} $$

Therefore, \(n^{13}-n\) is divisible by \(13\). \(\ \blacksquare\)

References