How can you prove that $n^5-n$ is divisible by $30$ for any integer $n\ge 2$?

[Ackbach]

Here is this week's POTW:

-----

For any integer $n\ge 2$, prove that $n^5-n$ is divisible by $30$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to lfdahl, Sudharaka, Petek, Kiwi, Fallen Angel, kaliprasad, and MarkFL for their correct solutions! I'm very glad to see such enthusiastic participation in the University POTW!

There were essentially three different methods represented by the above submissions, so I will post three representative solutions, one for each method:

Solution by MarkFL:

Spoiler

Suppose we write as our induction hypothesis $P_n$:

\(\displaystyle n^5-n=30k\) where \(\displaystyle k\in\mathbb{N}\)

Checking the base case $P_2$, we find:

\(\displaystyle 2^5-2=30k\)

\(\displaystyle 30=30\cdot1\)

The base case is true, so as our induction step, let's add the following to $P_n$:

\(\displaystyle \left((n+1)^5-(n+1)\right)-\left(n^5-n\right)=5n(n+1)\left((n+2)^2-3n\right)\)

Now, since one of $n,\,n+1,\,n+2$ must be divisible by 2 and one must also be divisible by 3 (and in the case of $n+2$ being divisible by 3, then $3n$ is as well), we may write:

\(\displaystyle 5n(n+1)\left((n+2)^2-3n\right)=30p\) where \(\displaystyle p\in\mathbb{N}\)

And so we obtain:

\(\displaystyle (n+1)^5-(n+1)=30k+30p=30(k+p)\)

Thus, we have derived $P_{n+1}$ from $P_n$, thereby completing the proof by induction.

Solution by Kiwi:

Spoiler

For any integer a we can express n as:

n=ab+r for some integers b and r where \(0 \leq r \lt a\)

\(\therefore n^5-n=(ab+r)^5-ab-r \equiv r^5-r\) mod a

Now if a = 5 then \(r \in \{0,1,2,3,4\} \text{ and } r^5-r \in \{0^5-0,1^5-1,2^5-2,3^5-3,4^5-4\}\) but all of these are congruent to zero so \(r^5-r \equiv 0\) mod 5

Simiarly if a = 3 then \(r \in \{0,1,2\} \text{ and } r^5-r \in \{0^5-0,1^5-1,2^5-2\}\) but all of these are congruent to zero so \(r^5-r \equiv 0\) mod 3

And if a = 2 then \(r \in \{0,1\} \text{ and } r^5-r \in \{0^5-0,1^5-1\}\) but all of these are congruent to zero so \(r^5-r \equiv 0\) mod 2

\(n^5-n\) is divisible by the primes 2,3 and 5 so by the unique factorisation of n into primes \(n^5-n\) is divisible by their product which is 30.

Solution by Sudharaka:

Spoiler

By Fermat's Little Theorem $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)\]

Again by Fermat's Little Theorem $n^3-n$ is divisible by 3 and hence $n^5-n$ is divisible by 3.

\[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)\]

Once again, by Fermat's Little Theorem $n^2-n$ is divisible by 2 and hence $n^5-n$ is divisible by 2. Therefore $n^5-n$ is divisible by 5, 3, and 2 and hence it is divisible by $5\times 3\times 2=30$.