From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Try to solve this Date: 18 Oct 1999 23:17:16 GMT Newsgroups: sci.math Keywords: Wolstenholme's congruence (sum 1/k = 0 mod p^2) In article <7ue8bo$sqt$1@nnrp1.deja.com>, wrote: >Prove that if p is a prime number greater than 3, then the >numerator of the (reduced) fraction > >1 + 1/2 + 1/3 + ... + 1/(p-1) > >is divisible by p^2. Perhaps I was being too defensive when I suggested that the original poster hunt for the result in Niven&Zuckerman[&Montgomery]. In response to a followup request I'll outline the proof of this ("Wolstenholme's congruence"), adapted from the NZM proof. Let f(x) = (x-1)*...*(x-[p-1]). This may be expanded as a sum of multiples of powers of x; we may write the result as f(x) = x^(p-1) - (s_1) x^(p-2) + (s_2) x^(p-3) + ... - (s_[p-2]) x + s_[p-1] say. Of course a few of these coefficients are easily identified -- for example, s_1 is the sum of the integers through p-1 which is p(p-1)/2; s_[p-1] is their product, i.e. (p-1)!. Also, s_[p-2] is the sum of all products of all-but-one at a time; a moment's thought shows this is ( 1 + 1/2 + 1/3 + ... + 1/(p-1) )*( (p-1)! ), establishing the connection with the original problem. Now, the other coefficients are rather complicated to identify as "simple" functions of p, but we don't really need to do so. All we need is the observation that all s_i, for i < (p-1), are multiples of p. This fact is easily proved from Fermat's Little Theorem, which implies that (the image of) f(x) is the same as x^(p-1) - 1 in the polynomial ring (Z/pZ) [x] . So now we prove the desired statement: observe that f(p) = (p-1)! = f(0), so 0 = (f(p) - f(0))/p = p^(p-2) - (s_1) p^(p-3) + (s_2) p^(p-4) + ... +(s_[p-3]) p - (s_[p-2]) . This is a sum of p-1 integers, all of which are clearly multiple of p^2 except for the last two, i.e. (s_[p-3]) p = (s_[p-2]) mod p^2. But on the other hand, we already showed each s_i is a multiple of p, so the left side is again a multiple of p^2, meaning that the right side is, too. Since (p-1)! is coprime to p, the numerator of 1 + 1/2 + 1/3 + ... + 1/(p-1) must already be a multiple of p^2. Remaining assignment: This proof is not valid for all primes p. Explain. Extra credit: It's easy to see that the sum of the first half of the reciprocals (i.e. through 1/( (p-1)/2 ) inclusive) is the negative of the second half, mod p; that's why the whole sum is at least a multiple of p. So what, exactly, is the value of that half-sum mod p? Weierfrich has shown that the "first case" of Fermat's last theorem is true unless 2^p = 2 mod p^2. Use the binomial theorem to show 2^(p-1)-1 = (-p/2)*( 1 + 1/2 + ... + 1/((p-1)/2) ) mod p^2, so that the Weierfrich condition only holds when the half-sum is 0 mod p. Find all primes for which this condition holds. :-) dave