Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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.
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/