メモ(数論12): Unlucky Seven

チラ裏 > 数論 i > メモ12

「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。誤字脱字・間違いがあるかもしれません。

***

2022-12-31 アンラッキー・セブン 2, 4, 8, 16, 32…の不思議

#数論 #ジグモンディの定理

2 を次々と倍々にした数 2, 4, 8, 16, 32, … に、それぞれ 1 を足してみます。
  3, 5, 9, 17, 33, …
この一つ一つの数は、どんな数で割り切れるでしょうか?

3, 5, 17素数(1 と自分自身でしか割り切れない数)。9 は 3 で(2回)割り切れます。33 は 3 と 11 で割り切れます。

64, 128, … など、もうちょっと先まで同様のことを考えてみると――

2n + 1 の約数たち
n2n2n + 1約数に分解
1 2 3 (3)
2 4 5 (5)
3 8 9 3 × 3
4 16 17 (17)
5 32 33 3 × (11)
6 64 65 5 × (13)
7 128 129 3 × (43)
8 256 257 (257)
9 512 513 3 × 3 × 3 × (19)
10 1024 1025 5 × 5 × (41)
11 2048 2049 3 × (683)
12 4096 4097 17 × (241)
13 8192 8193 3 × (2731)
14 16384 16385 5 × (29) × (113)
15 32768 32769 3 × 3 × 11 × (331)
16 65536 65537 (65537)

約数への分解は、素数の積の形で書いてあります。素数の約数(素因数)が2個以上あるとき、それらをいくつか掛け合わせたものも、約数: 例えば n = 9 の 513 = 3 × 3 × 3 × 19 は、もちろん 3 × 19 = 57 や 3 × 3 × 19 = 171 などでも割り切れる…。それはいいとして、丸かっこを付けてある素因数 (3), (5), (17), (11), …などは「新出素数」――つまり、表のもっと前の部分にはなかった素因数。例えば n = 6 の 5 × (13) でいうと、5 は n = 2 のとき既出なので丸かっこが付かず、(13) は既出でないので丸かっこ付き。n = 14 の場合、新出素数が2個あります!

この表をしばらく眺めていると、素朴な疑問として、全部の素数がどこかで新出するのだろうか? 3, 5, 11, 13, 17, 19 などがあるので、2 は別にして、全部の素数がどこかにありそうな気もしますが、素数 7 が見当たりません。もっと先まで表を作ると、そのうち 7 も出現するのでしょうか?

実は 7 は、どんなに n を大きくしても永遠に 2n + 1 の約数になることができない不運な素数(?)なのです。これ自体は、ちょっと考えると簡単に分かることなのですが(詳しくは次回以降)、興味をそそられますよね。他にも、同様の「不運な素数」があるのだろうか。ある素数が「不運」かどうか、事前に予言する方法はあるのだろうか?

さらに、この表をじっくり眺めていると、丸かっこ内の素数(=新出素数)は、どれも新出時点の n の倍数より 1 大きい。例えば (11) は n = 5 で新出し、5 の倍数プラス1。(43) は n = 7 で新出し、7 の倍数プラス1。丸かっこ内の数を対応する n で割ると、必ず 1 余る! これは、どういう現象なのでしょうか?

他にも、より深い問題として、なぜ n = 3 のときだけ新出素数がないのか? これは Zsigmondy(ジグモンディ)の定理という、あまり聞いたこともないような定理の、特別な場合に対応する現象なのです…。

2, 4, 8, 16, 32, … なんていう平凡な数列でも、それに1プラスするだけで、面白いことがいっぱいあるものですね! (下に続く)

⁂

2023-01-02 アンラッキー・セブン② 幸運と不運の分かれ目

#数論

2, 4 = 2 × 2, 8 = 2 × 2 × 2, 16 = 2 × 2 × 2 × 2, …は「2 だけ」を掛け合わせた数なので、3 では割り切れない。より詳しく言うと、2 は 3 の倍数より 1 小さい(この場合の「3 の倍数」とは「3 の 1 倍」つまり 3 自身)。このことを次のような記号で表す:
  2 ≡ −1 (mod 3)
一方、4 は 3 の倍数より 1 大きい。8 は 3 の倍数より 1 小さく、16 は 3 の倍数より 1 大きい。記号的には、それぞれこうなる:
  4 ≡ 1 (mod 3), 8 ≡ −1 (mod 3), 16 ≡ 1 (mod 3)

これについては、最初の…
  2 ≡ −1 (mod 3)
…の両辺を2乗・3乗・4乗したと考えると、見通しがいい。例えば:
  4 ≡ 1 (mod 3) は 22 ≡ (−1)2 (mod 3) と同じこと(☆)
  8 ≡ −1 (mod 3) は 23 ≡ (−1)3 (mod 3) と同じこと

ところで本題とは全然関係ないが、(☆)は「マイナスかけるマイナスがプラスになることの証明」といえなくもない…。22 ≡ (−1)2 が 4 ≡ 1 と同じ意味であるからには、(−1)2 = (−1) × (−1) が +1 と同じ意味にならねばならず、事実 4 は 3 の倍数プラス 1 である!

【1】 より一般的に、−1 の偶数乗は +1、奇数乗は −1 なので、2 の偶数乗は 3 の倍数より 1 大きく、2 の奇数乗は 3 の倍数より 1 小さい(ここで偶数・奇数というのは、正の偶数・奇数のこと)。すなわち:
  n は偶数 ⇔ 2n ≡ 1 (mod 3)
  n は奇数 ⇔ 2n ≡ −1 (mod 3)
この2種類の式の両辺に 1 を足すと:
  n は偶数 ⇔ 2n + 1 ≡ 2 (mod 3)
  n は奇数 ⇔ 2n + 1 ≡ 0 (mod 3)
前者は「3 で割ると 2 余る」という意味を持ち、後者は「3 で割ると 0 余る」つまり「3 で割り切れる」という意味。

結局、2, 4, 8, 16, 32, … にそれぞれ 1 を足したもの――
  3, 5, 9, 17, 33, …
――要するに、第n項が 2n + 1 である数列において、奇数番目の項は 3 で割り切れ、偶数番目の項は 3 で割り切れない(3 で割ると 2 余る…言い換えると、3 の倍数より 1 小さい)。よって、この数列の各項を素因数分解した場合、3 は第1項で新出素数となり、第3項・第5項・第7項…で既出素数となる。

2n + 1 の素因数: 3 の出現位置
n2n2n + 1素因数分解
1 2 3 (3)
2 4 5 (5)
3 8 9 3 × 3
4 16 17 (17)
5 32 33 3 × (11)
6 64 65 5 × (13)
7 128 129 3 × (43)

