Sophie Germain Primes and Cunningham Chains

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$.

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 $2020$