# Divisibility of (n^5 - n) by 30

• Apr 11th 2011, 11:19 PM
wik_chick88
Divisibility of (n^5 - n) by 30
hey guys am having major problems with this question:
show that $n^5 - n$ is always divisible by 30
i tried mathematical induction, which would have worked if it needed to be divisible by 10, but not 30!
• Apr 11th 2011, 11:50 PM
chisigma
Quote:

Originally Posted by wik_chick88
hey guys am having major problems with this question:
show that $n^5 - n$ is always divisible by 30
i tried mathematical induction, which would have worked if it needed to be divisible by 10, but not 30!

Is...

$n^{5} -n = n\ (n-1)\ (n+1)\ (n^{2}+1)$ (1)

Now observing (1) we deduce that either n, or n-1 or n+1 contains 2 or 3 so that 6 devides (1). Let suppose now that neither n, nor n-1 nor n+1 contains 5 so that is $n=5 k \pm 2$ or $n= 5 k \pm 3$. Is...

$n= 5 k \pm 2 \implies n^{2}+1 = 25 k^{2} \pm 20 k +4 +1$

$n= 5 k \pm 3 \implies n^{2}+1 = 25 k^{2} \pm 30 k +9 +1$

... and in both cases $n^{2}+1$ contains 5...

Kind regards

$\chi$ $\sigma$
• Apr 12th 2011, 12:28 AM
Drexel28
Quote:

Originally Posted by wik_chick88
hey guys am having major problems with this question:
show that $n^5 - n$ is always divisible by 30
i tried mathematical induction, which would have worked if it needed to be divisible by 10, but not 30!

Or you could note it suffices to check for $n=0,1,2,-2,-1$ which is trivial.
• Apr 12th 2011, 12:39 AM
Shanks
hint：it suffices to prove that n^5-n is congruent to 0 mod 2 and 3 and 5. Apply the Fermat's little theorem.
• Apr 12th 2011, 01:34 AM
Deveno
you don't need induction, you can prove it directly.

suppose n>1.

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

one of n-1,n, or n+1 is divisible by 3.

one of n,n+1 is divisible by 2. hence n^5 - n is divisible by 6.

now if n = 5k, 5|n. if n = 5k+1, 5|n-1, and if n = 5k+4 5|n+1. so in those 3 cases, it is obvious, 5|n^5 - n.

but if n = 5k+2, n^2+1 = (5k+2)^2 + 1 = 25k^2 + 20k + 5 = 5(5k^2 + 4k + 1).

and if n = 5k+3, n^2+1 = (5k+3)^2 + 1 = 25k^2 + 30k + 10 = 5(5k^2 + 6k + 2).

so in all cases, n^5 - n is divisivble by 2,3 and 5, and since these are all co-prime, their product 30 divides n^5 - n.

my apologies to chisigma, i wrote this up before dinner, and didn't post it until after you replied :)