# Divisibility of composite numbers

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.

-
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

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.

-

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

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

-

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

-

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

-

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.

-

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

-