【2】 第3項の素因数において、3 が二重に出現する理由は今のところ不透明だが、とにかくどの奇数項でも、素因数 3 が必ず一つは存在しなければならない。この単純な考察は、3 以外の素因数にも適用できる。例えば 2, 4, 8, 16; 32, 64, 128, 256; … を 5 で割った余りは 2, 4, 3, 1; 2, 4, 3, 1; … であり、周期4で同じ余りがループしている:
  n = 1 のとき 2n ≡ 2 (mod 5)
  n = 2 のとき 2n ≡ 4 (mod 5) 言い換えれば 2n ≡ −1 (mod 5)
  n = 3 のとき 2n ≡ 3 (mod 5) 言い換えれば 2n ≡ −2 (mod 5)
  n = 4 のとき 2n ≡ 1 (mod 5)
  n = 5 のとき 2n ≡ 2 (mod 5)
  n = 6 のとき 2n ≡ 4 (mod 5) 言い換えれば 2n ≡ −1 (mod 5)
  n = 7 のとき 2n ≡ 3 (mod 5) 言い換えれば 2n ≡ −2 (mod 5)
  n = 8 のとき 2n ≡ 1 (mod 5)
  ………

2n + 1 が素因数 5 を持つこと、つまり 2n + 1 が 5 で割り切れるということは、
  2n + 1 ≡ 0 (mod 5) 両辺から 1 を引けば 2n ≡ −1 (mod 5)
ということなので、上記の観察から、n = 2 のとき 5 が新出素数となること、その後、4項ごとに(第6項・第10項・第14項などで) 5 が既出素数となることが予想される。事実、例えば 210 = 1024 に 1 を足せば 5 の倍数になる!

〔参考〕 2 の累乗は偶数なので、最下位桁は偶数。従って、mod 5 で 2, 4, 5, 1 のループは、mod 10 で 2, 4, 8, 6 のループとなる。実際:
  2, 4, 8, 16; 32, 64, 128, 256; 512, 1024, 2048, 4096; …

【3】 じゃあ一体なぜ、素数 7 には同様の議論が通用しないのか(どこまで行っても 7 が新出素数にならないのか)? 素数 11 や 13 や 17 などはどこかで出現するのに(前回参照)、なんで 7 は駄目なの?

2n + 1 が素因数 7 を持つこと、つまり 2n + 1 が 7 で割り切れるということは、
  2n + 1 ≡ 0 (mod 7) 両辺から 1 を引けば 2n ≡ −1 (mod 7)
ということなので、それが不可能という現象については、次のように要約できる:
  2, 4, 8, 16, 32, … は、どこまで行っても 7 の倍数より 1 小さくなることはない
実際 2, 4, 8, 16, 32, 64, … をそれぞれ 7 で割った余りを調べてみると 2, 4, 1; 2, 4, 1; … という周期3のループになって、余り 6 にはならない。

そもそも「余りがループする」というのは、どういう現象なのだろうか。確かに数値的観察では「余りがループする」ようだけど、ものすご~い先の例えば第1万項くらいで、突然気まぐれに余りが 6 になったりしないのだろうか…?

その点を解明する必要があるのだが、とりあえず今回の考察からだけでも、次の重要な結論が得られる。

「第n項が 2n + 1 の数列」の各項の素因数を考えたとき、素数 p の出現位置では、次が成り立つ:
  2n ≡ −1 (mod p)
この条件を満たす n が一つ以上あるとして、そのうち最小の n において p は新出する。

一般論として、もし p で割った余りがループするのなら(事実ループするのだが)、一度でも出現した素因数は――何らかの周期でループするのだから、その一定の周期で――無限回、出現する。つまり上記の「一つ以上あるとして」というのは控えめな表現で、実際には、あるのなら無限個ある。無限回の出番がある「幸運な素数」と、一度も出番のない「不運な素数」の分かれ目は、上記の条件を満たす n の有無。

次回は、この「余りのループ」について研究してみたい――Fermat の小定理に関連する現象だが、Fermat の小定理を使わない証明も可能かもしれない。

実は、素数の新出位置には、かなり強い制約がある。前回の表を詳しく観察すると、「p が n において新出するなら、n は p − 1 の約数」ということが予想される。しかも、どんな約数でもいいわけではなく、p − 1 の2分の1、または4分の1、または6分の1…など「偶数分の1」であることが必要。従って、p = 7 が新出するチャンスがあったとしたら、唯一 n = 3 においてだった(p − 1 = 6 の「偶数分の1」の形の約数は、それしかない)。p = 7 がこの唯一のチャンスを生かせなかったのは「たまたま不運」だったのだろうか。それとも、何か理由があるのだろうか?

⁂

2023-01-04 アンラッキー・セブン③ 2は1の4乗根!?

#数論

ある数の4乗根とは、4乗するとその数になる値。例えば 3 を 4 乗すると…
  34 = 3 × 3 × 3 × 3 = (3 × 3) × (3 × 3) = 9 × 9 = 81
…なので 3 は 81 の4乗根。同様に 24 = 16 なので、2 は 16 の4乗根。

パラレルワールドの一つ mod 5 の世界では、「5 で割った余りが同じなら同じ値」と見なされるので、16 と 11 と 6 と 1 などは「同じ」(合同):
  16 ≡ 11 ≡ 6 ≡ 1 (mod 5)
だから 24 ≡ 1 (mod 5) であり、2 は 1 の4乗根となる!

驚くべきことに 3 以上のどんな奇数 a を考えても、パラレルワールド mod a では、2 は 1 の何乗根かになっている。例えば…
  a = 3 のとき 22 = 4 ≡ 1 (mod 3) つまり 2 は 1 の2乗根
   ↑ 4 を 3 で割ると 1 余る
  a = 5 のとき 24 = 16 ≡ 1 (mod 5) つまり 2 は 1 の4乗根
   ↑ 16 を 5 で割ると 1 余る
  a = 7 のとき 23 = 8 ≡ 1 (mod 7) つまり 2 は 1 の3乗根
   ↑ 8 を 7 で割ると 1 余る
  a = 9 のとき 26 = 64 ≡ 1 (mod 9) つまり 2 は 1 の6乗根
   ↑ 64 を 9 で割ると 1 余る
  a = 11 のとき 210 = 1024 ≡ 1 (mod 11) つまり 2 は 1 の10乗根
   ↑ 93 × 11 = 930 + 93 = 1023 は11の倍数なので、1024 を 11 で割ると 1 余る
  a = 13 のとき 212 = 4096 ≡ 1 (mod 13) つまり 2 は 1 の12乗根
   ↑ 315 × 13 = 3150 + 945 = 4095 は13の倍数なので、4096 を 13 で割ると 1 余る

この一つ一つの観察は、別々のパラレルワールド内のことだが、それにしても mod 3, mod 5, mod 7, mod 9 などのどの世界でも、同様の現象が起きている。これは「フェルマーの小定理」の一般化と関係あるのだが、以下では、もっと単純な発想で、このミステリーを解明してみたい。

