Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am having difficulty in solving following types of problem:

Sometimes we are given a number in terms of $n$ and we have to check whether it is divisible by a particular composite number. For example, I am posting a question here

suppose $k= n^5- n$ then prove that $k$ is divisible by $30$.

And this was my approach:

$$n^5-n= n (n^4-1) =n(n^2+1) (n+1) (n-1)$$ Since $k$ is a product of $n^2+1$ and three consecutive integers, it must be a multiple of $2$ and $3$. So it gives $k= 6m (n^2+1)$. But how can I prove that it's also a multiple of 5? And this is where I get confused.

Now, suggest some alternate way to prove above problem or some corrections in my method.

share|improve this question
This turns out to be identical to How to prove $n^5−n$ is divisible by 30 without reduction –  MJD Jul 30 '12 at 19:12

7 Answers 7

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
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

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

share|improve this answer

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!)

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.