Divisibility of composite numbers

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

let, $f(k) = k^5 - k$ where k is a natural number

we need to show that $f(k)$ is divisible by $30$

take the case when $k = 1$

$f(1) = 0$ which is divisible by $30$

take the case when $k = 2$

$f(2) = 2^5 - 2$

i.e. $f(2) = (2)(2^4 - 1)$

i.e. $f(2) = (2)({2^2}^2 - 1)$

i.e. $f(2) = (2)(2^2 - 1)(2^2 + 1)$

i.e. $f(2) = (2){(2 - 1)(2 + 1)(2^2 + 1)}$

i.e. $f(2) = (2){(1)(3)(4 + 1)}$

i.e. $f(2) = (2){(1)(3)(5)}$

i.e. $f(2) = (2)(15)$

i.e. $f(2) = 30$ which is divisible by $30$

Assume $f(n)$ is divisible by $30$ where $n$ is a natural number

let, $f(n) = 30(\zeta)$ where $\zeta$ is a natural number

take the case when $k = n + 1$ where $n$ is a natural number

i.e. $f(n+1) = (n+1)^5 - (n+1)$ -------(2)

i.e. $f(n+1) = (n+1)((n+1)^4 - 1)$

i.e. $f(n+1) = (n+1)((n+1)^2 - 1)((n+1)^2 + 1)$

i.e. $f(n+1) = (n+1)((n+1) - 1)((n+1) + 1)((n+1)^2 + 1)$

i.e. $f(n+1) = (n+1)(n)(n+2)(n^2 + (2)(n) + 1^2 + 1)$

i.e. $f(n+1) = (n)(n+1)(n+2)(n^2 + (2)(n) + 2)$ -------(3)

A careful observation will reveal that the product of three consecutive natural numbers $(n)(n+1)(n+2)$ will always be divisible by 6

let, $(n)(n+1)(n+2) = (6)(\beta)$ where $\beta$ is a natural number

i.e. $f(n+1) = (6)(\beta)(n^2 + (2)(n) + 2)$ -------(4)

i.e. $f(n+1) = (6)(\beta)f_{5}(n)$ -------(5)

here, $f_{5}(n) = (n^2 + (2)(n) + 2)$ -------(6)

Now one just needs to show that $(\beta)f_{5}(n)$ is divisible by $5$ which indeed is

Consider, $f(n+1) - f(n) = (n+1)^5 - (n+1) - (n^5 - n)$

i.e. $f(n+1) - f(n) = (n+1)((n+1)^4 - 1) - n(n^4 - 1)$

i.e. $f(n+1) - f(n) = (n+1)((n+1)^2 - 1)((n+1)^2 + 1) - n(n^2 - 1)(n^2 + 1)$

i.e. $f(n+1) - f(n) = (n+1)(n)(n+2)((n+1)^2 + 1) - n(n-1)(n+1)(n^2 + 1)$

i.e. $f(n+1) - f(n) = (n)(n+1)((n+2)((n+1)^2 + 1) - (n-1)(n^2 + 1))$

i.e. $f(n+1) - f(n) = (n)(n+1)((5)n^2 + (5)n + 5)$

i.e. $f(n+1) - f(n) = (n)(n+1)(5)(n^2 + n + 1)$, which is divisible by $5$

we also know that $f(n+1)$ and $f(n)$ is always an even number which leads to the conclusion that $f(n+1)$ and $f(n)$ is a multiple of $5$ because the difference of two even numbers is divisible by $5$ $iff$ the numbers are individually divisible by $5$

Now $6$ and $5$ are relatively prime to each other

i.e. f(n+1) must be a multiple of 6 and 5 concurrently

i.e. $f(k) = k^5 -k$ is always divisible by 30