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

Question

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..

Answer 1

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$?

Answer 2

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

Answer 3

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} $$

Answer 4

$$\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}$$

Answer 5

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".

Answer 6

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

Answer 7

$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.

Answer 8

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.