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

8 Answers 8

up vote 6 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

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

share|improve this answer
    
$\beta = (3/2)x^2 - (3/2)x + 1$ where x is a natural number –  Rajesh K Singh Jul 24 '12 at 14:55
    
i.e. $\beta = 3y + 1$ where $y$ is a natural number –  Rajesh K Singh Jul 26 '12 at 11:23
    
This is a tough read. The case $k=2$ is unnecessary, and the steps ... Yikes. Why not just say $f(2) = 32-2=30$?? –  The Chaz 2.0 Jul 27 '12 at 17:18

Your Answer

 
discard

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.