カニンガム鎖の合同性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 23:43 UTC 版)
「カニンガム鎖」の記事における「カニンガム鎖の合同性」の解説
奇素数 p 1 {\displaystyle p_{1}} を、ある第1種カニンガム鎖の初項とする。奇数なので p 1 ≡ 1 ( mod 2 ) {\displaystyle p_{1}\equiv 1{\pmod {2}}} である。後続の各素数は p i + 1 = 2 p i + 1 {\displaystyle p_{i+1}=2p_{i}+1} より p i ≡ 2 i − 1 ( mod 2 i ) {\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}} となる。よって p 2 ≡ 3 ( mod 4 ) {\displaystyle p_{2}\equiv 3{\pmod {4}}} , p 3 ≡ 7 ( mod 8 ) {\displaystyle p_{3}\equiv 7{\pmod {8}}} , と続く。 この性質は二進法で表記すると簡単に見てとれる（位取り記数法の底が何であっても、底をかけると数字列が左に1桁シフトする）。 p i + 1 = 2 p i + 1 {\displaystyle p_{i+1}=2p_{i}+1} を底2で考えると、2を掛けることで p i {\displaystyle p_{i}} の最下位桁は p i + 1 {\displaystyle p_{i+1}} の最下位から2番目の桁に移り、また p i + 1 {\displaystyle p_{i+1}} は奇数なので最下位桁はやはり1である。このように二進法では本質的に、カニンガム鎖の各項は1桁の左シフトと最下位桁への"1"の挿入で得られる。例えば141361469から始まる長さ6のカニンガム鎖の場合は次のようになる: 二進法十進法1000011011010000000100111101 141361469 10000110110100000001001111011 282722939 100001101101000000010011110111 565445879 1000011011010000000100111101111 1130891759 10000110110100000001001111011111 2261783519 100001101101000000010011110111111 4523567039 同様のことが第2種カニンガム鎖についても成り立つ。 p 1 ≡ 1 ( mod 2 ) {\displaystyle p_{1}\equiv 1{\pmod {2}}} と p i + 1 = 2 p i − 1 {\displaystyle p_{i+1}=2p_{i}-1} から、 p i ≡ 1 ( mod 2 i ) {\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}} がわかる。二進法では、第2種カニンガム鎖の各項の末尾は "0...01" となる。ここで各 i {\displaystyle i} に対し、 p i + 1 {\displaystyle p_{i+1}} の末尾で0が連続する個数は p i {\displaystyle p_{i}} のものより1だけ多い。第1種カニンガム鎖と同じく、この末尾の左側の部分は項が進むにつれて1桁ずつ左にシフトしていく。 第1種カニンガム鎖では p i = 2 i − 1 p 1 + ( 2 i − 1 − 1 ) {\displaystyle p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,} なので p i ≡ 2 i − 1 − 1 ( mod p 1 ) {\displaystyle p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}} である。ここでフェルマーの小定理より 2 p 1 − 1 ≡ 1 ( mod p 1 ) {\displaystyle 2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}} だから、 p 1 {\displaystyle p_{1}} は p p 1 {\displaystyle p_{p_{1}}} を割り切る（ i = p 1 {\displaystyle i=p_{1}} とおく）。これより、無限の長さのカニンガム鎖は存在しない。
※この「カニンガム鎖の合同性」の解説は、「カニンガム鎖」の解説の一部です。
「カニンガム鎖の合同性」を含む「カニンガム鎖」の記事については、「カニンガム鎖」の概要を参照ください。
- カニンガム鎖の合同性のページへのリンク
