1 + 2^n + 3^n + 4^n Divisible by 5Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/