# $n^5-n$ is divisible by $10$?

I was trying to prove this, and I realized that this is essentially a statement that $n^5$ has the same last digit as $n$, and to prove this it is sufficient to calculate $n^5$ for $0-9$ and see that the respective last digits match. Another approach I tried is this: I factored $n^5-n$ to $n(n^2+1)(n+1)(n-1)$. If $n$ is even, a factor of $2$ is guaranteed by the factor $n$. If $n$ is odd, the factor of $2$ is guaranteed by $(n^2+1)$. The factor of $5$ is guaranteed if the last digit of $n$ is $1, 4, 5, 6,$ $or$ $9$ by the factors $n(n+1)(n-1)$, so I only have to check for $n$ ending in digits $0, 2, 3, 7,$ $and$ $8$. However, I’m sure that there has to be a much better proof (and without modular arithmetic). Do you guys know one? Thanks!

#### Solutions Collecting From Web of "$n^5-n$ is divisible by $10$?"

Your proof is good enough. There’s a slight improvement, if you want to avoid modular arithmetic / considering cases.

$n^5 – n$ is a multiple of 5
$\Leftrightarrow$ $n^5 + 10 n^4 + 35n^3 + 50 n^2 + 24 n = n^5 -n + 5(2n^4 + 7n^3 + 10n^2 + 5n)$ is a multiple of 5. The latter is just $n(n+1)(n+2)(n+3)(n+4)$, which is the product of 5 consecutive integers, hence is a multiple of 5.

Note: You should generally be able to do the above transformation, and can take the product of any 5 (or k) consecutive integers, if you are looking at a polynomial of degree 5 (or k).

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

$(n-2)(n-1)n(n+1)(n+2)$ is even and divisible by 5, since it is the product of 5 consecutive integers.

$5(n-1)n(n+1)$ is also even and divisible by $5$.

Note: Both expressions are also divisible by $3$, so $n^5-n$ is actually divisible by $30$!

Clearly, $n$ and $n^5$ are of the same parity. Hence, $2 \vert (n^5-n)$.

To check for divisibility by $5$, note that
\begin{align}
n^5 – n & = (n^2+1)n(n+1)(n-1)\\
& = (n^2-4+5)n(n+1)(n-1)\\
& = (n^2-4)n(n+1)(n-1) + 5n(n+1)(n-1)\\
& = (n-2)(n-1)n (n+1)(n+2) + 5n(n+1)(n-1)\\
\end{align}

Clearly, $5 \vert 5n(n+1)(n-1)$. Also, $(n-2)(n-1)n (n+1)(n+2)$ is a product of $5$ consecutive numbers and hence $5$ divides it.

Since $n$ and $n^5$ have the same parity, $f(n):=n^5-n$ is divisible by $2$. It is also divisible by $5$, since $f(0)=0$ and $f(n+1)-f(n)=\dotsc=5 n (n^3 + 2 n^2 + 2 n + 1)$. More generally, for every prime $p$, $f(n):=n^p-n$ is divisible by $p$, this is Fermat’s little theorem. In fact, $f(n+1)-f(n)=\sum_{0<k<p} \binom{p}{k} n^k$ and $p \mid \binom{p}{k}$ for $0 < k < p$.

