Sophie Germain Primes and Cunningham Chains

OldTrout, Going Postal
Sophie Germain

A Sophie Germain prime is a prime number \(p\) such that \(\,2p + 1\) is also a prime number.

That is, \(\,p : 2p + 1 = q\),  where \(p\) and \(q\) are both prime.  For example, \(\,29 + 29 + 1 = 59\).

The sequence begins \(\,2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, . . .\)

Sophie Germain (\(1776 – 1831\)) explored these primes whilst working on Fermat’s Last Theorem which was finally proved by Wiles in \(1995\).

A Cunningham Chain (of the first kind) is a sequence of prime numbers such that all except the last are Sophie Germain primes.

A chain of length five is \(\{2, 5, 11, 23, 47\}\).  A chain of length six is \(\{89, 179, 359, 719, 1439, 2879\}\).

It is often noted that each term in the sequence, from the third onwards (because \(p, 2p + 1, 4p + 3, 8p + 7, 16p + 15, . . .\)), is described as being of the form \(4k + 3\), where \(k\) is a counting number \(k =  1, 2,  3, . . . k\).

Computer searches are being conducted for the longest Cunningham chains.

“Well, sir, if I were you, I wouldn’t start from here.”

Let us look at the numbers in a Cunningham Chain in another way by group theory (cyclic permutations). The prime numbers in base \(10\) are of the form
\(10k + 1\\
10k + 3\\
10k + 7\\
10k + 9\),

where \(k = 1, 2, 3, . . . k\).

OldTrout, Going Postal
Allan Joseph Champneys Cunningham

We go back and apply Germain’s rule, start with \(10k + 1\), which is prime

\(10k + 1 : 10k + 1 + 10k + 1 + 1 = 10l + 3\), assume it is prime

\(10l + 3 : 10l + 3 + 10l + 3 + 1 = 10m + 7\), assume it is prime

\(10m + 7 : 10m + 7 + 10m + 7 + 1 = 10n + 5\), which is never prime because \(5\) divides it. Stop!

If we were to apply the rule to \(10n + 5\), we would have a number of the form \(10k + 1\) and would cycle through these numbers but we would never find a long Cunningham Chain.  (where \(k, l, m, n = 1, 2, 3, . . . k, l, m, n\)). For example \(\{41, 83, 167\}\).

Now, start with \(10k + 9\), which is prime

\(10k + 9 : 10k + 9 + 10k + 9 + 1 = 10l + 9\) which might be prime . . . we have a fixed point to cycle.

“If I were you, sir, I would always begin at a prime number that ended with a \(\,9\).”

A Cunningham Chain of length seven begins at \(1, 122, 659\).

Note : There are Cunningham Chains (of the second kind) where \(\,p : 2p\, – 1 = q\).  By a similar argument the longer chains have prime numbers all ending in a \(1\).
 

© OldTrout 2016