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 
divisible by 5, and prove that your answer is correct.

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.

Does this help?  Write back if you'd like to talk about this 
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).

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

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