【1】 例えば 5 で割った余りは 0, 1, 2, 3, 4 の5種類しかない。一方、2 を倍々にした数(2, 4, 8, 16, 32, 64, …)は、無限に考えられる。ということは 2, 4, 8, 16, 32, 64, … の一つ一つを 5 で割ると(割られる数は無限に続くけど、余りは5種類しかないんだから)、どこかで同じ種類の余りが出る。だって、仮に5番目までの数が全部異なる種類の余り(0, 1, 2, 3, 4 のどれか)を持つとしても、6番目の数は、もはや違う種類の余りを持つことはできない――遅くとも5番目までには、全種類の余りが出尽くしてしまうから。

だから 1 から 6 の範囲の、何らかの2種類の整数 ○ と △ について、2 と 2 は、5 で割ったとき同じ余りを持つ。この相異なる2種類の整数 ○ と △ のうち、大きい方を x、小さい方を y とでもすると:
  2x ≡ 2y (mod 5) ただし x は y より大きい
この両辺を 2y で割ると:
  2x/2y ≡ 2y/2y (mod 5) つまり 2x−y ≡ 1 (mod 5)  ※注1
x は y より大きい整数なので x − y = ℓ は自然数になって:
  2 ≡ 1 (mod 5)
ℓ がいくつかはともかく、mod 5 の世界で 2 が 1 の ℓ 乗根になるのは必然といえる。具体的な数値としては 25 = 32 と 21 = 2 は、どちらも 5 で割ると 2 余るので、x = 5, y = 1 となって ℓ = 5 − 1 = 4。つまり、この世界では 2 は 1 の4乗根となる(最初に観察した通り)。

※注1  2x/2y = 2x−y になる理由: 「x 個の 2 の積」が分子、「y 個の 2 の積」が分母なので(そして x の方が大きいので)、約分すると、分子にある 2 が y 個消え、分母は 1 になる; 結局、約分の結果は「x−y 個の 2 の積」。…やってることは普通の整数の計算と同じだが、正確に言うと、これは「パラレルワールドの割り算」。2yと mod の数 5 が互いに素であることから、2y で自由に割り算できるのだ。

【2】 「5 で割った余りは 0, 1, 2, 3, 4 の5種類」といっても、よく考えてみると 2, 4, 8, 16, 32, … が 5 で割り切れること(余りが 0 になること)はあり得ないので、この場合、実際には「発生する可能性のある余り」は 1, 2, 3, 4 の4種類しかない。だから、どんなに遅くとも 2, 4, 8, 16, 32, … の4番目の数までで、可能性のある全種類の余りは出尽くしてしまい、5番目の数では既出の余りが再出現する。事実「1番目の数 2 と5番目の数 32 は、どちらも 5 で割ると 2 余る」。

同様に考えると、2, 4, 8, 16, 32, 64, … を 7 で割った余りは、可能性として1~6の6種類しかなく、遅くとも7番目の数までには、同じ余りが2回以上出るはず。この場合、実際には7番目まで行くまでもなく、4番目の 16 が、1番目の 2 と同じ余りを持つ(どちらも 7 で割ると余り 2)。【1】と同様に表現すると…
  x = 4, y = 1 に対して 2x ≡ 2y (mod 7)
  従って 2x−y = 23 ≡ 1 (mod 7)
…となり、mod 7 では、2 は 1 の3乗根となる(最初に観察した通り)。この場合、理論上の可能性として余りは最大6種類あるものの、実際には、3種類の余りしか出現しない。2, 4, 8, 16, 32, 64, … を 7 で割った余りは、2, 4, 1, 2, 4, 1, … となっている。

より一般的に、2, 4, 8, 16, 32, … を3以上の奇数 a で割った余りは、a−1 種類の選択肢しかないので、遅くとも a 番目の項までには同じ余りがリピート。それについて上記と同様の分析をすると、mod a の世界では、「1 は 2 の ℓ 乗根」となる(ℓ の具体的な値は a によって異なる)。要するに、
  2 ≡ 1 (mod a)  ‥‥《あ》
が成り立つ。言葉で言えば 2 を ℓ 乗すると ≡ 1 になる

【3】 2, 4, 8, 16, 32, … を a で割った余りは、mod a では 2, 4, 8, 16, 32, … 自身と「同じ」であり、次々と 2 倍になっていく。例えば:
  2 ≡ 2 (mod 7), 4 ≡ 4 (mod 7), 8 ≡ 1 (mod 7), 16 ≡ 2 (mod 7), …
だから 2 を ℓ 乗すると ≡ 1 になるということは(上記の例では ℓ = 3)、「その次の数」は ≡ 2 に戻る(1番目の余りと同じ)ということであり、従って「そのまた次の数」は ≡ 4 ということであり(2番目の余りと同じ)、以下同様にループする。そして 2ℓ 乗すれば再び ≡ 1 になって、無限に同じことが繰り返される。というのも:
  《あ》の両辺を 2 乗すれば (2)2 ≡ 12 つまり 22ℓ ≡ 1 (mod a)
  《あ》の両辺を 3 乗すれば (2)3 ≡ 13 つまり 23ℓ ≡ 1 (mod a)
  《あ》の両辺を 4 乗すれば (2)4 ≡ 14 つまり 24ℓ ≡ 1 (mod a)
  ………

以上のことから 2, 4, 8, 16, 32, … を奇数 a で割った余りは、周期 ℓ でループする。これが前回観察した「余りのループ」の正体。このことは 2, 4, 8, 16, 32, … の各数に 1 を足した数列――
  3, 5, 9, 17, 33, …
――の各項がどんな素因数を持つか?という最初の疑問(新出素数)にも、重大な影響を及ぼす。

けれど、奇数 a とそれに対応する周期 ℓ は、一体どういう関係にあるのだろうか?

周期 ℓ は最大でも、「可能性のある全種類の余り」が出尽くす a−1 であり、mod 7 の場合のように a−1 より小さいこともある。今回の観察からだけでも、それは分かる。a が小さい場合には、21, 22, 23, … を一つずつ a で割ってみれば、どこかで余りが 1 になるのだから、実用上、一つずつ試すことで ℓ を確定できるだろう。でも例えば a = 123 のように少し数が大きくなった場合、この考え方だと、ℓ を決定するのに最悪100回以上も試行錯誤の割り算を繰り返す必要がある…。計算の手間についてはとりあえず無視するとしても、「1 から a−1 のどれかの数」というのでは、あまりにも漠然としていて、見通しが悪い。ここはやはりフェルマーの小定理や、その一般化を考えるのが得策のようだ…。(続く)

⁂

2023-01-08 オイラーの定理 もしも週が8日だったら

#数論

小学生のフェルマーの小定理」の別バージョン。簡単な算数だけで「オイラーの定理」。アホくさい(けど分かりやすい?)アプローチをお楽しみください。

