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