hey guys am having major problems with this question:

show that is always divisible by 30

i tried mathematical induction, which would have worked if it needed to be divisible by 10, but not 30!

please help!

Printable View

- April 11th 2011, 11:19 PMwik_chick88Divisibility of (n^5 - n) by 30
hey guys am having major problems with this question:

show that is always divisible by 30

i tried mathematical induction, which would have worked if it needed to be divisible by 10, but not 30!

please help! - April 11th 2011, 11:50 PMchisigma
- April 12th 2011, 12:28 AMDrexel28
- April 12th 2011, 12:39 AMShanks
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.

- April 12th 2011, 01:34 AMDeveno
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 :)