【1】 「1週間が8種類の曜日から成る異世界」を考える。8種類の曜日を順に「1曜日」「2曜日」…「8曜日」と呼ぶことにして、話を簡単にするため、毎月の「1日」は「1曜日」に固定されているとする(そして月の日数は無限にあるとしよう)。「8曜日」である8日の翌日の9日は、「1曜日」に戻る。そのまた翌日の10日は「2曜日」。そして例えば(その5日後の)15日は「7曜日」…。一般に「D日」は、D が8の倍数なら「8曜日」で、そうでなければ D を8で割った余りを R として「R曜日」となる。

この架空のカレンダーにおいて、第一週の「奇数曜日」は、もちろん次の 4 種類の日付:
  S = {1, 3, 5, 7}
これらの各日付を奇数倍すると、再び 4 種類の「奇数曜日」の日付になる。例えば、3倍したものをこう書くことにする:
  3S = {3, 9, 15, 21}  ← S の4個の日付をそれぞれ3倍した
これらの新しい4種類の日付のうち(「3曜日」の3日は新しくないが)、9日は「1曜日」、15日は「7曜日」、21日は「5曜日」なので、3S は、S と同じく、4種類の「奇数曜日」を過不足なく1回ずつ含む。同様に:
  5S = {5, 15, 25, 35}
は左から順に「5曜日」「7曜日」「1曜日」「3曜日」なので、4種類の「奇数曜日」を1回ずつ含み、
  7S = {7, 21, 35, 49}
は左から順に「7曜日」「5曜日」「3曜日」「1曜日」なので、やはり4種類の「奇数曜日」を1回ずつ含む。

【2】 より一般的に、1週間が w 種類の曜日から成るとして、全種類の曜日(すなわち「1曜日」から「w曜日」)のうち、曜日の番号と w が2以上の公約数を持たない場合を「素敵な曜日」と呼ぶことにする。例えば w = 6 の場合(1週間が6日)、素敵な曜日は「1曜日」と「5曜日」の2個しかない――「2曜日」「4曜日」「6曜日」は、「2」「4」「6」が w = 6 と公約数2を持つので素敵でなく、「3曜日」「6曜日」は、「3」「6」が w = 6 と公約数3を持つので素敵でない(「6曜日」は二重の意味で、素敵でない)。

w = 7 の場合、「7曜日」以外は全部素敵(w が変わったので「6曜日」は素敵になった)。w = 8 の場合(【1】参照)、奇数曜日が素敵。w = 9 の場合、「3曜日」「6曜日」「9曜日」は素敵でないが、それ以外の6種類の曜日は素敵。w = 10 の場合「1曜日」「3曜日」「7曜日」「9曜日」の4種類が素敵。w = 11 の場合、「11曜日」以外の10種類が全部素敵。

「素敵な曜日」の日付を「素敵な日付」「素敵な数」と呼ぶことにしよう。実は、第一週の「全種類の素敵な日付」に「素敵な数」を掛けた日付は、再び「全種類の素敵な日付」になる。例えば w = 8 の場合、第一週の奇数曜日
  S = {1, 3, 5, 7}
が「素敵」であり、1, 3, 5, 7 という日付の数字自身は「素敵な数」に当たる。そして 3S も 5S も 7SS と全く同じ曜日の集合であることは【1】の通り。別の例として w = 6 の場合、第一週の素敵な日付は:
  S = {1, 5}
これらの日付に、素敵な数 5 を掛けると:
  5S = {5, 25}
5日は「5曜日」、25日は(週が6日のこの世界では)「1曜日」なので、曜日の観点では、この 5S もやはり S と同じであることが分かる。

この性質は――少々意味不明なように思えるかもしれないが――オイラーの定理を証明するための鍵となる。

〔付記〕 実は「素敵な数」というコンセプトは「逆数を持つ数」という意味を持ち、「素敵な数」だけを考えることは「掛け算・割り算が自由にできる世界」を構築することに当たる(付録参照)。

「素敵な曜日」の定理 1 以上の任意の整数 w を選んで、固定する。その w に対して、第一週の全種類の素敵な日付を集めたもの――
  S = {d1, d2, …, de}  ここで e は第一週に含まれる素敵な曜日の数
――を(その w についての)オイラー集合と呼ぶことにしよう。オイラー集合の各要素に、任意の素敵な数 a を掛けた結果の e 種類の日付――
  aS = {ad1, ad2, …, ade}
――は、S と同じく、全種類の素敵な曜日を過不足なく1個ずつ含む。

〔注意〕 「素敵」の定義は「w との間に 2 以上の公約数がない」。教科書用語で言えば「互いに素」ってやつ。言い換えると、素敵な数というのは、「w のどの素因数 p から見ても p の倍数ではない」ような数。「オイラー集合」というのは説明の便宜上の名前で、一般的な用語ではない。

証明 aS に含まれる e 個の日付は、どれも素敵。というのも、仮定によって a は素敵だし、d1, d2, … なども素敵なので、前者も後者も、w の素因数 p の倍数ではない。素数 p の倍数ではない数を掛け合わせても、もちろん p の倍数になるわけがなく、すなわち素敵な数と素敵な数の積は、素敵なまま。

これで「aS の日付は全部素敵」ってことは分かったが、問題は「これらの日付は、全部曜日が別々か」。もしも同じ曜日の日付が2個以上含まれていたら、aS には e 個しか日付がないんだから、e 種類の素敵な曜日を全部含むことは不可能で、定理が成り立たない。他方、aS の日付の曜日が全部異なるのなら、aS はちょうど e 種類の日付を含むのだから、e 種類の素敵な曜日をちょうど1個ずつ含むことになり、定理が証明される。…真相は後者であること(つまり、曜日の重複が起きないこと)を示そう。もし仮に、例えば ad1 と ad2 が同じ曜日だとすると:
  ad1 ≡ ad2 (mod w)  ‥‥《い》
――ここで
  左辺 ≡ 右辺 (mod w)
という記号の意味は「左辺を w で割った余りと、右辺を w で割った余りが等しい」(詳細)。

a と w は互いに素なので(つまり a は素敵なので)、《い》の両辺を a で割ることができて:
  d1 ≡ d2 (mod w)  ‥‥《う》
これは d1 と d2 が同じ曜日という意味だが、そんなことが起きるはずない(理由: オイラー集合 S は「第一週の」素敵な曜日の日付なので――そして週の全部の日付は曜日が違うので――、同じ曜日が2回以上含まれるわけない)。要するに「ad1 と ad2 が同じ曜日」という仮定《い》は、無理!

ad1 と ad2 に限らず、aS に含まれるどの2個の(相異なる)日付を選んでも、全く同様の議論が成り立つ: もしも《い》に当たる式が成り立つなら(つまり曜日の重複が起こるとしたら)、その両辺を a で割ると《う》の形になるが、その結論は無理なので、曜日の重複はあり得ない。□

