Proving $5 \mid (n^5-n)$ for all $n \in \mathbb{Z}^+$

Question

Prove for all $n \in \mathbb{Z}^+$ that $5 \mid (n^5-n)$

My proof

Basis step: Since $5 \mid (1^5-1) \iff 5 \mid 0$ and $5 \mid 0$ is true, the statement is true for $n=1$.

Inductive step: Assume the statement is true for $n = k$; that is, assume that $5 \mid (k^5-k)$ is true. Then there is $m \in \mathbb{Z}^+$ such that $$k^5 - k = 5m.$$ We must show that this statement is true for $n = k+1$, i.e. show that there is $\ell \in \mathbb{Z}^+$ such that $$(k+1)^5 - (k+1) = 5\ell.$$ Note that $(k+1)^5 - (k+1)$ expands as $k^5 + 5k^4 + 10k^3 + 10k^2 + 4k$.

We can try to find a polynomial $P(x)$ such that $$(k^5-5) + P(x) =(k+1)^5 - (k+1) = k^5 + 5k^4 + 10k^3 + 10k^2 + 4k$$ so as to try to add $P(x)$ to both sides of the assumption. We find that $$\begin{align}P(x) &= k^5 + 5k^4 + 10k^3 + 10k^2 + 4k - (k^5-5) \\ &=5k^4 + 10k^3 + 10k^2 + 5k \end{align}$$ and we can also observe that since $k\in\mathbb{Z}^+$, we have that $\frac{1}{5}P(x) = k^4 + 2k^3 + 2k^2 + k$ is a positive integer. Thus we add this to both sides of our assumption $$ \begin{align} k^5 - k &= 5m \\ (k^2 - k) + P(x) &= 5m + P(x) \\ (k+1)^5 - (k+1) &= 5\left(m + \tfrac{1}{5}P(x)\right) \end{align}.$$ Since $\frac{1}{5}P(x),m \in \mathbb{Z}^+$, it follows that $m + \tfrac{1}{5}P(x) \in \mathbb{Z}^+$. Thus $5 \left| \big[ (k+1)^5 - (k+1) \big] \right.$

By PMI, $5 \mid (n^5-n)$ for all $n \in \mathbb{Z}^+$.

My questions

1. Is this proof valid?
2. What other ways can this be proved by induction? The polynomial expansions took a while to deal with, so I was wondering if there are any alternate methods. (Just FYI, I only have college first-year-level knowledge)

Answer 1

You were close to a shorter proof after you expanded $(k+5)^5-(k+1)$, since \begin{align*} (k+5)^5 - (k+1) &= k^5 + 5k^4 + 10k^3 + 10k^2 + 4k \\ &= (k^5-k) + (5k^4 + 10k^3 + 10k^2 + 5k), \end{align*} and by induction hypothesis, $5$ divides $k^5-k$ and clearly $5$ divides each term in $5k^4 + 10k^3 + 10k^2 + 5k$, so $5$ divides $(k+5)^5 - (k+1)$. The moral of the story is that sometimes it's a good idea not to cancel things out, but to try to find a way to shift them around.

---

Edit: I see this is effectively what you ended up with anyway, but finding ways to shorten proofs and make them clearer is a good thing to strive for.

Answer 2

In $\mathbb{Z}_5$ the integers mod $5$, which is a field, all elements obey $x^5=x$, or $0= x^5 -x$, from which the statement follows right away.

Answer 3

An alternative proof:

Note that we can write $n^{5} - n$ as follows:

$$n^{5} - n = 5\left[6{n\choose 2} + 30{n\choose 3} + 48{n\choose 4} + 24{n\choose 5}\right].$$

This is very clearly a multiple of $5$ (the expression is $5$ times another integer), so we are done.

Here, ${n\choose k} = {\frac{n!}{k! (n-k)!}}$

Answer 4

Here is another way. For every $n \in \mathbb{Z}^{+}$, we have (here we use $a^2 -b^2 = (a-b)(a+b)$) \begin{align} n^5 - n = n(n^4 -1) & = n(n^2-1)(n^2+1) \\ &= n(n-1)(n+1)(n^2 -4 +5) \\ & = n(n-1)(n+1)(n^2 -4) + 5n(n-1)(n+1) \\ & = n(n-1)(n+1)(n-2)(n+2) + 5n(n-1)(n+1) \\ & = (n-2)(n-1)n(n+1)(n+2) + 5n(n-1)(n+1). \end{align} In the last line, the first term is a product of 5 consecutive integers, so it must be divisible by $5$. Moreover, clearly $5$ divides the second one :)

Answer 5

$n^5 - n = n(n^4 - 1) = n(n^2 - 1)(n^2 + 1) = n(n - 1)(n+1)(n^2 + 1)$.

There is a unique $q, r$ so that $n = 5q + r; 0\le r < 5$. This is basically dividing $n$ by $5$ and finding the remainder.

If $r = 0$ then $n = 5q$ and $n^5 - n = 5q(n-1)(n+1)(n^2 + 1)$ and we are done.

If $r = 1$ then $n = 5q +1$ and $n-1 = 5q$ and $n^5 -n = n(5q)(n+1)(n^2 + 1)$ and we are done.

If $r = 2$ then $n = 5q + 2$ and $n^2 + 1 = (5q+2)^2 + 1 = 25q^2 + 20q + 4 + 1 = 5(5q^2 + rq + 1)$ and $n^5 -n = n(n-1)(n+1)5(q^2 + 4q + 1)$ and we are done.

If $r = 3$ then $n = 5q + 3$ and $n^2 + 1 = (25q^2 + 30q + 9) + 1 = 5(q^2 + 6q + 2)$ and $n^5 -n = n(n-1)(n+1)5(q^2 + 6q + 2)$ and we are done.

If $r = 4$ then $n = 5q + 5$ and $n + 1 = 5q +5=5(q+1)$ and $n^5 - n = n(n-1)5(q+1)(n^2 + 1)$ and we are done.

Those are the only $5$ options.