Inductive Proof of Divisibility

Date: 06/25/2002 at 01:40:06
From: Harsh Mantri
Subject: Number Theory, Divisibility Test

How do you prove that for any integer n the number (n^5)-n is 
divisible by 30?

Thanks

Date: 06/25/2002 at 08:53:51
From: Doctor Paul
Subject: Re: Number Theory, Divisibility Test

We proceed by induction on n.

The case n = 1 is obvious.

Now assume that 30 divides n^5 - n, and consider:

  (n+1)^5 - (n+1) = n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n  

A number is divisible by 30 if and only if it is divisible by 2, 3, 
and 5 (the prime factors of 30).  So we need to show that this is the 
case.

Let's first show that 

  n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n 

is always divisible by two.

If n is even, then n^5, 5*n^4, 10*n^3, 10*n^2, and 4*n will all be 
even.  Thus their sum is even (and hence divisible by two).

If n is odd, then n^5 is odd, 5*n^4 is odd, and the other three terms 
are even.  Thus 

    n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n  

  = odd + odd   + even   + even   + even 

which will be an even number.  Thus 

  n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n 

is always divisible by two.

Now let's show that 

  n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n 

is divisible by five.  Write:

    n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n 

  = (n^5 - n) + (5*n^4 + 10*n^3 + 10*n^2 + 5*n) 

  = (n^5 - n) + 5*(n^4 + 2*n^3 + 2*n^2 + n)

The second term above is clearly divisible by five.  And we've assumed
that the first term is divisible by 30, which means it must also be
divisible by 5.  

Finally, we show that 

  n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n 

is always divisible by three.  There are three possibilities:  

  1.  n is a multiple of three

  2.  n is one more than a multiple of three

  3.  n is two more than a multiple of three.

If n is a multiple of three, then

    n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n  

  = n*(n^4 + 5*n^3 + 10*n^2 + 10*n^1 + 4)

which will also be a multiple of three.

If n is one more than a multiple of three, then 

  n^5 will also be one more than a multiple of three

  5*n^4 will be five more than a multiple of three

  10*n^3 will be ten more than a multiple of three

  10*n^2 will be ten more than a multiple of three

  4*n will be four more than a multiple of three.

Thus the sum will be 

  1 + 5 + 10 + 10 + 4 = 30

more than a multiple of three.  But 30 more than a multiple of three
is in fact a multiple of three.

The case where n = 2 mod 3 (2 more than a muliple of three) is 
similar.  I'll leave it for you.

That completes the proof.

I hope this helps.  Please write back if you'd like to talk about 
this some more.

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

Date: 06/25/2002 at 13:26:55
From: Harsh Mantri
Subject: Thank you (Number Theory, Divisibility Test)

Thanks a lot, Dr. Paul. Truly it is a complete proof.