I found this in an article in The American Mathematical Monthly Vol. 1, No. 6, Jun., 1894. The article is taken from a paper by J. W. NICHOLSON., President and Professor of Mathematics at Louisiana State University.
To keep it simple I will present a very small example of the professor's theorem.
Pick a prime number, p (I'll use five because it keeps things short and easy) .
Now take the sum of the squares of every integer smaller than p and "voila", it is divisible by p
42 + 32 + 22 + 12 = 30, which is divisible by 5.
and it doesn't have to be a square, the same series using cubes gives:
43 + 33 + 23 + 13 = 100, which is also divisible by 5.
In general, the first baby rule says for prime p, (p-1)n + (p-2) n + ... + 1n will be divisible by p as for any power n smaller than p.
Go ahead, try a few of your own.
Now to kick it up a little... let's add in any constant, c, to the mix.
It is also true, that for prime p and n smaller than p:
(c+p-1)n+(c+p-2)n ...... + (c+0)n will also be divisible by p.
If I keep p = 5 and use c=2 the series would be :
(2+4)2+(2+3)2++(2+2)2+(2+1)2 + (2+0)2 =90 which is still divisible by 5.
Ok, and one to grow on: you can use a constant multiplier in front of the p-x terms... for example using a multiplier of three in each case we have
(2+3x4)2+(2+3x3)2+(2+3x2)2+(2+3x1)2 + (2+0)2 =410 which is still divisible by 5.
According to the Professor, this works only if, we use a prime p, As pointed out in the comments, there are some primes for which this is not true (and some non primes for which it is true in at least one of the versions described. I originally misstated what he wrote.
No justification was given, and I could provide none, but the brilliant Joshua Zucker sent a few guidelines to assist:
The group of units mod p is cyclic.
So we are summing 1 through p-1, which for p odd, means we have 0 mod p.
Now, any odd power won't cause a problem because we can still pair x with -x to get a sum of 0.
I think we can deal with all the powers by viewing all the numbers as powers of some generator mod p, but I'm too lazy to work out the details.
Anyway, the point of the group being cyclic mod p is that your addition of a constant and multiplication by a constant leaves your numbers the same mod p, so the second half of things is pretty much doing nothing.
So we are summing 1 through p-1, which for p odd, means we have 0 mod p.
Now, any odd power won't cause a problem because we can still pair x with -x to get a sum of 0.
I think we can deal with all the powers by viewing all the numbers as powers of some generator mod p, but I'm too lazy to work out the details.
Anyway, the point of the group being cyclic mod p is that your addition of a constant and multiplication by a constant leaves your numbers the same mod p, so the second half of things is pretty much doing nothing.
8 comments:
I've programmed this and find that n<p-1, rather than the n<p as suugested in the blog. Any return comments?
I also find that the additive and multiplicative constants (e.g.,(a+m*p), can be positive or negative.
And finally, I find that the additive and multiplicative constants may be complex. Of course, the results will be Gaussian integers.
I'm not sure what you thoughts are on your n<p-1 comment. If there is an error, let me know. My examples used n<p. Trying the first rule to test 7 just now, I used 7-1 = 6 for my largest value and got( 6^2+5^2 + 4^2 + 3^2 + 2^2 + 1)/7=13. Help me figure out what you think ke may have gotten wrong.
I'm not sure what you thoughts are on your n<p-1 comment. If there is an error, let me know. My examples used n<p. Trying the first rule to test 7 just now, I used 7-1 = 6 for my largest value and got( 6^2+5^2 + 4^2 + 3^2 + 2^2 + 1)/7=13. Help me figure out what you think ke may have gotten wrong.
Thank you so much for responding. I'm talking about the power n to which p-1, p-2, etc are raised. Your demo with was with n=2. Try this with n=6, which is p-1. That is (6^6+5^6+4^6+3^6+2^6+1)/7=9595.857...
The blog says "divisible by p for any power n smaller than p." I'm saying, "...smaller than p-1."
I have checked the referenced article by Nicholson and find that my assertion is correct. Nicholson uses (n+1), our p, as the prime number and asserts that the division property applies when the power x, or n in our notation, x<n. Or in Pat's notation, n<p-1. I apologize if there is any confusion because the original article and the blog use the parameter n in different connotations. The article is available at JSTOR. There is also a biography of Nicholson in the same issue that you might find interesting.
Post a Comment