Germain's "easy" theorem relies on the observation that a pth power (mod q) is 1, -1, or 0 if p and q=2p+1 are both prime. Thus, if we had a solution to
we would find, on reducing (mod q), that a sum of terms, each just 1, -1, or 0, was 0. Since we can always require that x, y, and z share no common factor, by dividing it out if necessary, we see that not all three terms can be 0 (which would imply that q was a factor shared by all three terms). Neither can all three terms be different from 0. In fact, the only possibility is that 1, -1, and 0 each occur exactly once. This means that exactly one of x, y, or z is a multiple of q.
Germain's Theorem says that if p and q=2p+1 are odd primes (i.e., p is a Germain prime), and x, y, and z are integer solutions to
,then one of x, y, or z is a multiple of p.
We will prove it by assuming we have a solution in which none of x, y, or z is a multiple of p, and showing that this leads to an absurdity. (As before we can assume that there is no integer factor common to all three terms.)
The proof begins with a clever, but familiar, factorization:
The last factor on the right, which we shall sometimes denote by ( ) in what follows, is a sum of p terms.
Lemma: The two terms in this factorization, (y+z) and ( ), are relatively prime.
Proof of Lemma: Assume a prime r divides both factors. Then y+z=0 (mod r), so that y=-z (mod r). Then in the expression ( ), which is also divisible by r, and hence 0 (mod r), we can replace z by -y everywhere, and find, more simply,
Now p could not be 0 (mod r), unless p were r, because they are both prime. But then p would divide x, contrary to assumption, because it divides (y+z), which is a factor of x. Thus p is not 0 (mod r), and hence y=0 (mod r). But then z=-y=0 (mod r), and hence x, (which has (y+z) as a factor), is also 0 (mod r). We have deduced that all of x, y, and z must have r as a factor, which is absurd, since we could always divide out such a factor. Thus the lemma is proved.
Thus every prime which is a factor of (y+z) appears p times, which is to say (y+z) is a pth power of an integer, and similarly for ( ). By permuting x, y, and z, we find analogous results for (x+z) and (x+y):
for some integers A, B, C, and D. Now we know exactly one of x, y, and z is a multiple of q, by the easy theorem. Let us call that one x. Then y and z are different from 0 (mod q). Solving for x and reducing (mod q), we find
Now the easy theorem tells us that one of A, B, or C is 0 (mod q). Since x=0 (mod q), it cannot be B or C, which would then imply that y or z is also 0 (mod q). Thus A=0 (mod q). But then y=-z (mod q), and hence
Since y is not 0 (mod q), it is either 1 or -1, because it is a pth power of an integer C. When it is raised to the even power p-1, it is 1. Thus p itself is the pth power of an integer D (mod q). But that means that p itself must be 1 or -1 (mod q), and this is absurd! (After all, q=2p+1, so p is roughly q/2, and cannot be within 1 of q.) This is the contradiction which shows that the original hypothesis cannot be true. Thus one of x, y, or z must be a multiple of p after all.
The "easy" theorem is easy because it is really a statement about modular arithmetic: more precisely, about pth powers (mod q), where q=2p+1. But Germain's theorem itself is deeper, because it is a statement about the integers themselves, not just modular arithmetic. You will see this in the following assignment, where we imagine perhaps we could prove Germain's theorem the same way we prove the "easy" theorem. Recall that there we simply reduce pth powers (mod q) and see what happens: we find one of the pth powers must be 0 (mod q). So perhaps if we reduce (mod p), we would see that one of the pth powers must be 0 (mod p)? That would be a much easier proof! But it doesn't work, as you will see:
(a) What can you say about pth powers (mod p)? That is, what is x^p (mod p)? You may think you couldn't possibly know, but do some examples: you will be surprised! Here p is a prime, of course.
(b) Let p be a Germain prime greater than 3, and find a solution to
such that none of x, y, or z is 0 (mod p).
(c) If Germain's Theorem is true, how is (b) possible??