【3】 このことから、次の重大な定理が成り立つ。

オイラーの定理 1 以上の任意の整数 w について、a を任意の素敵な数として、オイラー集合の要素の数を e とすると:
  ae ≡ 1 (mod w)

証明 「素敵な曜日」の定理によれば S に含まれる e 個の日付と aS に含まれる e 個の日付は、曜日が1対1対応。つまり次の e 個の式が成り立つ:
  d1 ≡ ad (mod w)  ← 最初の素敵な曜日
  d2 ≡ ad (mod w)  ← 2個目の素敵な曜日
  ………
  de ≡ ad (mod w)  ← 最後の(e個目の)素敵な曜日
ここで右辺の ○, △, …, □ は、具体的にどれがどれかはケースバイケースだが、とにかく全体としては 1, 2, …, e が過不足なく1回ずつ現れる(言い換えると aS の各要素 ad1, ad2, …, ade が1回ずつ右辺に登場)。上記 e 個の式の左辺同士・右辺同士を全部掛け合わせると:
  d1d2…de ≡ ae(d1d2…de) (mod w)
d1, d2, … などは全部素敵なので、それらの積 d1d2…de も素敵であり、上の式の両辺をこの数で割ることが許される。その結果は:
  1 ≡ ae (mod w)
すなわち、オイラーの定理が成立。□

〔例1〕 w = 8 のとき e = 4 だった(奇数曜日が素敵になるケース: 【1】【2】参照)。素敵な数(つまり w = 8 と互いに素な数)の例として a = 3 を選ぶと、オイラーの定理によって、
  ae ≡ 1 (mod w) すなわち 34 ≡ 1 (mod 8)
が予言される。これは 34 を 8 で割ると 1 余るという意味だが、34 = 81 は、まさにこの性質を持っている。予言が的中した!

〔例2〕 w = 9 のとき、オイラー集合は {1, 2, 4, 5, 7, 8} で e = 6。素敵な数の例として a = 2 を選ぶと、
  ae ≡ 1 (mod w) すなわち 26 ≡ 1 (mod 9)
が予言される。これは 26 = 64 を 9 で割ると 1 余るという意味だが、まさにそうなっている。

〔例3〕 w = 10 のとき、オイラー集合は {1, 3, 7, 9} で e = 4。素敵な数の例として a = 3 を選ぶと、
  ae ≡ 1 (mod w) すなわち 34 ≡ 1 (mod 10)
が予言される。これは 34 = 81 を 10 で割ると 1 余るという意味だが、まさにそうなっている。

【4】 オイラーの定理の特別の場合として、もし w が3以上の素数なら、素数の性質上 w の約数は 1 と w 自身だけなので、オイラー集合は
  {1, 2, …, w−1}
となる――要するに「w曜日」以外の全部の曜日が素敵。この場合 e = w−1 だから(理由: w 個の曜日の中で最後の 1 個を除いたものが素敵)、オイラーの定理はこうなる:
  aw−1 ≡ 1 (mod w)
これはフェルマーの小定理に他ならない。

つまり、オイラーの定理の証明によって、フェルマーの小定理も証明されたことになる。フェルマーの小定理では mod が素数に限られるが、オイラーの定理では、それが拡張され、任意の正の整数を mod とすることができる。オイラーの定理はフェルマーの小定理の上位バージョンで、有効範囲が広い!

正の整数 w を選べば、それに対応するオイラー集合のサイズ e が定まる。 w を入力として e を求めるこの計算(関数)は、オイラーのファイ関数と呼ばれ、e = φ(w) のように表記される。w が素数の場合に限れば、オイラーの定理は「フェルマーの小定理」と同じ意味になり、前述のように e = φ(w) = w−1 という簡単な計算が成り立つ。

この観点から見ると、mod p におけるフェルマーの小定理の指数 p−1 の正体は、p に対するオイラー集合の要素の数。

…というわけで、オイラーの定理の表面的意味を理解することは、別に難しくない。「オイラー集合のどの要素も e 乗すると ≡ 1 になる」というだけの話。そして e は「その集合の要素の数」という単純明快な意味を持つ。

〔例1〕 w = 6 のとき {1, 5} の 2 個が素敵(e = 2)。素敵な数を 2 乗すると ≡ 1 になる。つまり…
  12 = 1
  52 = 25
…のどちらの数も、w = 6 の倍数より 1 大きい。

〔例2〕 w = 7 のとき {1, 2, 3, 4, 5, 6} の 6 個が素敵(e = 6)。例1と同様に…
  16 = 1
  26 = 64
  36 = 729
  46 = 4096
  56 = 15625
  66 = 46656
…のどの数も、w = 7 の倍数より 1 大きい。

けれど「w が与えられたとき、どうやって e を決定するか」(オイラーのファイ関数の計算法)という問題が、残っている。それがはっきりしないことには、オイラーの定理を活用しにくい…。w が素数のときは上記のように 1 を引くだけで e が求まるが、w が素数以外の場合にどうすればいいのだろうか…。(続く)

*

【5】(付録) 君は群論が好きか? 群論って眠くなる…? まぁ、とりあえず必要もないけど、せっかくここまで来たんだ、ちょいと脱線して、オイラー集合がどんな「世界」なのか考えてみる。小難しい群論用語を使わず、同じ意味のことを普通の言葉で書くと…

オイラー集合は、単なる「要素の集まり」ではなく「その内部で自由に掛け算ができる」という性質を持つ。1週間の曜日の数 w ――言い換えれば mod の数――に対応するオイラー集合は、そのカレンダーの全種類の「素敵な数」の集まりで、しかも「素敵な数」と「素敵な数」の積は再び「素敵な数」なのだから、この性質は自然に理解可能だろう。例えば mod 10 での掛け算の表は次の通り(積が 10 を超えたら 10 で割った余りで置き換えている――結果的に、これらの積は、普通の掛け算の結果の最下位桁を取り出したものに当たる)。

〔解説〕 w = 10 の世界において、例えば「3曜日」になる日付(3 や 13 など)と「7曜日」になる日付(7 や 17 など)の積は、曜日の観点では「1曜日」の日付。この計算では(曜日さえ合ってれば)「その曜日の日付」としてどんな数を選んでも構わない。ざっくり言えば「3曜日」×「7曜日」=「1曜日」となる。なぜなら前者の日付は 10m+3 の形を持ち、後者の日付は 10n+7 の形を持つので、それらの積は次のように 10k+1 の形を持つ:
  (10m+3)(10n+7) = 100mn+70m+30n+21 = 10(10mn+7m+3n+2)+1
最後の丸かっこ内を k とすると、上記の数は 10k+1 に等しい。あるいはもっと単純に:
  3 × 7 ≡ 21 ≡ 1 (mod 10)

