In the late 1630s, Pierre de Fermat (1601-1665) wrote a marginal note in his copy of Claude Bachet's Latin translation of Diophantus's Arithmetica that was to intrigue mathematicians for the next 300 years.
"It is impossible to separate a cube into two cubes, or a biquadrate into two biquadrates, or in general any power higher than the second into two powers of like degree; I have discovered a truly remarkable proof which this margin is too small to contain."
In modern symbolic notation, which Fermat did not have available to him, this claim is known as
Fermat's Last Theorem (FLT):
xn + yn = zn
has no positive integer solutions for x, y, z when n > 2
We now know, of course, that Fermat's Last Theorem is true for every value of n > 2 thanks to the crowning work of Andrew Wiles, first described in 1993 and then published in 1995. But as L.E. Dickson wrote in 1917,
This challenge problem has received attention of many mathematicians of the highest ability, including Euler, Legendre, Gauss, Abel, Sophie Germain, Dirichlet, Kummer and Cauchy.
Quite a list of distinguished mathematicians! It is interesting that Dickson gave the first name of only one person on this list. Perhaps it was because of all the names given, he felt that Sophie Germain would be the least recognized by most readers. But indeed, Sophie Germain was one of the first to provide a partial solution for a large class of exponents.
The case n = 4 had been settled by Fermat when he used his method of infinite descent to prove that the area of a right triangle with rational sides is never a perfect square, a condition that is equalivant to the claim that there are no integer solutions to x4 + y4 = z2, and hence no solutions to x4 + y4 = z4. Because any integer greater than 2 is either a multiple of 4 or contains a factor that is an odd prime, it therefore suffices to prove FLT for odd prime exponents. For example, if n = 4k has solutions for x, y, and z, then
x4k + y4k = z4k => (xk)4 + (yk)4 = (zk)4
would say there is a solution for n = 4, which we know is impossible. A similar argument shows that if there is no solution for an exponent that is a prime greater than 2, then there is no solution for any exponent containing that odd prime factor.
In 1770 Euler published a proof of FLT for n=3, although the proof is now considered incomplete because one step involving the divisibility properties of integers of a special form was done without sufficient justification. Gauss also gave a proof for n=3 that was not published until after his death. The cases n=3 and n=4 were therefore all that was known at the time that Sophie Germain wrote her first letter to Gauss on November 21, 1804, using the pseudonym Antoine Le Blanc. In her letter, she said
"I add to this art some other considerations which relate to the famous equation of Fermat xn + yn = zn whose impossibility in integers has still only been proved for n = 3 and n = 4; I think I have been able to prove it for n = p-1, p being a prime number of the form 8k+7. I shall take the liberty of submitting this attempt to your judgement, persuaded that you will not disdain to help with your advice an enthusiastic amateur in the science which you have cultivated with such brilliant success."
There is no further mention, however, of Germain's proof or of Gauss's respone, if any, so the proof was most likely incorrect. In 1819, Germain returned to the study of number theory and in a letter to Gauss dated May 1819 she wrote
"Although I have labored for some time on the theory of vibrating surfaces (to which I have much to add if I had the satisfaction of making some experiments on cylindrical surfaces I have in mind), I have never ceased to think of the theory of numbers...A long time before our Academy proposed as the subject of a prize the proof of the impossibility of Fermat's equation, this challenge...has often tormented me."
Germain also corresponded with Adrien-Marie Legendre. In one of her letters to Legendre in the early 1820's she proved that if n is an odd prime and if 2n+1 is prime, then xn + yn = zn implies that x, y, or z is divisible by n. Notice that this is not quite Fermat's Last Theorem, but it does say that if there is a solution to FLT for that value of n, then one of the numbers must be divisible by n. For example, n=5 and n=11 are both prime, so any solution to x5 + y5 = z5 would have to have either x, y, or z divisible by 5. Thus Fermat's Last Theorem could be broken into two cases:
FLT I: xn + yn = zn has no integer solutions for which x, y, and z are relatively prime to n, i.e. in which none of x, y, and z are divisible by n;
FLT II: xn + yn = zn has no integer solutions for which one and only one of the three numbers is divisible by n.
Germain proved that Case I holds when n and 2n+1 are both prime. A prime n for which 2n+1 is also prime is now called a Sophie Germain prime. Her proof actually showed more, however. The result now known as Sophie Germain's Theorem was presented in 1823 by Legendre in a paper to the French Academy of Sciences and included in a supplement to his second edition of The Theory of Numbers.
It is easy to see from this theorem why Case I holds for a Sophie Germain prime. Suppose p=2n+1 is a prime, where n is an odd prime. Then for any number 0 < a < p, Fermat's Little Theorem implies that (an)2 = ap-1 = 1 mod p. Therefore (an-1)(an+1) = 0 mod p, and since p is a prime, we must have either an = 1 mod p or an = -1 mod p. This means that if x, y, and z are not congruent to 0 mod p, then
xn + yn + zn = ±1 ±1 ±1
which can never equal 0 mod p. Hence property (1) in Sophie Germain's theorem is true. Moreover, it is impossible for xn = n mod p to have a solution, establishing property (2) in Sophie Germain's theorem.
For each odd prime n < 100, Germain gave a prime p for which her theorem applies, thereby showing that case I of Fermat's last theorem holds for all prime exponents less than 100.
Legendre is often credited with generalizing Germain's argument to show that properties (1) and (2) hold for the odd prime exponent n provided that one of the numbers 4n+1, 8n+1, 10n+1, 14n+1, or 16n+1 is a prime. But this result can also be found in Germain's letters as described in recent articles by Andrea Del Centina and by Reinhard Laubenbacher and David Pengelley. When n=3, the numbers 4·3+1=13, 10·3+1=31, and 14·3+1=43 are all prime, but only p=13 satisfies properties (1) and (2) for n=3 (note that p=2·3+1=7 also satisfies the two properties.) With this result Germain (and Legendre) were able to show that all prime exponents less than 197 satisfy Case I of Fermat's Last Theorem. The following table gives an auxilliary prime p=kn+1 that satisfies Sophie Germain's theorem for each of the primes less than 197. The entries in blue are the Sophie Germain primes. You can see why Germain and Legendre stopped at 197. The first prime that works for n=197 is p=7487=38·197+1.
| n | p=kn+1 | k | n | p=kn+1 | k | n | p=kn+1 | k | n | p=kn+1 | k | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 7 | 2 | 5 | 11 | 2 | 7 | 29 | 4 | 11 | 23 | 2 | |||
| 13 | 53 | 4 | 17 | 137 | 8 | 19 | 191 | 10 | 23 | 47 | 2 | |||
| 29 | 59 | 2 | 31 | 311 | 10 | 37 | 149 | 4 | 41 | 83 | 2 | |||
| 43 | 173 | 4 | 47 | 659 | 14 | 53 | 107 | 2 | 59 | 827 | 14 | |||
| 61 | 977 | 16 | 67 | 269 | 4 | 71 | 569 | 8 | 73 | 293 | 4 | |||
| 79 | 317 | 4 | 83 | 167 | 2 | 89 | 179 | 2 | 97 | 389 | 4 | |||
| 101 | 809 | 8 | 103 | 1031 | 10 | 107 | 857 | 8 | 109 | 1091 | 10 | |||
| 113 | 227 | 2 | 127 | 509 | 4 | 131 | 263 | 2 | 137 | 1097 | 8 | |||
| 139 | 557 | 4 | 149 | 1193 | 8 | 151 | 1511 | 10 | 157 | 1571 | 10 | |||
| 163 | 653 | 4 | 167 | 2339 | 14 | 173 | 347 | 2 | 179 | 359 | 2 | |||
| 181 | 1811 | 10 | 191 | 383 | 2 | 193 | 773 | 4 | 197 | 7487 | 38 |
Auxillary primes p=kn+1 satisfying Germain's Theorem for n
The observant reader might notice that the claim about when Case I holds did not include auxillary primes of the form p=6n+1 or the form p=12n+1, and that, indeed, in the table above, the values k=6 and k=12 never appear. The reason for this is that a prime of the form p=6mn+1 will never satisfy condition (1) of Sophie Germain's theorem [Proof]. For example, suppose n=5 and p=31=6·5+1. Let x=1, y=9, and z=81. None of these three integers are equal to 0 mod 31, but
15 + 95 + 815 = 3486843451 = 112478821·31 = 0 mod 31
These three integers therefore violate the requirement of property (1).
Given an odd prime n, how can one find an auxillary prime p satisfying the two properties in Sophie Germain's Theorem? One way to proceed is is to make use of a theorem by Euler.
Euler's Theorem: Let p be a prime and let 0 < a < p. Then xn = a mod p has a solution if and only if a(p-1)/d = 1 mod p, where d = (n, p-1) is the greatest common divisor of n and p-1.
Now suppose n and p-1 are relatively prime where p > n, so d=1. Then Euler's theorem would say that xn = a mod p has a solution if and only if ap-1 = 1 mod p. But this last condition holds for all values of a less than p by Fermat's Little Theorem, in particular, there is a solution to xn = n mod p. Hence property (2) is not satisfied for any prime p for which (n,p-1) = 1. This means that it is only necessary to look at possible candidates of the form p = kn+1, as Sophie Germain and Legendre did. Moreover, if k is odd, then kn+1 would be even (remember that n is an odd prime), hence not a prime. Therefore one needs to only look at cases where k is even, k is not a multiple of 6, and p=kn+1 is prime.
So consider the case when p=kn+1. Then d=(n,p-1)=n and (p-1)/d = k. To see if property (2) holds for p, it is only necessary to calculate nk. If the result is not equal to 1 mod p, then there is no solution to xn = n mod p. Checking property (1) is aided by the following observation.
Theorem: Property (1) of Sophie Germain's theorem holds for the prime n and the auxilliary prime p if and only if the set of non-zero n powers mod p does not contain two consecutive integers. [Proof]
By Euler's theorem, the set of non-zero n powers mod p has the same number of elements as the set of solutions to the equation ak = 1 mod p. But since k is a divisor of p-1, a theorem of number theory allows us to conclude that the number of non-congruent solutions to this equation is exactly k. Therefore there are exactly k non-zero n powers mod p. Moreoever, because n is odd, these power residues come in pairs of positive and negative values since an = -(p-a)n mod p. To verify property (1), therefore, it is only necessary to check k/2 positive residues. For example, suppose we take n=47 and p=47*6+1=283. The following Mathematica code computes a47 mod 283 for a=1 up to a=282.
In[78]:= Table[PowerMod[a,47,283],{a,1,282}]
Out[78]=
{1,282,239,1,45,44,238,282,238,238,238,239,238,45,1,1,45,45,282,45,282,45,44,
44,44,45,282,238,1,282,239,282,282,238,239,238,45,1,282,238,44,1,282,238,
239,239,45,239,44,239,1,238,282,1,239,45,44,282,238,1,1,44,44,1,239,1,282,
45,45,44,1,45,238,238,45,282,44,1,282,45,44,239,44,282,44,1,239,45,238,44,
44,44,238,238,238,44,238,239,44,44,44,282,44,45,238,1,45,282,239,44,1,238,
44,239,282,1,44,45,239,282,44,282,45,239,282,239,1,282,44,44,282,282,45,1,
238,238,238,238,45,239,1,282,44,238,45,45,45,45,282,238,1,1,239,239,1,282,
44,1,44,238,1,239,1,44,238,239,282,1,44,239,45,282,239,44,1,238,282,45,238,
239,1,239,239,239,44,45,239,45,45,45,239,239,239,45,238,44,282,239,1,239,44,
239,238,1,282,239,1,238,45,45,238,282,239,238,238,1,282,44,282,239,239,282,
282,45,1,239,238,44,282,1,45,282,44,239,44,238,44,44,45,1,282,239,45,1,282,
238,45,44,45,1,1,44,1,282,45,1,238,239,239,239,238,1,238,1,238,238,282,282,
238,45,44,45,45,45,1,45,239,238,282,44,1,282}
We see there are many repetitions! The set actually reduces to just the six elements {1, 44, 45, 238, 239, 282} = {±1, ±44, ±45} mod 283. The only powers we really need to check are {1, 44, 45} and in this set we see that there are two consecutive integers. Therefore property (1) of Sophie Germain's theorem does not hold for n=47 and p=283. In particular,
247 + 347 + 547 = -1 + -44 + 45 mod 283 = 0 mod 283
Of course, we should have already expected this because p is of the form 6n+1. Now take n=47 and p=47*14+1=659. This time we will not list the 47th powers mod 659 of all the integers from 1 to 658. The set of distinct residues is {±1, ±12, ±55, ±144, ±249, ±270, ±307}. This set does not contain two consecutive integers, so property (1) does hold for this auxilliary prime p.
Both properties (1) and (2) are easily checked with a computer. For example, here is some Mathematica code that will search for an auxillary prime for a given prime integer n.
g[x_,p_] := p/2 - Abs[x-p/2]
SG1[n_,k_] :=
Module[{A={}, p=k*n+1},
For[a=1, Length[A] < k/2, a++, A=Union[A,{g[PowerMod[a,n,p],p]}]];
FreeQ[Drop[A-RotateRight[A],1],1]
]
SG2[n_,k_] := Not[PowerMod[n,k,n*k+1]==1]
SGCheck[n_Integer] :=
Module[{k=2},
While[ If[Mod[k,6]>0 && PrimeQ[n*k+1],(k<100) &&!(SG2[n,k] && SG1[n,k]),
True],k=k+2];
n*k+1
] /; PrimeQ[n]
The function g simply converts the residues larger than p/2 to the corresponding positive residues less than p/2. The function SG1 checks to see if the set of non-zero n powers mod p=kn+1 contains two consecutive integers by subtracting consecutive elements in the ordered set of residues and looking for the value 1. It thus returns the value TRUE if property (1) of Sophie Germain's theorem holds for p. The function SG1 stops computing the n powers mod p as soon as it finds a set of size k/2 of positive residues less than p/2. The function SG2 returns the value TRUE if the statement nk = 1 mod p is FALSE, i.e. if property (2) of Sophie Germain's theorem holds for p. Finally, SGCheck takes a prime integer n and checks each prime p=kn+1 (for k an even integer that is not a multiple of 6) until it finds a value of k for which both conditions in Sophie Germain's theorem are true. It only searches for k < 100, however, since there is no guarantee in Sophie Germain's theorem that an auxilliary prime will always exist.
The Italian mathematician Count Guglielmo Libri had conjectured in 1832 that for a given prime n, there cannot be more than a finite number of auxilliary primes p that satisfy the two properties in Sophie Germain's theorem. A. E. Pellet showed in 1876 that Libri's conjecture was correct, but could not specify a bound for the values of p that might satisfy the properties in the theorem. In 1909, L.E. Dickson provided a second proof of the conjecture by showing that if n and p are odd primes such that
p > (n - 1)2(n - 2)2 + 6n - 2
then the congruence xn + yn + zn = 0 mod p always has integer solutions that are each relatively prime to p, thus violating property (1) of Sophie Germain's theorem. For example, if n=5, then this happens for p > 172. If we take p=5·38+1=191, then the set of 5th powers mod 191 is
{1,5,6,11,25,30,31,32,36,37,38,41,52,55,66,69,70,84,107,121,122,125,
136,139,150,153,154,155,159,160,161,166,177,180,185,186,190}
which contains several sets of consecutive integers, so property (1) fails for this value of p.
A year earlier, in 1908, Dickson also proved that if n and p=kn+1 are odd primes with k
< 27 and k not a multiple of 3, then property (1) of Sophie Germain's
Theorem always holds for this n and p except for 7 special cases. These
special cases are
n = 3 : k = 10, 14, 20, 22, 26
n = 5 : k = 26
n = 31 : k = 22
In 1951, P Dénes extended Germain and Legendre's original result by proving that if n is an odd prime and p=2kn+1 is a prime, where k is not a multiple of 3 and k < 54, then the first case of Fermat's Last is true for the exponent n. Fee and Granville extended the upper limit to k < 101 in 1991. It is not necessarily the case, however, that properties (1) and (2) in Sophie Germain's theorem hold for all these primes.
In 1985 D.R. Heath-Brown, E. Fouvry, and M. Adelman proved that there are infinitely may primes n for which the first case of Fermat's Last Theorem holds. Grosswald wrote in Mathematical Reviews that "The tools used, or quoted, in the proof are rather formidable and comprise, among others, a (very particular case of a recent) theorem of Faltings, old theorems of Sophie Germain and of Wieferich and Mirimanoff, and a generalization of Sophie Germain's theorem..."
So 150 years after Sophie Germain died, her mathematical results were still be used.
A prime number n such that 2n+1 is also prime is now called a Sophie Germain prime. Mathematicians are intrigued by finding large numbers, especially large prime numbers. The record for the largest known Sophie Germain prime (as of January 2007) is 48047305725•2172403-1, a number with 51910 digits.
There actually are applications for Sophie Germain primes in number theory and even in cryptology for digital signatures based on the Diffie-Hellman key agreement algorithm, so finding large Sophie Germain primes is actually a worthwhile pursuit.
Here's another record. The largest palindromic Sophie Germain prime is the following 1047 digit number found by Harvey Dubner:
n = 10...05321812350...01
where each ... gap represents 516 additional 0's. But there's an aesthetic problem with this number -- 2n+1 is prime, but is not a palindrome! So here's a final record, also found by Dubner:
n = 1919191918090908081808090908191919191
p = 2n+1 = 3838383836181816163616181816383838383
r = 2p+1 = 7676767672363632327232363632767676767
All three of these numbers are prime and all three are palindromes! Both n and p are therefore Sophie Germain primes. It is impossible, however, to have a sequence n, p, r of three odd Sophie Germain primes that are all palindromes (of two digits or more) because 2r+1 would always end in 5 in such a sequence and thus would not be a prime.
An excellent reference about Sophie Germain's work with Fermat's Last Theorem can be found in Mathematical Expeditions, Chronicles by the Explorers, by Reinhard Laubenbacher and David Pengelley, published by Springer in 1999. Section 4.4, pages 185-193, discusses "Germain's General Approach."
To read a very detailed reassessment of Germain's work in number theory, see the fascinating article by Laubenbacher and Pengelley called "'Voice ce que j'ai trouvé:' Sophie Germain's grand plan to prove Fermat's Last Theorem," available at www.math.nmsu.edu/~davidp. A description of their findings is also available from a 2008 two-part series in Science News called "An Attack on Fermat", by Julie Rehmeyer.