Associated Topics || Dr. Math Home || Search Dr. Math

### Proving Divisibility

```Date: 04/30/2002 at 06:02:08
From: Emily Wong
Subject: Proving divisibility

Dear Dr Maths,

Prove that 1^99 + 2^99 + 3^99 + 4^99 + 5^99 is divisible by 15.

I'm, not sure how to start the problem.

Thank you very much for your help.

Yours sincerely,
Emily Wong
```

```
Date: 05/02/2002 at 11:51:15
From: Doctor Douglas
Subject: Re: Proving divisibility

Hi, Emily,

Thanks for submitting your question to the Math Forum.

This is a very interesting problem in number divisibility!

Let's call the number N:  N = 1^99 + 2^99 + 3^99 + 4^99 + 5^99
If you could show that N is divisible by 3 AND that N is also
divisible by 5, then it would be divisible by 15.

Can you finish off the problem with this hint? You probably already
know techniques for determining whether or not a number is divisible
by 3 and by 5. You may have to break the number N into parts (i.e.
1^99, 2^99, etc., and test whether each individual part is divisible
by three and/or five).

Write back if you get stuck!

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

```
Date: 05/03/2002 at 04:55:35
From: Emily Wong
Subject: Proving divisibility

Dear Dr Douglas,

I am still quite stuck. I'm not sure how to prove that, for example
2^99 is divisible by 3 and/or 5 because 2^99 is such a large number.

Thank you very much.

Yours sincerely,
Emily Wong
```

```
Date: 05/03/2002 at 12:31:25
From: Doctor Douglas
Subject: Re: Proving divisibility

Hi, again, Emily.

For divisibility by three, what will matter is the total digit sum of
the number N. So we need to know what the remainder is (upon dividing
by three) of ALL of the individual parts: 1^99, 2^99, 3^99, 4^99, and
5^99. The sum N may be divisible by three even if the individual parts
are not.

Let's consider 2^99:

2^1 = 2                     has remainder 2 when divided by 3
2^2 = 2 x 2^1 = 2 x (3k+2)  3k+2 has remainder 2, k is some integer
= 6k + 2x2 = 6k + 4
= (6k + 3) + 1          2^2 has remainder 1 when divided by 3
2^3 = 2 x 2^2 = 2 x (3k+1)  here k is a different integer
= 6k + 2                2^3 has remainder 2 when divided by 3
2^4 = 2 x 2^3 = 2 x (3k+2)
= 6k + 4 = (6k+3) + 1   2^4 has remainder 1 when divided by 3

and so on. I think you can see the pattern. We know from this
reasoning that 2^99 will have remainder 2 when divided by 3, even
though we don't know all of the actual digits in 2^99. And it's okay
that 2^99 divided by 3 isn't an integer, because we don't know yet
what will happen with the other terms in N. If you carry out similar
analyses for 1^99, 3^99, 4^99, and 5^99, you'll be able to see what
the various remainders will be upon dividing by 3, and whether or not
the *sum* of the remainders is a multiple of three - if it is, then
N is divisible by 3. Of course 1^99 is easy - its remainder is 1, and
3^99 is obviously divisible by 3 (remainder = 0).

Now the analysis for divisibility-by-five is a little easier, since
we only need the final digit in each part. If the five final digits
from the five terms add up to something that ends in 5 or ends in
zero, then N will be divisible by 5.

2^1 = 2      ends in 2
2^2 = 4      ends in 4
2^3 = 8      ends in 8
2^4 = 16     ends in 6
2^5 = 32     ends in 2
2^6 = 64     ends in 4
2^7 = 128    ends in 8
2^8 = 256    ends in 6
2^9 = 512    ends in 2

Do you see how this pattern continues? Every factor of 2^4 doesn't
change the digit:

2^(k+4) mod 10 = 2^(k) mod 10      for any positive integer k

where "mod 10" means take the remainder upon dividing by 10.  So
the final digit in 2^99 is

2^99 mod 10 = (2^4 * 2^95) mod 10
= 2^95 mod 10                    using the pattern we found
= (2^4 * 2^91) mod 10
= 2^91 mod 10 = 2^87 mod 10
= ... =
= 2^3 mod 10 = 8                 so the final digit in 2^99 is 8.

You'll have to apply similar analyses to 3^99 to find its final digit.
But at least 1^99 and 4^99 and 5^99 are relatively easy. Once you have
the five final digits, you can add them up to see whether or not their
*sum* ends in 5 or 0 and hence, divisible by 5. And that will imply
that N is divisible by 5.

By combining these two facts (N is divisible by both 5 and 3), you'll
be able to show that N is divisible by 15.

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

```
Date: 05/04/2002 at 02:29:09
From: Emily Wong
Subject: Proving divisibility

Dear Dr Douglas,

Thank you very much for your help.  I am very grateful.

Yours sincerely,
Emily Wong
```
Associated Topics:
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