表からも一目瞭然だが、集合内でどのように掛け算をしても、結果は(曜日の観点では)再び集合内のどれかの要素に。さらに、この集合内には、どの要素に対しても逆数(掛けると積が 1 になる相手)がある。

「素敵な数」の積(mod 10)
×1379
11379
33917
77193
99731

逆数の存在(第一の証明) w がどんな正の整数であるにせよ、その w に対して「1曜日」は素敵(なぜなら 1 と w は「2 以上の公約数」を持たない)。だから、オイラー集合は必ず「1」を含む。つまり集合内には、必ず要素「1」がある。

ヘッダーを除く表の中身(白い部分)について、最初の行(横)を「第一週の素敵な曜日」の日付と解釈すると、既に観察したように、掛け算の結果として、全部の行は「素敵な曜日」を過不足なく一つずつ含む(上の例では「1曜日・3曜日・7曜日・9曜日」――それを例えば 3 倍した日付は、再び全種類の素敵な曜日になるのだった)。あるいは最初の列(縦)を「第一週の素敵な曜日」と解釈すれば、全く同じ理屈から、どの列も「素敵な曜日」を過不足なく一つずつ含む。結局、どの行も、どの列も、重複なく「1」を1回だけ含む。その結果、どの要素から見ても、掛け算の結果が「1」になる相手(自分自身の場合もあるが)――つまり逆数――が、ちょうど一つ存在する。□

逆数を掛けることを「割り算」と呼ぶなら、オイラー集合は掛け算・割り算が自由にできる世界といえる(集合内の任意の数 a で割り算したければ、a の逆数を掛け算すればいい)。

逆数の存在(第二の証明) 逆数の存在については、オイラーの定理そのものからも、証明できる。任意の正の整数 w に対して、オイラー集合の要素の数(素敵な曜日が全部で何種類あるか?)を e として、任意の素敵な数を a とすると:
  ae ≡ 1 (mod w)
…これがオイラーの定理だが、ae つまり「e 個の a を掛け合わせる」ということは、「e−1 個の a を掛け合わせて、さらにもう1回 a を掛けること」。つまり上の式をこう書くことができる:
  (ae−1)a ≡ 1 (mod w)
この式を解釈すると「任意の要素 a について、その a を (ae−1) 倍すれば ≡ 1 になる」。この ae−1 という数も、素敵な数(なぜなら、素敵な数 a を e−1 回掛け合わせたものなので)。だから(曜日の観点では)同じオイラー集合に属する。言い換えると…
  任意の a ∈ S の逆数は ae−1S
となる。□

〔例〕 w = 10 のとき e = 4。この世界で a = 7 の逆数は ae−1 = 73 = 343 ≡ 3 (mod 10)。月の343日と3日は、曜日の観点ではどちらも「3曜日」で等しい。等しいのだから、どちらを使っても構わない: 7 × 343 = 2401 ≡ 1 (mod 10) なので 343 は 7 の逆数だし、7 × 3 = 21 ≡ 1 (mod 10) なので 3 も 7 の逆数。343 と 3 は同一の曜日を指す別名に過ぎない。

逆数の存在(第三の証明・参考) 上記2種類の説明と比べると分かりにくいかもしれないが、次のような分析もできる。1回読んだだけでピンとくる話じゃないかもしれないけど、参考までに…

任意の素敵な数 a と、基準となる w は、互いに素(最大公約数が 1)。だから、次の式を満たす整数 x, y が存在する(Bachet–Bézout の定理):
  ax + wy = 1  ‥‥《え》
この式を mod w で考えると、左辺第2項にある w の倍数 wy は消滅して ax ≡ 1 (mod w) となる。つまり a の逆数 x が(具体的な値は分からないけど)存在。問題は、この謎の要素 x が同じオイラー集合に属しているかどうかだが、《え》で変数名を交換して旧 a と旧 x をそれぞれ x と a と呼ぶことにすると、式《え》が成り立つことから、a は――つまりもともとの x は―― w と互いに素(Bachet–Bézout の定理の逆)。だから、もともとの謎の要素 x も素敵な日付。従って、曜日の観点では、オイラー集合に属する(=この日付と曜日が同じ日付が、オイラー集合の要素の中にある)。□

この分析によると「逆数を持つこと」と「素敵であること」は本質的に同じ意味なので、「mod w のオイラー集合とは、mod w の要素のうち、逆数を持つやつだけを全部集めたもの」といえる。

*

脱線ついでに、mod 8 の「素敵な数」の掛け算も見ておこう(mod 10 と原理は同じで、この場合、普通に掛け算して積が 8 を超えたら 8 で割った余りに置き換えている)。

「素敵な数」の積(mod 8)
×1357
11357
33175
55713
77531

mod 10 と同様、4種類の素敵な数があり、既に証明したようにどの数も逆数を持つのだが、掛け算の構造が異なる! mod 8 のオイラー集合には、どの数も「自分自身が自分の逆数」(自分に自分を掛けると 1 になる)という奇妙な性質がある。mod 10 には、なかった性質だ…。

この性質は、かなりヤバイ。x2 ≡ 1 (mod 8) を解きたいとき、「2次方程式の解は2種類」という常識を当てにして x ≡ 1 or −1 つまり x ≡ 1 or 7 (mod 8) とやると…。本当は4個も解があるのに、解が2個しか求まらない。一体どうすればいいんだッ?!

ところで mod 10 の4種類の要素については、たった一つの要素「3」のべき(累乗)として表現可能: 31 ≡ 3, 32 ≡ 9, 33 ≡ 7, 34 ≡ 1 (mod 10)。一方 mod 8 では、上記のヤバイ性質のせいで、どの数からスタートしても2乗しただけで ≡ 1 になってしまい、従って3乗するともともとの数に戻ってしまうので、同様のことができない。「4種類の要素を持ち、掛け算・割り算が自由にできる世界」という点は同じでも、mod 8 と mod 10 のオイラー集合は内部構造が違う…ってことが分かる。

⁂

2023-01-12 アンラッキー・セブン④ あなたの勘では…?

#数論 #第二補充法則

フェルマー風の数列――
  A: 3, 5, 9, 17, 33, 65, 129, …
それは 2 が倍々となる次の数列の各項に 1 を足したもの。
  B: 2, 4, 8, 16, 32, 64, 128, …

A の偶数番目の項 5, 17, 65 = 5 × 13, 257, 1025 = 5 × 5 × 41, … を調べると、どの数も、そしてどの約数も、「4 の倍数より 1 大きい」という性質を持っているようだ。そういう目で、今度は A の奇数番目の項を眺めると:
  3, 9 = 3 × 3, 33 = 3 × 11, 129 = 3 × 43, 513 = 3 × 3 × 3 × 19, …
