A prime number $p$ is a Sophie Germain prime when $2p+1$ is also prime. 5 is one, because 11 is prime. 7 is not, because $15=3\cdot5$. The list begins:

$$2,\ 3,\ 5,\ 11,\ 23,\ 29,\ 41,\ 53,\ 83,\ 89,\ 113,\ 131,\ldots$$

The prime $2p+1$ that goes with each is called a safe prime: $5, 7, 11, 23, 47, 59, 83, \ldots$ Sophie Germain needed them for her theorem on Fermat. Two centuries later, they protect internet connections.

Do they run out?

Below 100 there are 10 Sophie Germain primes; below 1000, 37. They become rarer, but they keep appearing. Nobody knows how to prove there are infinitely many. It is an open problem, in the same family as the twin prime conjecture, which asks whether there are infinitely many pairs of primes like $11$ and $13$ that differ by 2.

Chains

Sometimes the operation can be repeated. Starting from $2$:

$$2\to5\to11\to23\to47,$$

all prime, until $2\cdot47+1=95$ is not. A sequence like this is called a Cunningham chain, after the British soldier and mathematician Allan Cunningham, who studied them early in the twentieth century. The chain from 89 is long too: $89\to179\to359\to719\to1439\to2879$, six primes in a row.

A theorem of Euler and Lagrange

Mersenne numbers $2^p-1$ are the favourite candidates for giant primes. Euler stated, and Lagrange proved in 1775, that safe primes can spoil the party:

If $p$ is a Sophie Germain prime with $p\equiv3\pmod4$, then $2p+1$ divides $2^p-1$.

For $p=11$ we have $2p+1=23$, and indeed $2^{11}-1=2047=23\cdot89$. For $p=23$, $2^{23}-1=8\,388\,607=47\cdot178\,481$. So, at a stroke, infinitely many Mersenne numbers are ruled out, if there are infinitely many Sophie Germain primes of this form.

Cryptography

When you open a secure website, your computer and the server need to agree on a secret key over a network anyone can listen to. One of the most widely used methods for this, created by Whitfield Diffie and Martin Hellman in 1976, does arithmetic modulo a huge prime $q$, with hundreds of digits.

Its security depends on a certain problem, the discrete logarithm, being hard modulo $q$. It becomes easy when $q-1$ breaks into small factors. That is why the standards recommend a safe prime, $q=2p+1$, with $p$ also prime: then $q-1=2p$ has a giant prime factor, and that shortcut is closed. The prime Sophie Germain used as an auxiliary to study Fermat became a padlock.

Exercise: check that 2p + 1 divides 2ᵖ − 1 for p = 3, but not for p = 5

For $p=3$, which is $\equiv3\pmod4$: $2p+1=7$ and $2^3-1=7$. It divides. For $p=5$, which is $\equiv1\pmod4$: $2p+1=11$ and $2^5-1=31$, which is not a multiple of 11. The theorem only holds for $p\equiv3\pmod4$; for $p\equiv1\pmod4$ what happens is that $2p+1$ divides $2^p+1$: $2^5+1=33=3\cdot11$.

Exercise: continue the Cunningham chain that starts at 41

$41\to83\to167\to335$. The first three are prime, but $335=5\cdot67$ is not. The chain has length 3.

Sources: biography of Sophie Germain, MacTutor · Whitfield Diffie and Martin Hellman, “New Directions in Cryptography” (1976) · RFC 7919, finite field Diffie-Hellman groups.

All Sophie Germain topics · ← Sophie Germain’s theorem and Fermat’s Last Theorem · The Sophie Germain identity: factoring what looks prime →

Image credits.