# 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
Note: some answers below were merged from a later question – Bill Dubuque Oct 31 '15 at 1:31

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

-

n^5 -n = n^5 + 6n -n = n(n^(4) - 1) + 6n =n(n+1)(n^2 + 1)(n-1) + 6n 6(n^2 +1) m + 6n 6[{n^2+1+n}]

by fermat 's theorem** n^5 is congruent to n modulo 5 5|n^5 -n hence, 30|n^5-n

-
Please use MathJax formatting on this site. This question already has a large number of very good answers, do you really think it needs another one, especially if it is poorly formatted and does not have much detail? – 6005 Oct 29 '15 at 17:33

Funny brute force approach. Just show:

$$n^5-n = 5!\binom{n+2}{5} + 5\cdot 3!\binom{n+1}{3}=120\binom{n+2}{5}+30\binom{n+1}{3}$$

In general, if $d$ is odd, then you can write:

$$n^d-n = \sum_{i=0}^{\lfloor d/2\rfloor} a_i \binom{n+i}{2i+1}$$

where the $a_i$ are multiples of $(2i+1)!$.

Since the left side is divisible by $(n+1)n(n-1)$, we have that $a_0=0$. We also have $a_{\lfloor d/2\rfloor}=1$. So we have $\lfloor d/2\rfloor-1$ different $a_i$ to determine.

But you can actually determine them by induction, since $\binom{n+i}{2i+1}=0$ when $2i+1>n$. So choose $n=2$ and we get $2^{d}-2 = a_1\binom{3}{3}$ so $a_1=(2^{d}-2)$.

Then take $n=3$, and we get:

$$3^d-3 = a_2\binom{3+2}{5} + a_1\binom{3+1}{3}=a_2 + 4(2^d-2)$$

So $a_2 = 3^d-3 - 4(2^d-2)$.

In general, for $a_k$, we take $n=k+1$ and:

$$a_k = (k+1)^d - (k+1) - \sum_{i=0}^{k-1} a_i\binom{k+1+i}{2i+1}$$

By induction, you can prove that if $D\mid n^d-n$ for all integers $n$, then $D$ must divide $a_i$ for all $i$. And obviously, any factor of all $a_i$ is a common factor of $n^d-n$ for all $n$. So the general solution is the greatest common divisor of $a_1,\dots,a_{\lfloor d/2\rfloor}$. You can do this sequentially, so you compute $3^d-3$ modulo $2^d-2$, and then compute the GCD, etc.

For example, for $d=7$, $2^7-2=126$. Next compute $3^7-3\bmod {126}=42$. Since $42\mid 126$, we get $\gcd(2^7-2,3^7-3)=42$. Then compute $4^7-4$. This is actually obviously divisible by $2(2^6-1)=a_1$. So we get:

$$\gcd(2^7-2,3^7-3,4^7-4)=42$$

This actually works with any odd integer polynomial $g(n)$ of degree $d$ - the greatest common factor of the values of $g(n)$ is:

$$\gcd(g(1),g(2),\dots,g(\lceil d/2\rceil))$$

Now, if $a^d\equiv a\pmod D$ and $b^d\equiv b\pmod D$ then $(ab)^d \equiv ab\pmod{D}$. So $g(n)=n^d-n$ has the particular property that if $D\mid g(a)$ and $D\mid g(b)$ then $d\mid g(ab)$. So you only have to compute the cases in the set where $n$ is prime. So, for example, when $d=19$, you get:

$$\gcd(2^{19}-2,3^{19}-3,5^{19}-5,7^{19}-7)$$

This has all eschewed using Fermat, only using some divisibility theorems and knowledge about binomials and congruences.Indeed, the above argument

But with Fermat's little theorem, we can get much further.

It's pretty obvious that $D$ has to be square-free, because for any prime $p$, $p^d-p$ has only one factor of $p$.

Also, if $n^d-n$ is divisible by $p$ for all $n$ then for any if $g$ is a generator modulo $p$, then $g^d\equiv g\pmod p$ means that $p-1$ divides $d-1$. And visa versa, if $p-1\mid d-1$, then $p$ is a common factor.

So what this really means is that the greatest common factor of $n^d-n$ with $d$ odd is exactly the product of the primes $p$ such that $p-1\mid d-1$.

The same argument works for $d$ even, so that the common factor of $n^d-n$ when $d$ is even is always just $2$, since for any odd prime $p$, $p-1$ is not a factor of the odd $d-1$.

-

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.

-

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.

-
Note that $n^4-1$ is not always divisible by $5$. – Thomas Andrews Oct 14 '15 at 17:22

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

-

For divisibility by $5$, you can use Fermat's little theorem which states that $n^p\equiv n\pmod p$ where $p$ is a prime $\implies n^5-n\equiv 0\pmod 5$.