因数にやけに 3 が多いことはさておき、どの素因数も「4 の倍数より 1 小さい」ようだ(3, 11, 43, 19)。――偶数番目・奇数番目の項に関するこの観察。たまたま数列の最初の方がそうなってるだけなのだろうか。それとも、どこまで行っても、無限にこの性質が維持されるのか?

あなたの勘では…?

【1】 B の第2項以降は全部 4 の倍数なのだから、それに 1 を足した A の第2項以降が 4k+1 の形(k: 整数)を持つことは、当たり前。でも 4k+1 の形だからといって、それを徹底的に約数に分解したとき――(1 と自分自身以外に約数を持たない)素数にまで分解したとき――、その素数も 4k+1 型になるとは限らない。実際 A の第3項 9 = 3 × 3 や第5項 33 = 3 × 11 では、4k+1 型の数が 4k+3 型の素数の積に分解される。

ところが A の偶数番目の項に関する限り、どこまで行ってもその素因数は 4k+1 型に限られる。次の法則がその根拠。

第一補充法則 p を 3 以上の素数とする。このとき、もし p が 4k+1 型なら、x2 ≡ −1 (mod p) は(整数の)解を持つ。逆に、この式が解を持つのは p が 4k+1 型の場合に限られる。≡ −1 の意味は、下記の具体例参照。

A の第 n 項を An = 2n + 1 としよう。もし n が偶数 2m なら(m は 1 以上の整数)、こうなる。
  A2m = 22m + 1 = (2m)2 + 1
この数が 3 以上の素数 p で割り切れるとすると、それは p で割った余りが 0 という意味なので:
  (2m)2 + 1 ≡ 0 (mod p)  ‥‥《か》
両辺から 1 を引くと:
  (2m)2 ≡ −1 (mod p)  ‥‥《き》
言い換えると x2 ≡ −1 (mod p) には x = (2m) という解がある。だから、第一補充法則から p は 4k+1 型に限られる!

〔具体例〕 m = 3, n = 2m = 6 の場合、A6 = 26 + 1 = 65 は、素数 p = 13 で割り切れる(p = 5 でも割り切れるが、ここでは例として 13 を取り上げる)。このとき 2m = 23 = 8 なので、《か》に当たる式は:
  82 + 1 ≡ 0 (mod 13)
《き》に当たる式は:
  82 ≡ −1 (mod 13)
だから x2 ≡ −1 (mod 13) には、少なくとも一つの解 x = 8 がある。ここで ≡ −1 (mod 13) というのは「13 で割ると −1 余る」つまり「13 で割り切るには 1 不足している」=「13 の倍数より 1 小さい」と解釈可能(実際 64 は、13 の倍数 65 より 1 小さい)。あるいは、上の式の左辺の 82 つまり 64 と、右辺の −1 は「13 で割った余りが同じ」と解釈することもできる。64 を 13 で割れば、商が 4 で余りが 12。一方、−1 を 13 で割れば――「商が 0 で余りが −1」とも言えるけど、「13 で割った余りは 0~12 のどれかになる」という常識を守るとすれば――商が −1 で余りが 12。確かに、どっちも余り 12。…けど、そんなふうにいちいち考えんのも面倒なので、
  ○ ≡ △ (mod □)
の形については、○ と △ の差が □ の倍数、と解釈するのが一番シンプルかもしれない(フェルマーの小定理への道②参照)。
  82 ≡ −1 (mod 13)
の場合 82 − (−1) = 65 は、確かに 13 の倍数だ。

x2 ≡ a (mod p) を満たす解 x がある場合、a は p の平方剰余(へいほうじょうよ)と呼ばれる。解がなければ a は平方非剰余(略して非剰余)と呼ばれる。「平方剰余」は、普通の整数の世界での「平方数」(4, 9, 16, 25, … など)と同様の概念の、mod p バージョン。「非剰余」の方は「非平方数」(平方数でない数)に当たる。第一補充法則は −1 が平方剰余になるための、必要十分条件。例えば x2 = −1 (mod 7) は解を持たない(言い換えると −1 は 7 の非剰余。要するに、平方して 7 で割ったとき、余りが 6 になる整数は存在しない): 奇数の素数 7 は 4k+1 型じゃないから、必要条件を満たさないのだ…。

〔補足〕 普通の整数の世界で、例えば 49 は平方数(7 の平方)。一方、32 ≡ 9 ≡ 2 (mod 7) なので、2 は mod 7 の世界の「平方数」(3 の平方)に当たる(32 の 9 自身も、もちろん「平方数」だが、それと合同な 2 も「平方数」)。つまり 2 は mod 7 における平方剰余――それを略して「2 は 7 の平方剰余」という。これは「7 の平方が ≡ 2」という意味ではなく、「何かの平方が mod 7 の世界で ≡ 2」という意味。同様に「−1 は 7 の非剰余」というのは「−1 の平方は ≢ 7」という意味ではなく「何を平方しても mod 7 の世界では ≢ −1」という意味。

【2】 この流れだと、何となく「同様の理屈で、最初の数列 A の奇数番目の項の素因数は 4k+3 型に限られるのだろう」という予感がするかもしれない…。「偶数番目の項の素因数が 4k+1 型限定なら、バランスの問題として、奇数番目の項の素因数は 4k+3 型限定だろう」という考えは不自然ではないし、最初に見たように少なくとも数列の最初の方では、実際その通りになっている。正確に言うと、第27項 A27 までは、そうなっている。けど第29項は…
  A29 = 229 + 1 = 536870913 = 3 × 59 × 3033169
…分かりにくいが、実はこの 3033169 は4k+1型の素数。別の例として、第35項は:
  A35 = 235 + 1 = 34359738369 = 3 × 11 × 43 × 281 × 86171
281 が 4k+1 型であることは明らか。この数が素数であることも、簡単に確かめられる。

281 は 172 = 289 より小さいので、合成数だとすれば 2, 3, 5, 7, 11, 13 のどれかで割り切れるはず。どれでも割り切れないことは、暗算でも分かる。

従って「奇数番目の項の素因数は 4k+3 型に限られる」という予想は、正しくない!

実は、奇数番目の項の素因数は 8k+1 型または 8k+3 型に限られる。8k+3 型は 4k+3 型の一種なので、4k+3 型の素因数が含まれてること自体は事実だが、それに加えて、4k+1 型の一種(8 の倍数より 1 大きいタイプ)の素因数も、含まれる可能性がある。上記の 281 のように。

【3】 奇数番目の項のこの振る舞いは、幾つかの法則と関係している。まず…

第二補充法則 p を 3 以上の素数とする。このとき、もし p が 8k+1 型または 8k+7 型なら、x2 ≡ 2 (mod p) は解を持つ。逆に、この式が解を持つのは p がこれらの型の場合に限られる。

