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
Math Forum Home || Math Library || Quick Reference || Math Forum Search