Math Help - Divisibility by 30

1. Divisibility by 30

Does any one want to try this. I spent hours on it.

prove that 30| n^9 - n.

2. I might take a crack at it, but don't want to duplicate your work. What have you tried?

Do you know how to use the Principle of Mathmatical Induction?
Can you state divisibility by 30 in any other way?

3. Originally Posted by karlito03
Does any one want to try this. I spent hours on it.

prove that 30| n^9 - n.

Without induction:

$n^9-n=n(n^8-1)=n(n^4-1)(n^4+1)=n(n^2-1)(n^2+1)(n^4+1)=n(n-1)(n+1)(n^2+1)(n^4+1)$.

Well, now just prove that the above is always divisible by 2, by 3 and by 5 and you're done.

Tonio