コラッツ予想がとけたらいいな2

自分の考察を書いていきます。

レピュニット素数の厳密な判定

レピュニット (Repunit) とは全ての桁が 1である自然数のことである。つまり 1, 11, 111, 1111,...である。 Rn = (10^n - 1) / 9 の形に表される。repeated unitを省略したものが名前の由来である。

レピュニット - Wikipedia

ソロベイ-シュトラッセン素数判定法は、Robert M. Solovay(英語版)とVolker Strassen(英語版)によって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。

ソロベイ–シュトラッセン素数判定法 - Wikipedia

本稿でレピュニットとは、Rnでnが5以上の素数を指すものとします。

底11で判定します。
ソロベイ-シュトラッセン素数判定法の右辺のヤコビ記号(11/Rn)は、

(11/Rn) = -(Rn/11) = -(1/11) = -1

になります。

合成数について、11^(Rn-1)/2≡-1 mod Rnになるとして、矛盾を導きます。

例として、R5=11111=41*271をとります。

 11^5555 = -1 + 11111a         (1)
 11^5555 = x + 41b            (2)
(1)を2乗して41でmodをとる
 11^11110 ≡ 1 mod 41           (3)
(1)*(2)で41でmodをとる
 11^11110 ≡ -x mod 41           (4)
(3)と(4)から、x=-1
これは、Rnの全ての素因数で成り立ちます。

Rnの素因数pで、ヤコビ記号(11/p)=1になるものがあれば、11^a mod pが-1になることはないので(あやしい)、矛盾します。

Rnの全ての素因数で(11/p)=-1の場合は、p=4p'+1となるものを選びます。
(Rn=4a+3だから、そういうpは必ず存在する)

 11^(p-1)/2 ≡ -1 mod p
 11^(p-1)/2*2 ≡ +1 mod p
 11^(p-1)/2*3 ≡ -1 mod p
……

よって、

 (p-1)/2*(2α+1) = (Rn-1)/2

p=4p'+1なので、左辺は偶数、右辺は奇数なので矛盾します。

よって、合成数について、11^(Rn-1)/2 ≡ -1 mod Rnは成り立ちません。

まとめると、

Rnに対して、ソロベイ–シュトラッセン素数判定法を底11でおこなう。
11^(Rn-1)/2≡-1 mod Rnであれば、Rnは素数である。
それ以外の値であれば、Rnは合成数である。

ということが言えると思います。