第一補充法則は −1 が平方剰余になる必要十分条件だったが、第二補充法則は 2 が平方剰余になる必要十分条件。このことから p が 8k+3 型または 8k+5 型なら 2 は p の非剰余となる。表にまとめると:

第一・第ニ補充法則
↓奇素数 p の型p の例−1 は p の…2 は p の…
4k+18k+117, 41平方剰余平方剰余
4k+38k+33, 11, 19, 43非剰余非剰余
4k+18k+55, 13, 29, 37平方剰余非剰余
4k+38k+77, 23, 31, 47非剰余平方剰余

4k+1 型、4k+3 型をそれぞれバニラ、チョコと呼ぶと、バニラがOKでチョコが駄目(第一補充法則)。8k+1, 8k+3, 8k+5, 8k+7 型をそれぞれ春・夏・秋・冬と呼ぶと、春・冬(両端)がOKで夏・秋が駄目(第二補充法則)。

さらに、次が成り立つ(第二補充法則【11】参照)。

平方剰余・非剰余の積の性質 〔ア〕 a, b が両方とも p の平方剰余なら ab も p の平方剰余。 〔イ〕 a, b の一方が p の平方剰余、他方が非剰余なら ab は p の非剰余。 〔ウ〕 a, b が両方とも p の非剰余なら ab は p の平方剰余。

平方剰余を (+1) として、非剰余を (−1) とすると、(+1) 同士の積、(−1) 同士の積は (+1) になり、(+1) と (−1) の積は (−1) になる。

今、最初の数列の奇数番目の項――第 2m+1 項とする――を考えると(m は 0 以上の整数):
  A2m+1 = 22m+1 + 1 = 2(2m)2 + 1
この数が 3 以上の素数 p で割り切れるとすると:
  2(2m)2 + 1 ≡ 0 (mod p)
両辺から 1 を引くと:
  2(2m)2 ≡ −1 (mod p)  ‥‥《く》
《く》左辺の因子のうち、(2m) の平方である (2m)2 は、もちろん p の平方剰余。例えば (2m)2 を R とすると、x2 ≡ R (mod p) には、当たり前だが x = (2m) という解がある(下記の具体例参照)。つまり《く》をこう書くことができる:
  R は p の平方剰余、そして 2R ≡ −1 (mod p)  ‥‥《け》

《け》左辺において、もし 2 が p の平方剰余なら、積の性質〔ア〕から、《け》左辺の 2R も p の平方剰余、それと合同な右辺の −1 も p の平方剰余。第一・第二補充法則から(表参照)、p が 8k+1 型のときに限って、この状況(2, −1 がどちらも平方剰余)があり得る。一方、もし 2 が p の非剰余なら、積の性質〔イ〕から 2R も p の非剰余、それと合同な右辺の −1 も p の非剰余。再び第一・第二補充法則を使うと、p が 8k+3 型のときに限って、この状況(2, −1 がどちらも非剰余)があり得る。

〔具体例〕 m = 3, n = 2m+1 = 7 の場合、A7 = 27 + 1 = 129 は、素数 p = 43 で割り切れる。このとき《く》に当たる式は:
  2(23)2 ≡ −1 (mod 43)
ここで R = (23)2 = 82 が 43 の平方剰余であるというのは、x2 ≡ 82 (mod 43) に解があるという意味だが、実際、見たまんま x = 8 という解がある。《け》に当たる式は:
  2R ≡ −1 (mod 43)
43 は 8k+3 型の素数なので、第二補充法則から 2 は 43 の非剰余。43 は 4k+3 型ともいえるので、第一補充法則から −1 も 43 の非剰余。つまり上の式は「非剰余である 2 に、平方剰余 R を掛けたら、非剰余 −1 になる」という意味を持ち、積の性質〔イ〕の通りになっている。

【4】 以上を要約すると、数列 An = 2n + 1 の偶数番目の項の素因数は 4k+1 型(言い換えれば 8k+1 型または 8k+5 型)に限られ、奇数番目の項の素因数は 8k+1 型または 8k+3 型に限られる。すなわち 8 で割って余りが 1, 3, or 5 の素数だけが、この数列のどれかの項の約数となる可能性を持つ: そのうち 8k+3 型は奇数番目の項限定、8k+5 型は偶数番目の項限定だけど、8k+1 型は、理論上どっちにもなり得る。一方、8 で割って余りが 7 の素数(8k+7型)は、この数列のどの項の約数になる可能性もない。

これが「約数 7 がどこにも現れない」という現象の理由。同じ理由から 23 も、この数列の約数としては一度も出番がない。

7 が「アンラッキー」という構造はこれでクリアーになった!

それでは 8k+7 型以外の素数なら、必ずこの数列の約数としてどこかで出番があるのだろうか?

数列 A を素数 p で割った余りは、大ざっぱな話として、遅くとも p 項目にはループする。ループが始まる前にどこかで余りが 0 にならないことには、無限ループの性質上、永遠にどの項も p で割り切れない。この「特定の数で割った余りは、有限の範囲でループ」という縛りは、この数列において、かなり厳しい制約といえるだろう。

2, 4, 8, 16, … という数列 B は、文字通り指数関数的にものすごい勢いで大きくなり、10項目にはもう1000を超えてしまう。それに 1 を足した数列 A も、増加スピードは同様。他方、素数は 1000 以下だけでも 168 個(2 を除いても 167 個)もあり、比較で言うと「存在密度」が高い。約4分の1に当たる 8k+7 型には出番がないとはいえ、「出番があるかもしれない素数」は、依然として多い。その全部が、100項やそこらまでで、因数として全種類出現する…というのは、何となく無理なような気もする。8k+1 型、8k+3 型、8k+5 型素数のうち、実際に因数として出番があるのは、10%くらいの割合では…。それとも、この「選抜」はもっと甘くて、それらの素数の50%くらいは、どこかで因数として出現するのだろうか。あるいは、ひょっとして…実は、100%出現するのだろうか?

30 以下の(奇数の)素数に話を限った場合:
  p = 3 は第1項で出現 21 + 1 = 3 は 3 の倍数
  p = 5 は第2項で出現 22 + 1 = 5 は 5 の倍数
  p = 7 は出現しない(8k+7型)
  p = 11 は第5項で出現 25 + 1 = 33 は 11 の倍数
  p = 13 は第6項で出現 26 + 1 = 65 は 13 の倍数
  p = 17 は第4項で出現 24 + 1 = 17 は 17 の倍数
  p = 19 は第9項で出現 29 + 1 = 513 は 19 の倍数
  p = 23 は出現しない(8k+7型)
  p = 29 は第14項で出現 214 + 1 = 16385 は 29 の倍数
ここまでは 8k+7 型以外、因数として100%出現しているが、果たしてこのまま出現率100%が維持されるのか…。

あなたの勘では…?

(続く)

⁂


<メールアドレス>