Hacker News new | past | comments | ask | show | jobs | submit login
Numerators of harmonic numbers (johndcook.com)
33 points by ColinWright on July 20, 2015 | hide | past | favorite | 8 comments

Wolstenholme's theorem that the numerator of H_{p-1} is a multiple of p^2 is a bit tricky to prove, but the weaker result that the numerator is a multiple of p is very straightforward. Here are two ways.


Multiply through by P := 1.2.3...(p-1); note that if a fraction's numerator is a multiple of p after doing this, it must have been before as well. Now what we have is obviously an integer; it's P/1 + P/2 + P/3 + ... + P/(p-1).

Clearly none of these terms is a multiple of p. And no two of these terms can be equal mod p, because if P/a-P/b is a multiple of p then so is ab(P/a-P/b) = (b-a)P, but that's impossible: neither b-a nor P is a multiple of p, and p is prime.

So their values mod p must be 1,2,3,...,p-1 in some order, and when you add those up you get a multiple of p. We're done.

(For an audience familiar with the relevant ideas, this can be considerably abbreviated: "Mod p, this is the sum of the inverses of 1,2,...,p-1, and these are just 1,2,...,p-1 in some order, whose sum is 0, QED.")


Group the fractions in pairs: 1/k and 1/(p-k). The sum of each pair is p/k(p-k) and of course when we add these up the numerator is still a multiple of p (because there are no p's in the denominator). Done.

(I think the first of these is really the simpler and more informative of the two, even though the second is shorter.)

Is it true only for primes? Is there a case for which the rule holds but p isn't prime?

"Leudesdorf has proved that for a positive integer n coprime to 6"


Have you actually tried it? There is code in the article - have you tried running it? If so, what have you tried, and what answers did you get? If not, why not?

I've tried it, and used it to test primality. Then I thought I might be biased.


Looking carefully, you have this very, very wrong. You've said:

    Today I found something called Wolstenholme’s
    theorem, which says: 

        A number n (> 3) is prime if the numerator
        of H(n-1) is a multiple of n², where
        H(n) =  1/1 + 1/2 + ... 1/n
No, no, no, no, no ...

The theorem says:

        For a prime p > 3, the numerator of H_{p-1}
        is divisible by p^2.
You have your "if" condition the wrong way round.

I've tried to comment on your blog, but it requires a login using any of several techniques, none of which I use, and none of which I'm willing to create just for this. So I didn't.

Thank you for taking out the time. I've updated my post now.

Being true for primes does not mean that it's true only for primes. With regards composites the result (as it stands) says nothing, so for a given composite it might be true or false, and you'd need to test.

That means that if a number fails this test then it's definitely not prime, but if it passes then it may or may not be prime.

However, this link (as included in another comment) gives more information:


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact