The following algebraic identity is due to Sophie Germain:
She discovered this identity in her explorations related to Fermat's last theorem and primality testing. The identity is often used to find factors of integers of a certain form, and is common in contest mathematics. Here is a basic example:
Prove that is composite.
Then, by the Sophie Germain identity with and :
which is the product of two integers which are each greater than 1.
Note that if are positive integers, both factors of are sums of two squares and are positive integers greater than unless and i.e. (In this case, is in fact prime.) This fact is often useful in proofs (it is used several times in the last section of this wiki).
Here are a few typical applications of the identity.
Show that for any positive integer is not a prime.
The proof is similar to the example in the introduction. If is even, then so is If is odd, say then
and both factors are
While it is often enough to know that a factorization exists, sometimes the form of the factorization is useful, as in the following problem and examples:
(MIT ATF Math Prize for Girls, 2011)
The number is divisible by a five-digit prime number. What is it?
Notice that looks like the fourth row of Pascal's triangle; that is,
So our number is Apply Sophie Germain's identity to factor it as
The only possible five-digit prime factor is and since we are given that there is a five-digit prime factor, this must be it.
Sophie Germain's identity appears in an important question in abstract algebra: "Under what conditions on and is the polynomial irreducible?"
It's clearly necessary that not be an power, but this is not enough. For instance, factors over the rational numbers as So in fact it is also necessary that not be a power for any prime dividing
Is this condition sufficient, or are there other counterexamples?
Yes, if is divisible by and for some the polynomial factors by Sophie Germain's identity.
It turns out that this is the entire list of counterexamples:
Let be a field, and let be a positive integer. Then is irreducible over if and only if
is not a power for any , and
if is not of the form for
The proof is beyond the scope of this wiki, but the upshot of the theorem is that Sophie Germain's identity is essentially the "only" nontrivial factorization of a binomial of this type.
This section is dedicated to the proof of the following theorem:
Let be nonnegative integers. The only solutions to are and
The proof involves Sophie Germain's identity in multiple cases.
Look mod : So and is even. Write so the equation becomes
Now look mod : is impossible, so the equation becomes so exactly one of and is even.
Case 1: is even, is odd.
Write and the equation becomes so Sophie Germain's identity gives a factorization
The difference between the two factors is which is not divisible by but both factors are powers of so the only possibility is that the second one is This means that and which gives
Case 2: is odd, is even.
Write and the equation becomes Look mod : so is even. Write and now we have Then factorization gives
Again, the difference between these two factors is which is not divisible by so
Looking modulo we get that is odd, say so and Sophie Germain's identity gives
and again the difference between the two factors is which is not divisible by so the second factor is which implies So and which gives and hence
The proof is complete.
(Reference: Carl Johan Ragnarsson, "An Interesting Application of the Sophie Germain Identity," Mathematical Mayhem v. 26, no. 7, pp. 417-428.)