# How to prove $n^5 - n$ is divisible by 30 without reduction

How can I prove that prove $n^5 - n$ is divisible by 30?

I took $n^5 - n$ and got $n(n-1)(n+1)(n^2+1)$

Now, $n(n-1)(n+1)$ is divisible by 6.

Next I need to show that $n(n-1)(n+1)(n^2+1)$ is divisible by 5.

My guess is using Fermat little theory but I don't know how..

-
There are 8 more answers at Divisibility of composite numbers –  MJD Jul 30 '12 at 19:13

I'm going to take a leap, and suppose that you are doing exercises from the first section of Ireland and Rosen. In that case, I think that FLT is not the 'anticipated' method of solution.

So let's start from your factorization, $(n-1)n(n+1)(n^2 + 1)$

If $n$ is of the form $5k$, $5k-1$, or $5k+1$, we're done from the first three factors. What if $n$ is of the form $5k \pm 2$?

I claim to you that $n^2 + 1$ is always divisible by $5$ if $n = 5k \pm 2$. Perhaps the easiest way to see this is through strict computation. Or you could note that the constant term is either $5$ or $10$. In any case, I leave that part to you: can you show that $n^2 + 1$ is divisible by $5$ if $n = 5k \pm 2$?

-

By the Fermat little theorem, $n^{5} \equiv n \mod 5$ i.e. $n^{5} - n \equiv 0 \mod 5$.

-

Using combinatorial polynomials: \begin{align} n^5-n &=120\binom{n}{5}+240\binom{n}{4}+150\binom{n}{3}+30\binom{n}{2}\\ &=30\left(4\binom{n}{5}+8\binom{n}{4}+5\binom{n}{3}+\binom{n}{2}\right) \end{align} Note: The combinatorial polynomial expansion for a known polynomial, $P(n)$, is not as hard as it might seem. The coefficient, $a_0$, of $\binom{n}{0}$ is simply $P(0)$. If the coefficients, $a_j$, for $\binom{n}{j}$ are known for $j<k$, then the coefficient for $\binom{n}{k}$ is $$P(k)-\sum_{j=0}^{k-1}a_j\binom{k}{j}$$

-
a nice alternative. Is there some reason to believe this method will generally drop out the highest integer factor? –  Ronald Apr 15 '12 at 22:32
@Ronald: Yes. A polynomial maps $\mathbb{Z}$ to $\mathbb{Z}$ if and only if it is an integral linear combination of combinatorial polynomials. This is proven on the page cited in the answer. –  robjohn Apr 15 '12 at 22:36
not sure if I understand why integral linear combination is relevant to the factor 30 becoming apparent? surely the original polynomial is an integral linear combination of elementary polynomials, but the 30 is not apparent. –  Ronald Apr 15 '12 at 22:49
@Ronald: if $30$ is a factor of $P(n)$ for every $n\in\mathbb{Z}$, then consider $Q(n)=\frac{1}{30}P(n)$. $Q(n)$ is a polynomial that maps $\mathbb{Z}$ to $\mathbb{Z}$, so it is an integral linear combination of combinatorial polynomials. Thus, $P(n)=30Q(n)$ will be an integral linear combination of combinatorial polynomials in which all of the coefficients are multiples of $30$. In other words, taking the GCD of the coefficients of $P(n)$ written as a linear combination of combinatorial polynomials yields the GCD of of $P(\mathbb{Z})$. –  robjohn Apr 15 '12 at 23:43

$$\phi(2), \phi(3), \phi(5) \ | \ 4 \quad \stackrel{\textrm{Euler}}{\Longrightarrow} \quad n^5 \equiv n^{5-4} \mod{2,3,5} \quad \stackrel{\textrm{C.R.T.}}{\Longrightarrow} \quad n^5 - n \equiv 0 \mod{30}$$

-

Hint $\rm\ mod\ 5\!:\ n \not\equiv 0\ \Rightarrow\ n\equiv \pm1,\pm2\ \Rightarrow\ n^2\equiv \pm1\ \Rightarrow\ n^4\equiv 1\ \Rightarrow\ n^5\equiv n$

This is a special case of the following global-form of Fermat's little theorem.$\:$ For naturals $\rm\: a,k,n$

$\$ if $\rm\ a,k > 1\$ then $\rm\ a\ |\ n^k\! -\! n\$ for all $\rm\:n \iff a\:$ is squarefree, and $\rm\ p\!-\!1\: |\: k\!-\!1\ \ \:\forall$ primes $\rm\:p\:|\:a$

Hence for $\rm\: a = 30\: = 2\cdot 3\cdot 5\$ we deduce: $\rm\ \ 30\ |\ n^k-n\$ for all $\rm\:n\ \iff\ 4\ |\ k-1$

For the simple proof and further discussion see my 2009/04/10 sci.math post - which also presents the analogous generalization of Euler's $\phi$ function, and Korselt's criterion for Carmichael numbers.

Note: to fix rotted Google Groups links in the cited sci.math post it may be necessary to change $\$ http://google.com/... $\$ to$\$ http://groups.google.com/... i.e. insert "groups." before "google.com".

-

By Fermat little theorem $n^5\equiv n\ \pmod{5}$.

-

$n^5-n=(n-1)n(n+1)(n^2+1)$. Rewrite $n^2+1$ as $5(n-1)+(n^2-5n+6)$ to obtain $n^5-n=5(n-1)^2n(n+1)+(n-3)(n-2)(n-1)n(n+1)$ and use the fact that $n!$ divides the product of n consecutive numbers.

-

a) $\small n^5-n = n \cdot(n^4-1)$ and $\small (n^4-1)$ is divisible by 5 by little fermat.
b) $\small n^5-n = n \cdot(n^2-1)(n^2+1)$
$\small \qquad \qquad =n \cdot (n-1)(n+1)(n^2+1)$
$\small \qquad \qquad = (n-1)n(n+1) \cdot (n^2+1)$
$\qquad$ and $\small (n-1)n(n+1)$ is divisble by 6 (because by 2 and by 3)

Combine a) AND b) to see that $\small n^5-n$ is divisble by 5 AND 6 so also by 30.

-

Write as $n(n^2+1)(n^2-1)$ and note that the squares modulo $5$ are $\pm 1, 0$. Little Fermat does the trick immediately, but sometimes squares are useful.

-