Proving Divisibility

Date: 09/11/2003 at 05:35:24
From: Inari
Subject: divisibility

Prove:

  1.  that (n^2 - n) is divisible by 2 for every integer n
  2.  that (n^3 - n) is divisible by 6
  3.  that (n^5 - n) is divisible by 30

I know that 

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

Since n and n-1 are consecutive integers, one of them must be divisible
by 2, so their product is divisible by 2.  

Likewise, 

  n^3 - n = (n-1)n(n+1).  

Therefore, one of these factors is divisble by 2, one of the others is
divisible by 3, which implies that (n^3 - n) is divisble by 6 (i.e.,
it's divisible by both 2 and 3).  

But I'm stuck on the third one.  I know that 

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

How do I show that this is divisible by 2, 3, and 5, and thus by 30?

Date: 09/11/2003 at 12:48:43
From: Doctor Edwin
Subject: Re: divisibility

Hi, Inari.

Ooh, neat puzzle. You've done well so far -- well enough that I don't 
want to spoil the fun by giving too much away. So here's your hint: 
Think only about the last digit of n. 

Write back if you're still stuck and I'll help unstick you.

- Doctor Edwin, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 09/12/2003 at 01:54:45
From: Inari
Subject: divisibility

Whatever the last digit of n is, (n^5 - n) will always have 0 as the 
units digit.  This means that (n^5 - n) is divisible by both 2 and 5.
  
Also, 

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

We've already shown that (n-1)n(n+1) is divisible by 3 (from the 2nd
part of the question).  Therefore, (n^5 - n) is divisible by 2, 3, and
5, and is therefore divisible by 30.  Is this correct?

Date: 09/12/2003 at 08:00:29
From: Doctor Edwin
Subject: Re: divisibility

Nice! And neater than my proof, which was unnecessarily complicated. 
Good job.

- Doctor Edwin, The Math Forum
  http://mathforum.org/dr.math/