2.1: Problem 20: Prove that \(n^7 - n\) is divisible by \(42\) for any integer \(n\).

Proof

We want to show that \(n^7 - n\) is divisible by \(42\) for any integer \(n\). This means that we want to show that

$$ \begin{align*} n^7 &\equiv n \pmod{42}. \end{align*} $$

Observe that \(42 = 2 \cdot 3 \cdot 7\) and that \((2,3,7) = 1\). Therefore, by the Chinese Remainder Theorem, it suffices to show that the following congruences hold for all integers \(n\)

$$ \begin{align*} n^7 &\equiv n \pmod{2} \\ n^7 &\equiv n \pmod{3} \\ n^7 &\equiv n \pmod{7} \end{align*} $$

We will start by showing that

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

is true for any integers \(n\). Since we’re working modulo \(2\), then we have two residue classes. If \(n = 0\), then \(n^7 \equiv 0 \pmod{2}\). If \(n = 1\), then \(1^7 \equiv 1 \pmod{2}\). Next, we need to show that

$$ \begin{align*} n^7 \equiv n \pmod{3} \end{align*} $$

We have three residue classes to check. If \(n = 0\) or \(n = 1\), then clearly it is true. When \(n = 2\), then

$$ \begin{align*} 2^7 \equiv 128 \equiv 2 \pmod{3} \end{align*} $$

Finally, we need to show that \(n^7 \equiv n \pmod{7}\). Recall, in Problem 19 we saw that (due to Fermat’s theorem)

$$ \begin{align*} n^6 - 1 &\equiv 0 \pmod{7} \end{align*} $$

Now, observe that

$$ \begin{align*} n^7 - n &\equiv n \cdot (n^6 - 1) \pmod{7} \\ &\equiv n \cdot 0 \pmod{7} \\ &\equiv 0 \pmod{7} \\ \end{align*} $$

Therefore, \(n^7 \equiv n \pmod{7}\) as required. Thus, by CRT,

$$ \begin{align*} n^7 &\equiv n \pmod{42} \end{align*} $$

as we wanted to show. \(\ \blacksquare\)

References