-

$$\rm\begin{eqnarray} n(n^4\!-\!1)/30\: &=&\ \ \rm n\, (n^2\!-\!1)\,(\color{#C00}{n^2\!+\!1})/30\!\!\!\!\!\! & & \\ &=&\ \ \rm n\,(n\!+\!1)\,(n\!-\!1)\,(\color{#C00}5 &\!\color{#C00} + &\rm\color{#C00}{\, (n\!+\!2)\,(n\!-\!2)})/30 \\ &=&\ \ \rm (n\!+\!1)\,n\,(n\!-\!1)/6 &\! + &\rm \, \color{#C00}{(n\!+\!2)}\,(n\!+\!1)\,n\,(n\!-\!1)\,\color{#C00}{(n\!-\!2)}/30 \\ &=&\rm\qquad\qquad\ {n\!+\!1\ \!\choose 3}\ &\! + &\ \rm 4\,{n\!+\!2\ \! \choose 5} \in\, \Bbb Z \end{eqnarray}$$

-

It suffices to show that $k^5-k$ is always divisible by each of 2, 3, and 5. That is, we want $k^5-k\equiv 0 \mod d$ where $d$ is each of 2, 3, and 5.

We know that $k\equiv r\pmod 2$ where $r$ is 0 or 1. Then $k^5 - k \equiv r^5-r \equiv 0 \pmod2$. The last equivalence follows instantly from a consideration of the two cases: either $r=0$ in which case we have $0^5-0\equiv 0\pmod 2$, or $r=1$ in which case we have $1^5-1\equiv 0\pmod 2$.

Similarly $k\equiv r\pmod 3$ where $r$ is one of 0, 1 or 2. In each case consider $r^5-r\pmod 3$. The first two cases are completely trivial, and the same as in the previous paragraph. The $r=2$ case gives $32-2= 30\equiv 0\pmod 3$.

And again $k\equiv r\pmod 5$ where $r$ is one of $\{0,1,2,3,4\}$; now consider $r^r-r\pmod 5$. Again cases 0 and 1 are trivial; the other three give $30\equiv 0\pmod 5$, $3^5-3 = 243-3 = 240\equiv 0\pmod 5$, and $4^5-4 = 1024-4 = 1020 \equiv 0\pmod 5$, so we are done.

-

Note that $n^2+1$ is divisible by $5$ iff $n^2-4$ is divisible by $5$. But $n^2-4=(n-2)(n+2)$.

So $(n^2+1)(n-1)(n)(n+1)$ is divisible by $5$ iff $(n-2)(n-1)(n)(n+1)(n+2)$ is divisible by $5$. But this is the product of $5$ consecutive integers. End of proof.

Remark: There are more general ways of attacking the problem. But the one used above continues the pattern that you used for $2$ and $3$. Continuing in this way quickly becomes too complicated for practical use, and one ends up turning to Fermat's Theorem, and Euler's Theorem.

-
That was a great idea. Now i know how to deal with (n^2 + arbit ) type numbers while dealing with divisibility . Thanks :) – Simar Jul 24 '13 at 18:02

Let $f(n)=n^p-n$

Clearly, f(1) =1-1=0 is divisible by p.

Now, $f(n+1)-f(n)=((n+1)^p-(n+1))-(n^p-n)= \sum _{1≤r≤p-1} pC_rn^r$.

But prime p| $pC_r$ for 1≤r≤p-1.

So, the difference is divisible by p.

So, using mathematical induction, we can say p|($n^p-n$)

This comes from Fermat's Little theorem.

So, $n^5-n$ is divisible by 5.

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

Now, $n^3-n$ is divisible by 3, so is $n^5-n$.

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

Now, $n^2-n$ is divisible by 2, so is $n^5-n$.

So, $n^5-n$ is divisible by 2,3,5 so, it is divisible by lcm(2,3,5)=30

-

According to link#1, the product of 5 consecutive integers divisible by 5! and the product of 3 consecutive integers divisible by 3!.

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

$n^5-n= n^5-5n^3+4n + 5(n^3-n)$

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

So, the first part is divisible by 5! and the 2nd part is by 5(3!)

-

You are almost done: If $n \equiv 0, \pm 1 \pmod 5$ we are done (as we have $5 \mid n$, $5 \mid n-1$ or $5 \mid n+1$ then). So suppose $n \equiv \pm 2 \pmod 5$, but then $n^2 + 1 \equiv (\pm 2)^2 + 1 \equiv 0 \pmod 5$, hence $5 \mid n^2 + 1$, and so $5 \mid n^5 -n$ also in this case.

-

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

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

-

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

-

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

-

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

-

## protected by 6005Oct 29 '15 at 17:37

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.