Editing Cunningham chain (section)

== Congruences of Cunningham chains ==

Let the [[parity (mathematics)|odd]] prime <math>p_1</math> be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus <math>p_1 \equiv 1 \pmod{2}</math>. Since each successive prime in the chain is <math>p_{i+1} = 2p_i + 1</math> it follows that <math>p_i \equiv 2^i - 1 \pmod{2^i}</math>. Thus, <math>p_2 \equiv 3 \pmod{4}</math>, <math>p_3 \equiv 7 \pmod{8}</math>, 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 base "shifts" the digits to the left; e.g. in decimal we have 314&thinsp;×&thinsp;10 = 3140.) When we consider &nbsp;<math>p_{i+1} = 2p_i + 1</math> in base 2, we see that, by multiplying &nbsp;<math>p_i</math> by 2, the least significant digit of &nbsp;<math>p_i</math> becomes the secondmost least significant digit of &nbsp;<math>p_{i+1}</math>. Because <math>p_i</math> is odd—that is, the least significant digit is 1 in base 2–we know that the secondmost least significant digit of &nbsp;<math>p_{i+1}</math> is also 1. And, finally, we can see that &nbsp;<math>p_{i+1}</math> will be odd due to the addition of 1 to <math>2p_i</math>. 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:

{| border="1" align="center" class="wikitable"
! Binary || Decimal
|- align="right"
| 1000011011010000000100111101 || 141361469
|- align="right"
| 10000110110100000001001111011 || 282722939
|- align="right"
| 100001101101000000010011110111 || 565445879
|- align="right"
| 1000011011010000000100111101111 || 1130891759
|- align="right"
| 10000110110100000001001111011111 || 2261783519
|- align="right"
| 100001101101000000010011110111111 || 4523567039
|}

A similar result holds for Cunningham chains of the second kind.  From the observation that <math>p_1 \equiv 1 \pmod{2}</math> and the relation <math>p_{i+1} = 2 p_i - 1</math> it follows that <math>p_i \equiv 1 \pmod{2^i}</math>.  In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each <math>i</math>, the number of zeros in the pattern for <math>p_{i+1}</math> is one more than the number of zeros for <math>p_i</math>.  As with Cunningham chains of the first kind, the bits left of the pattern shift left by one position with each successive prime.

Similarly, because <math> p_i = 2^{i-1}p_1 + (2^{i-1}-1) \, </math> it follows that <math>p_i \equiv 2^{i-1} - 1 \pmod{p_1}</math>. But, by [[Fermat's little theorem]], <math>2^{p_1-1} \equiv 1 \pmod{p_1}</math>, so <math>p_1</math> divides <math>p_{p_1}</math> (i.e. with <math> i = p_1 </math>). Thus, no Cunningham chain can be of infinite length.<ref>{{cite journal|last=Löh|first=Günter|title=Long chains of nearly doubled primes|journal=Mathematics of Computation|date=October 1989|volume=53|issue=188|pages=751–759|doi=10.1090/S0025-5718-1989-0979939-8|url=https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/|doi-access=free}}</ref>