Key idea $\ \ p\!-\!1\mid n\!-\!1\,\Rightarrow\, p\mid a^n- a.\$ Proof $\$ Clear if $\,p\mid a.\,$ Else write $\, \color{#f0f}n = (p\!-\!1)k + 1.\,$

$\ \color{#0a0}{b\!-\!1\mid b^k\!-\!1}\,$ so $\,b = a^{p-1}\,\Rightarrow\, \color{#c00}{p\mid} \color{#0a0}{a^{p-1}\!-\!1\mid (a^{(p-1)k}\!-\!1)}a = a^\color{#f0f}{\large n}\!-\!a\$ by $\rm\color{#c00}{little\ Fermat}\ \ {\bf QED}$

So $\ p\!-\!1,q\!-\!1\mid n\!-\!1\,\Rightarrow\ p,q\mid a^n\!-a\,\Rightarrow\,pq\mid a^n\!-a,\,$ by $\,{\rm lcm}(p,q) = pq\,$ for $\,p\neq q\,$ primes. Yours is the special case $\ p = 2,\ q = 5,\ n = 5.$

The converse is also true, which yields the following generalization of little Fermat-Euler.

Theorem $\ \$ For naturals $\ m,n > 1$

$$m \mid a^n – a\ \ \ \text{for all }\ a\in\Bbb Z\iff m\ \text{ is squarefree, and prime } p\mid m\,\Rightarrow\, p-1\mid n- 1$$

To check if $n^5-n$ is congruent to $0$ modulo $5$, it suffices to check the five cases $n = 0, \pm 1, \pm 2$. Since the polynomial $n^5-n$ is odd, the sign is not important, and we need check only $0$, $1$, and $2$. The first two cases are trivial, and for the last case we calculate manually $32 – 2$ which is divisible by $5$.

Congruence modulo $3$ or modulo $2$ is similar (only involves the “trivial” cases).

Without modular arithmetic? How about induction?

Base case: it is true for $n = 0$ since $0^5 – 0 = 0$. It is also true for $-1$ and $1$ since $-1^5 + 1 = 0$, and $1^5 – 1 = 0$. And it is true for $-2$ and $2$: $-2^5 + 2 = -30$ and $2^5 – 2 = 30$.

Inductive hypothesis: if it is true for $k$, it can be shown to be true for $k + 1$ or vice versa. We can work it from $k + 1$ to $k$, avoiding any “trap door” steps, so that all derivation works both ways.

$$(k + 1)^5 – (k + 1) = 10q$$

$$k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 – (k + 1) = 10q$$

Rearrange terms, cancel 1 and -1:

$$k^5 – k + 5k^4 + 10k^3 + 10k^2 + 5k = 10q$$

Isolate $k^5 – k$:

$$k^5 – k = 5k^4 + 10k^3 + 10k^2 + 5k + 10q$$

Now we need to show that the right hand side is divisible by ten. We can do this as follows. First, rearrange some terms:

$$k^5 – k = 5k^4 + 10k^2 + 5k + 10k^3 + 10q$$

Now note that $10k^3$ and $10q$ are divisible by 10, the latter having come from our inductive hypothesis. So let us focus on the remaining terms, which comprise this formula:

$$5k^4 + 10k^2 + 5k$$

We can show that this is divisible by 10 by factoring out $5k$:

$$5k(k^2 + 2k + 1)$$

$$5k(k + 1)(k + 1)$$

But $k(k + 1)(k + 1)$ is an even number, which, multiplied by 5 is divisible by 10. To show that $k(k + 1)(k + 1)$ we divide into cases. If we suppose that $k$ is odd, then we have odd x even x even, which is even. If we suppose that $k$ is even, then we have even x odd x odd, which is even again.

So the inductive hypothesis is true. If $(k + 1)^5 – (k + 1)$ is divisible by $10$, then so is $k^5 – k$, and vice versa. By induction from the base case in the positive and negative directions, it is true for all $k \in \mathbb{Z}$.

Modular arithmetic wasn’t used, but one basic argument which was used is linked to modular arithmetic. Namely, the argument that some $N$ {is/isn’t} is divisible by $10$, then $N + 10k (k \in \mathbb{Z})$ likewise {is/isn’t} divisible by $10$. This is equivalent to the modular concept that $N$ is congruent to $N + 10k$ modulo $10$, but without the formal trappings. Furthermore the argument about the evenness of $k(k + 1)(k + 1)$ also relies on congruences in disguise. Division into even/odd cases is nothing more than division into the two symbols of the mod 2 congruence.
We cannot really even discuss divisibility without invoking ties to congruences. Divisibility by 10 means congruence to 0 mod 10.