Cunningham Chain - Congruences of Cunningham Chains

Congruences of Cunningham Chains

Let the odd prime be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus . Since each successive prime in the chain is it follows that . Thus, and so forth.

The above property can be informally observed by considering the primes of a chain in base 2. (Note that, as with all bases, multiplying by the number of the base "shifts" the digits to the left.) When we consider in base 2, we see that, by multiplying by 2, the least significant digit of becomes the secondmost least significant digit of . Because is odd--that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of is also 1. And, finally, we can see that will be odd due to the addition of 1 to . In this way, successive primes in a Cunningham chain are essentially shifted left in binary with ones filling in the least significant digits. For example, here is a complete length 6 chain which starts at 141361469:

Binary Decimal
1000011011010000000100111101 141361469
10000110110100000001001111011 282722939
100001101101000000010011110111 565445879
1000011011010000000100111101111 1130891759
10000110110100000001001111011111 2261783519
100001101101000000010011110111111 4523567039

A similar result holds for Cunningham chains of the second kind. From the observation that and the relation it follows that . In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each, the number of zeros in the pattern for is one more than the number of zeros for . As with Cunningham chains of the first kind, the bits left of the pattern shift left by one position with each successive prime.

Read more about this topic:  Cunningham Chain

Famous quotes containing the words chains and/or cunningham:

    While over Alabama earth
    These words are gently spoken:
    Serve—and hate will die unborn.
    Love—and chains are broken.
    Langston Hughes (20th century)

    Like an old brandy after a long rain,
    Distinguished, and familiar, and aloof.
    —James Vincent Cunningham (1911–1985)