# Proof of divisibility

• Oct 13th 2008, 10:39 AM
Caity
Proof of divisibility
Prove that $\displaystyle n^5 - n$ is divisible by 5 for n in N
• Oct 13th 2008, 01:53 PM
Moo
Hello,
Quote:

Originally Posted by Caity
Prove that $\displaystyle n^5 - n$ is divisible by 5 for n in N

You can work with modulos.

By Fermat's little theorem, we know that if n and 5 are coprime, then $\displaystyle n^4 \equiv 1 (\bmod 5)$, that is to say $\displaystyle n^4-1$ is divisible by 5 and hence n^5-n is too.

If n and 5 aren't coprime, that is n is a multiple of 5, then n^5-n is obviously divisible by 5.

___________________________________
You can work with algebra :

$\displaystyle n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n+1)(n-1)(n^2-4+5)$

$\displaystyle =n(n+1)(n-1)(n^2-4)+5n(n+1)(n-1)$

$\displaystyle =n(n+1)(n-1)(n-2)(n+2)+5n(n+1)(n-1)$

you can see that n(n+1)(n-1)(n-2)(n+2) is the product of 5 consecutive integers. Therefore, there is one of the factors that is divisible by 5. Hence it is divisible by 5.
5n(n+1)(n-1) is obviously divisible by 5.