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

1 + 2^n + 3^n + 4^n Divisible by 5

```Date: 03/22/2003 at 14:41:21
From: Julie
Subject: University level problem solving

Find all positive integers n for which 1 + 2^n + 3^n + 4^n is
```

```
Date: 03/23/2003 at 08:02:24
From: Doctor Jacques
Subject: Re: University level problem solving

Hi Julie,

We can write the equation:

1^n + 2^n + 3^n + 4^n = 0 mod 5

(I replaced 1 by 1^n to make things more symmetrical).

Now, Fermat's "little theorem" states that, if p is a prime and a is
not a multiple of p,

a^(p-1) = 1 mod p

In this case, if a is not a multiple of 5, we have:

a^4 = 1 mod 5

and, for any k:

a^(4k+m) = a^m * a^(4k) = a^m mod 5

and this shows that the equation only depends on the value of
(n mod 4), i.e. you only have to check the cases n = 0, 1, 2, and 3.

Note:

This is in fact a particular case of a more general property, namely
that, if p is a prime, the sum:

1^n + 2^n + ..... + (p-1)^n = 0 mod p

if and only if n is not a multiple of p-1.

some more, or if you have any other questions.

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

```
Date: 03/24/2003 at 15:53:09
From: Julie
Subject: University level problem solving

Since you switched to mod4, I understand this is why you only check
0,1,2,3=n. However, I don't understand what to check.  0mod4=?
1mod4=? 2mod4=? and 3mod4=?  I understand I must show each of these
answers is divisible by five and then I will have completed the
question, but I don't know how to go about doing this.
```

```
Date: 03/25/2003 at 02:02:17
From: Doctor Jacques
Subject: Re: University level problem solving

Hi Julie,

As we showed, we only need to check the formula for n = 0 to 3.

For n = 0, we have:

1 + 2^0 + 3^0 + 4^0 = 1 + 1 + 1 + 1 = 4

and this is not divisible by 5.

For n = 1, we have:

1 + 2 + 3 + 4 + 5 = 10

and, in a similar way:

n = 2 : 1 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30
n = 3 : 1 + 2^3 + 3^3 + 4^3 = 1 + 8 + 27 + 64 = 100

and we see that for n = 1, 2, 3 the result is divisible by 5.

As this depends only on (n mod 4), we can conclude that the sum is
divisible by 5 iff n = 1, 2, or 3 mod 4, i.e. if n is not a multiple
of 4.

Does this make sense? Write back if you require further assistance.

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

```
Date: 03/04/2004 at 01:23:24
From: Johny
Subject: primes

Is it true that for any prime p, 1^n + 2^n + ... + (p-1)^n is
divisible by p iff n is not divisible by (p-1)?

If n | p-1, it's trivial.  I can also prove that the sum is divisible
by p if n is odd, but I'm stuck when n is even.
```

```
Date: 03/04/2004 at 03:06:58
From: Doctor Jacques
Subject: Re: primes

Hi Johny,

Indeed, if n is a multiple of (p-1), by Fermat's theorem, all terms
are 1, and the sum is (p-1).

This also shows that n can be considered modulo (p-1), i.e., we may
assume 0 <= n <= p-2.

The multiplicative group of Z_p is cyclic.  If g is a primitive root
modulo p, the elements {1, 2, ..., p-1} are the same as:

{g^0 = 1, g, g^2, ... , g^(p-2)}

in some order.

Our sum can therefore be written as:

S = 1^n + 2^n ... = g^0n + g^1n + ... g^(n(p-2))
= 1 + q + ... + q^(p-2)

with q = g^n. (All this takes place in Z_p, of course.)

Now, this is a geometric progression, and we have

S (q - 1) = q^(p-1) - 1 = 0 (by Fermat's theorem)

and, since n < p-1 and g is a primitive root, q = g^n <> 1, and we
may cancel the factor (q-1).

some more, or if you have any other questions.

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

```
Associated Topics:
College 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