メモ（数論13）: Lucas–Lehmer Land

チラ裏　＞　数論 i　＞　メモ13

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

• 2023-01-13　いかすぜ！バイナッチ　依存症者の末路…ｗ
• 2023-01-16　「マイナス番目」のフィボナッチ数？　因数の出現位置
• 2023-01-17　バイナッチ数列の加法定理
• 2023-01-20　その数列は強いか？　「星のらせん階段」
• 2023-01-23　LLT: Lehmer’s Lemma 1　ギネスに載る素数…？
• 2023-01-29　美しいアラベスク　風に揺れるかすみ草
• 2023-01-31　LLT: Lehmer’s Lemmas 2 & 3　広い意味での Lucas 数列
• 2023-02-03　Lucas 数列という展望台　「ハイハイ、証明できました。んで？」
• 2023-02-06　メルセンヌ数と「LLT」（前編）
• 2023-02-12　メルセンヌ数と「LLT」（中編）
• 2023-02-22　メルセンヌ数と「LLT」（後編）
• 2023-03-02　メルセンヌ数の分解　もしも願いが一つかなうなら…

2023-01-13　いかすぜ！バイナッチ　依存症者の末路…ｗ

#数論　#フィボナッチ　#Lucas-Lehmer

フィボナッチ数列というのは 1, 1, 2, 3, 5, 8, 13, 21, … のように、各項が直前の2項の和になっている数列の一種。「第0項」の 0 から始めると:
　　0, 1, 1, 2, 3, 5, 8, 13, 21, …

それと似ているが、ひとひねり加え、各項を直前の2項の和の2倍としてみよう:
　　0, 1, 2, 6, 16, 44, 120, 328, …
例えば第3項（左端の 0 を第0項とする）の 6 は、直前の2項の和 1+2 の2倍。第4項の 16 は、直前の2項の和 2+6 の2倍。以下同様。フィボナッチ数列の「直前の2項の和」という部分に「～の2倍」という処理を追加した数列なんで、これをバイナッチ数列と呼ぶことにする（正式名称ではない）。「広い意味での Lucas 数列」の一例だが、あまり取り上げられることのない存在だろう。どんな景色が待ち受けているのだろうか…

【1】　とりあえず Binet（ビネ）の公式的な「一般項の式」を作りたい。Fibonacci の場合を思い出すと、フィボナッチ的性質を持つ単純な等比数列――
　　x, x², x³, …　　ただし x + x² = x³
――を考えることが出発点となった。それを模倣して、
　　x, x², x³, …　　ただし 2(x + x²) = x³
を考え、「ただし」の式の両辺を x で割ると:
　　2(1 + x) = x²　つまり　x² − 2x − 2 = 0
この2次方程式を解くと x = 1 ± √3。この2解を f = 1 + √3, g = 1 − √3 とすると、数列 fⁿ も数列 gⁿ も、それぞれ「直前の2項の和が次の項」という性質を持つのだから（n = 0, 1, 2, …）、それらを足した fⁿ + gⁿ も同じ性質を持ち、より一般的に cfⁿ + dgⁿ も同じ性質を持つ（c, d は定数。Fibonacci 数列やその一般化を考えたときの cuⁿ + dvⁿ と同様）。この定数 c, d を決定したい。

n = 0 のとき fⁿ = gⁿ = 1 なので cfⁿ + dgⁿ = c + d = 0 （なぜならバイナッチ数列の第0項は 0）、つまり d = −c。

n = 1 のとき fⁿ = 1 + √3, gⁿ = 1 − √3 なので cfⁿ + dgⁿ = c(1 + √3) + d(1 − √3) = 1 （なぜならバイナッチ数列の第1項は 1）、上記 d = −c を代入すると:
　　c(1 + √3) − c(1 − √3) = 1　つまり　2c√3 = 1　だから　c = 1/(2√3)

結局、バイナッチ数列の第n項――大文字の U_n で表すことにする――は（d = −c に注意すると）:
　　U_n = cfⁿ + dgⁿ = cfⁿ − cgⁿ = c(fⁿ − gⁿ)　ところが c = 1/(2√3) なので
　　U_n = (fⁿ − gⁿ) / (2√3)　ここで f = 1 + √3, g = 1 − √3
これが Binet の公式 F_n = (uⁿ − vⁿ) / √5 の^*1、バイナッチ・バージョン。

*1　ここで u = (1 + √5)/2, v = (1 − √5)/2。従って u − v = √5 = 公式の分母。バイナッチ・バージョンでも f − g = 2√3 = 公式の分母。この小文字の u, v は、バイナッチ数列を表すのに使う大文字の U, V とは無関係。

Binet の公式とその Bi-nacci 版
　　フィボナッチ数列の一般項　F_n = (uⁿ − vⁿ)/(u − v)
　　　　ただし u = (1 + √5)/2, v = (1 − √5)/2
　　バイナッチ数列の一般項　U_n = (fⁿ − gⁿ)/(f − g)
　　　　ただし f = 1 + √3, g = 1 − √3
フィボナッチの u & v が f & g に置き換わっただけで、内容的には同じパターン。

〔例〕　n = 3 の場合。3乗の展開の公式（二項定理の n = 3 に当たる）…
　　(x + y)³ = x³ + 3x²y + 3xy² + y³
…を使って展開すると:
　　f³ = (1 + √3)³ = 1 + 3⋅1⋅√3 + 3⋅1⋅3 + 3√3 = 10 + 6√3
同様に g³ = (1 − √3)³ = 1 − 3√3 + 9 − 3√3 = 10 − 6√3 なので:
　　f³ − g³ = (10 + 6√3) − (10 − 6√3) = 12√3
だから U₃ = (f³ − g³) / (2√3) = (12√3) / (2√3) = 6　バイナッチ数列の第3項と一致！

【2】　フィボナッチ数列 F_n には、Lucas（ルュカ）数と呼ばれる相棒の数列 L_n = 2, 1, 3, 4, 7, 11, … があって、両者は緊密な関係にあり、この二つを組み合わせることで、しばしば見通しが良くなるのだった。バイナッチ数列 U_n にも同様の相棒―― V_n で表すことにする――が考えられる。フィボナッチ数列の相棒は、Binet 形式では
　　L_n = uⁿ + vⁿ　　← 小文字の u, v。バイナッチ数列の U, V とは無関係
だったので、同様に考えると、バイナッチ数列の相棒は:
　　V_n = fⁿ + gⁿ

この相棒 V_n = fⁿ + gⁿ は、やはり cfⁿ + dgⁿ の形なので（c = d = 1）、「ある項は直前の2項の和の2倍」というバイナッチ的性質を持つ。具体的に…
　　V₀ = f⁰ + g⁰ = 1 + 1 = 2
　　V₁ = f¹ + g¹ = (1 + √3) + (1 − √3) = 2
…なので、V_n は 2, 2, 8, 20, 56, … となるはず（8 は直前の2項の和 2 + 2 の2倍、その次の 20 も直前の2項の和 2 + 8 の2倍、等々）。

〔例〕　n = 3 に対して f³ + g³ = (1 + √3)³ + (1 − √3)³ = (1 + 3√3 + 3⋅3 + 3√3) + (1 − 3√3 + 3⋅3 − 3√3) = 1 + 9 + 1 + 9 = 20

バイナッチ数列とその相棒

n	0	1	2	3	4	5	6
Un	0	1	2	6	16	44	120
Vn	2	2	8	20	56	152	416

バイナッチ数列の一般項
　　U_n = (fⁿ − gⁿ)/(f − g), V_n = fⁿ + gⁿ
　　ここで f = 1 + √3, g = 1 − √3　（従って f − g = 2√3）

相棒が活躍する一例として、フィボナッチ数列には F_2n = (u²ⁿ − v²ⁿ)/(u − v) = (uⁿ + vⁿ)(uⁿ − vⁿ)/(u − v) = L_nF_n = F_nL_n というシンプルな関係^*2がある（小文字の u, v はバイナッチの U, V とは無関係）。バイナッチとその相棒に関しても、単に文字が u, v から f, g に置き換わるだけで式の形は全く同じなので、同様に U_2n = U_nV_n というシンプルな関係が成り立つ。

〔例〕　U₄ = 16 は U₂V₂ = 2 × 8 に等しい。U₆ = 120 は U₃V₃ = 6 × 20 に等しい。

*2　詳細については「不思議っち☆フィボナッチ（第5話）」【15】参照。

文字が違うだけの同じ式なんだから「そうなって当然」とはいえ、なかなかエレガントで美しい！

でも、こんなこと、一体何の役に立つのだろうか。

A Primer for the Fibonacci Numbers [1] の中で Brousseau という人は、冗談半分に The inveterate Fibonacci addict tends to（長年のフィボナッチ依存症の人は往々にして…）と書いている。いわく 13 という数字を聞くと反射的に F₇ を連想し、55 という数字を聞くと F₁₀ だと思うのだそうだ。依存症なので、やめたくなくても、やめられない（らしいｗ）。

[1] https://www.fq.math.ca/primer.html

「広い意味での Lucas 数列」の理論には、ある種の応用もあるかもしれないけれど、その開祖（？）の Lucas 自身 Récréations mathématiques という本も書いている。数学パズルという言葉もあるように、それはレクリエーション（遊び）であり、悪く言えば「現実逃避」。分散コンピューティングによる因数分解や素数探しにしたって、誰かが「何の役に立つのか？」と尋ねれば「数学の発展に寄与する可能性もあるし、ハードウェアのテストにもなる」といった答えが返ってくるだろうが、参加者の本音は「あわよくば世界最大の素数を見つけて自慢したい」とか「面白ければ、役に立つかどうかなんてどうでもいい」といったところだろう。

高性能マシンを使い「誰が最初に素因数を見つけるか」と競争しているありさま、0.1%の高速化でしのぎを削っているありさま、オーバークロックしたCPUを徹夜でフル回転させているありさまなど、本質的には「走り屋」と変わらないのでは…ｗ

普通の人は「数学」と聞くと「学校の勉強」を連想し、「数論の面白さ」といわれれば「頭がいいんだ・うらやましい」などと短絡的に判断するかもしれないが、数論には「面白いだけで、とりあえず何の役にも立たない事柄」が非常に多い。歴史を振り返ると、そうした「すぐには役立たない研究」が後から重大な意味を持つことも確かにあるんだけど、リアルタイムで見ると、当事者は「面白いからやってる」だけ。何の役にも立たないことに夢中になれるのは、果たして善いことなのか。幸せなのか、ばかなのか…。たぶん、その両方なのだろう。

（続く）

2023-01-16　「マイナス番目」のフィボナッチ数？　因数の出現位置

#数論　#フィボナッチ　#Lucas-Lehmer

フィボナッチ数列 1, 1, 2, 3, 5, 8, 13, …。その第1項 F₁ = 1 の直前の理論上の「第0項」は F₀ = 0 だが、そのさらに直前の「第マイナス1項」は何だろうか？　このような「マイナス番目の項」を考えることで、通常の範囲のフィボナッチ数列について、素敵な性質が証明される。

【3】　フィボナッチ数列の第 −1 項を x として、それ以降の項を並べると:
　　x, 0, 1, 1, 2, 3, 5, …
フィボナッチ数列の性質上 x + 0 = 1 になるはずだから x = 1。

第 −2 項を y とすると y, 1, 0, 1, 1, 2, 3, 5, … となって y + 1 = 0 だから y = −1。

第 −3 項を z とすると z, −1, 1, 0, 1, 1, 2, 3, 5, … となって z + (−1) = 1 だから z = 2。

以下同様に考えると:
　　…, 13, −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, 13, …

〔補足〕　フィボナッチ数列を一つずつ左（マイナス番目の方向）に延ばすには、現在の左端の項をその手前（右隣）の項から引けばいい。例えば −8−13 = −21。なぜなら左端を B として
　　?, B, C
の形になっているとき、フィボナッチの性質上 ? + B = C だから ? = C − B となる。

次のことが予想される。「マイナス番目」のフィボナッチ数は、「プラス番目」の対応するフィボナッチ数と、絶対値は同じ。符号については、「マイナス奇数番目」の項はプラスで、「マイナス偶数番目」の項はマイナス。

普段 Binet の公式…
　　F_n = (uⁿ − vⁿ)/√5
　　ただし u = (1 + √5)/2, v = (1 − √5)/2
…を使うとき、何となく n は 1 以上（あるいは 0 以上）の整数のような感じがするが、別に n が負じゃ駄目という理由もなさそうだ（成分の v も、もともと負の数だし）。とりあえず n を 1 以上の正の整数と仮定しておいて、Binet の公式の n を負の整数 −n に置き換えてみると:
　　F_−n = (u⁻ⁿ − v⁻ⁿ)/√5

例えば u⁻ⁿ というのは u の逆数 u⁻¹ の n 乗のことだが^*3、u の逆数は −v で v の逆数は −u なので^*4、結局こうなる:
　　F_−n = (u⁻ⁿ − v⁻ⁿ)/√5 = [(u⁻¹)ⁿ − (v⁻¹)ⁿ]/√5 = [(−v)ⁿ − (−u)ⁿ]/√5
　　この右端の分子 = (−1)ⁿ(v)ⁿ − (−1)ⁿ(u)ⁿ = (−1)ⁿ(vⁿ − uⁿ)　　← (−1)ⁿ でくくった
　　= (−1)ⁿ × (−1)(−vⁿ + uⁿ)　　← 無理やり (−1) でくくって右端の丸かっこ内の符号を逆に
　　= (−1)ⁿ⁺¹(uⁿ − vⁿ)
これは通常の F_n の分子の (−1)ⁿ⁺¹ 倍に当たる（分母は同じ）。すなわち通常の F_n と比べ、n が奇数なら全く同じ（プラス1倍）、n が偶数なら符号だけ逆（マイナス1倍）。前記の予想通り！

負の番号のフィボナッチ数は整数で、対応する正の番号のフィボナッチ数と等しいか、またはその −1 倍である: F_−n = (−1)ⁿ⁺¹F_n

(−1)ⁿ⁺¹ の指数 n+1 に深い意味はなく、n が偶数 or 奇数のとき、それに対応して (−1)^△ が −1 or +1 になってくれれば、△ の式は何でもいい（n−1 や n+3 でもOK）。

*3　なぜなら u⁻ⁿ = (u⁻¹)ⁿ。例えば 3⁻¹ = 1/3 の両辺を2乗すると (3⁻¹)² = (1/3)² つまり 3⁻² = 1/9 とか。

*4　x = u と x = v は x² − x − 1 = 0 の2解なんで、解と係数の関係から uv = −1、つまり u(−v) = (−u)v = 1 となる（「カッシーニの隙間をたたけ！」【1】参照）。あるいは u = (1 + √5)/2 について、直接計算で u⁻¹ = 2/(1 + √5)。分母を有理化して:
　　u⁻¹ = [2(1 − √5)]/[(1 + √5)(1 − √5)] = [2(1 − √5)]/[1² − (√5)²]
　　= 2(1 − √5)/(−4) = (1 − √5)/(−2) = −v
v = (1 − √5)/2 についても同様。

【4】　「負の番号のフィボナッチ数」の概念を使うと、加法定理…
　　F_a+b = F_a+1F_b + F_aF_b−1　　《ア》
…の引き算バージョンが得られる。単に b を −b に置き換えればいい:
　　F_a−b = F_a+1F_−b + F_aF_−b−1　　《イ》

今 a 番目のフィボナッチ数 F_a と、b 番目のフィボナッチ数 F_b について、どちらも整数 q の倍数だと仮定しよう。このとき、q の倍数 F_a のそのまた倍数は、何であれ q の倍数。 q の倍数 F_b のそのまた倍数も、何であれ q の倍数。だから《ア》右辺は q の倍数と q の倍数の和で、従って、その和に等しい左辺 F_a+b もまた q の倍数。同じ仮定の下で、《イ》についても同様のことがいえる。F_−b−1 は何らかの整数だから、《イ》右辺第2項は F_a の倍数、従って q の倍数。一方 F_−b は、q の倍数 F_b の ±1 倍なので、やはり q の倍数^*5。従って《イ》右辺第1項も q の倍数。結局、q の倍数の和に等しい左辺 F_a−b も q の倍数。

*5　例えば b = 9 のとき F_b = F₉ = 34 は q = 17 の倍数; それに等しい F_−b = F₋₉ = 34 も、もちろん q = 17 の倍数。別の例として b = 10 のとき F_b = F₁₀ = 55 は q = 5 の倍数（11倍）; 符号が違うだけの F_−b = F₋₁₀ = −55 も、もちろん q = 5 の倍数（−11倍）。

観察　F_a と F_b がどちらも q の倍数なら、F_a+b も q の倍数、F_a−b も q の倍数。

〔例〕　F₉ = 34 と F₆ = 8 は、どちらも 2 の倍数なので、F₉₊₆ = F₁₅ も2の倍数、F₉₋₆ = F₃ も2の倍数（具体的な値は、それぞれ 610 と 2）。

この単純な観察が、以下の議論の鍵に！

【5】　フィボナッチ数列には、「数列の番号 n の倍数関係が、その番号に対応する値 F_n の倍数関係に、反映される」という美しい性質がある（「星のらせん階段」）。例えば、番号 7, 14, 21, … は 7 の倍数なので、それらの番号に対応する値 F₇, F₁₄, F₂₁, … は、どれも F₇ の倍数に。

値 F_n を構成する因数のレベルで見ても――。もし素数 q が、項の番号 n = w のとき F_w の因数として初登場（新出）したのなら、同じ素数 q は F_2w, F_3w, F_4w, … の因数として、周期的に再登場する（下の表参照）。しかも、それ以外の位置で q が F_n の因数になることはない（つまり n が「q の新出位置の番号」w の倍数でないなら、F_n は q の倍数ではない）。

フィボナッチ数の因数: 丸かっこ内は新出素数

n	Fn	素因数分解	n	Fn	素因数分解
1	1		13	233	(233)
2	1		14	377	13 × (29)
3	2	(2)	15	610	2 × 5 × (61)
4	3	(3)	16	987	3 × 7 × (47)
5	5	(5)	17	1597	(1597)
6	8	23	18	2584	23 × 17 × (19)
7	13	(13)	19	4181	(37) × (113)
8	21	3 × (7)	20	6765	3 × 5 × 11 × (41)
9	34	2 × (17)	21	10946	2 × 13 × (421)
10	55	5 × (11)	22	17711	89 × (199)
11	89	(89)	23	28657	(28657)
12	144	24 × 32	24	46368	25 × 32 × 7 × (23)

〔例〕　素因数 q = 7 の新出位置は w = 8。すなわち F₈ は素因数 7 を含むが、F₁ ～ F₇ の各数は、この素因数を持たない。素因数 q = 7 は、「w = 8 の任意の倍数」の番号の項（F₁₆, F₂₄, etc.）において出現する; それ以外の番号の項では出現しない。F₈ は新出素数 q = 7 の他に、既出の素因数 3 を持つ（それは第4項で新出した――項の番号 w = 8 は、因数 3 が初登場した項の番号 4 の倍数）。

素因数の出現位置の法則　第 w 項 F_w において新出した素因数 q は、第 2w 項、第 3w 項、第 4w 項、…で周期的に再出現するが、それ以外の項で出現することはない: 任意の番号 n について、n が w の倍数なら F_n は q の倍数; n が w の倍数でないなら F_n は q の倍数でない。

〔補足〕　素数 q がフィボナッチ数の因数のとき、「q が F_n の因数になる最初の項」の番号 n を「q が初登場する項の番号」（the rank of apparition of q）――略して q の新出位置――と呼ぶ（ただし n は正の整数とする）。F_n の素因数は、
　　(I)　その位置で初登場する原始的な素因数（primitive prime factor）――略して新出素数――と、
　　(II)　その位置より前の（n の約数番目のどれかの）項で初登場し、周期的に再登場する既出素数
に分けられる。Édouard Lucas は前者を diviseur propre、後者を diviseur impropre と呼んだ。フィボナッチ数列に限らず、任意の数列（例えばバイナッチ数列）の各項についても、同様に「因数の新出・既出」や「新出位置」を考えることができる。

証明　F_2w, F_3w, F_4w などは F_w 自体の倍数なので（「星のらせんの定理」）、q に限らず F_w の全素因数を含む。よって命題の前半は当たり前。問題は「それ以外の項は因数 q を含まない」という部分。例えば F₈ において初登場する素因数 q = 7 が F₁₆, F₂₄, F₃₂, … で再登場するのはいいとして、番号が8の倍数以外の項（例えば F₃₀）が因数 q = 7 を含んじゃ駄目！という理由があるのだろうか？

ここで最初の「マイナス番目のフィボナッチ数」の研究が役立つ。【4】の観察によれば、もしも F₃₀ と F₂₄ がどちらも q = 7 の倍数なら F₃₀₋₂₄ = F₆ も q = 7 の倍数になってしまう！　これは理不尽: 因数 q = 7 が初登場する項の番号は w = 8 だから、それより前の第6項がこの因数を持つわけない。よって F₃₀ が因数 q を持つという可能性は、否定される。この発想を一般の場合に適用しよう…。

一般に因数 q の新出位置を w とする。「w の倍数以外の変な番号 h の項 F_h が因数 q を持つ場合がある」と仮定して、矛盾を導く。変な番号 h は w の倍数じゃないので、w で割り切れない; h を w で割ったとき、商が k で余りが j とでもしよう:
　　h = kw + j　　ここで j は w で割った余りなので 1 以上 w 未満
　　つまり　h − kw = j
仮定によれば F_h は因数 q を持つ（つまり q の倍数）。F_kw は F_w の倍数なので、もちろん因数 q を持つ。従って【4】の観察から…
　　F_h−kw = F_j
…も q の倍数（つまり因数 q を持つ）。これは、ばかげているッ！　q が初登場する項の番号は w なので、F_j（番号 j は 1 以上 w 未満である）が因数 q を持つわけない。この不合理が生じた原因は「変な番号の項 F_h が因数 q を持つことがあり得る」という仮定。従って、その仮定は却下され、「w の倍数以外のでたらめな番号の項が、因数 q を持つことはない」と結論される。□

第 w 項で新出した素因数 q は、w の倍数番目の全部の項で周期的にフィボナッチ数の因数となり、それ以外の項では因数とならない。シンプルで素敵な構造だ！

出現位置の法則は、因数 q を（素数に限らず）任意の正の整数として、その初登場・再登場を考えても、そのまま成り立つ。その結果、次のことが示されるだろう: 番号 a, b の最大公約数が d なら、F_a と F_b の最大公約数は F_d に等しい。つまり（倍数関係だけでなく）最大公約数の関係についても、フィボナッチ数の項の番号の間の関係が、項の値の間の関係にそのまま反映される（後述）。

出現位置の法則や最大公約数との関係について証明する場合、文献的には Bézout の定理を経由することが多いようだ。このメモでは「負の番号のフィボナッチ数」という奇手を使い Bézout の定理をバイパスして、分かりやすい証明を目指した。アイデアは、本質的には D. H. Lehmer [2] に基づく。Lehmer は Lucas–Lehmer test の証明の補題において、バイナッチ数列に関して同種の論法を使った。

（続く）

2023-01-17　バイナッチ数列の加法定理

#数論　#フィボナッチ　#Lucas-Lehmer

フィボナッチ数列の場合、Binet の公式や加法定理が、いろいろな研究の土台となった。フィボナッチ数列のいとこ「バイナッチ数列」についても、加法定理を考えてみたい。導出法はフィボナッチ版とほとんど同じで、その復習ともいえる。加法定理の一つでは、フィボナッチ版にはなかった係数が付く（この係数は「逆数」の形の違いに由来し、さかのぼると、背後にある2次方程式の定数項の、符号を変えたものに当たる）。

【6】　Fibonacci 数列には、2種類の加法定理がある:
　　①　F_a+b = F_a+1F_b + F_aF_b−1
　　②　F_a+b = (F_aL_b + F_bL_a)/2
Fibonacci 数同士の関係として話が完結する①は、概念的にはシンプルだが、式の形がやや複雑で覚えにくい（覚え方）。②は相棒の Lucas 数とペアで考える必要があるが、その代わり式の形はシンプル。これらの公式については、帰納法で証明することもできるし（①・②）、Binet 形式を使い直接証明することもできるのだった。

①②の Bi-nacci バージョンを考えよう。②については、フィボナッチの②と同様の計算が成り立つ。バイナッチ数列とその相棒の一般項の公式から:
　　U_aV_b = (f^a − g^a)/(f − g) × (f^b + g^b)
　　U_bV_a = (f^b − g^b)/(f − g) × (f^a + g^a)
この2式について、左辺同士と、展開した右辺同士^*6をそれぞれ足し合わせると:
　　U_aV_b + U_bV_a = (2f^af^b − 2g^ag^b)/(f − g)
　　= 2(f^a+b − g^a+b)/(f − g) = 2U_a+b
これは②の両辺を 2 倍して、文字 F, L をそれぞれ U, V に置き換えたものと同一。つまり②に関しては、バイナッチでも、フィボナッチと全く同じ形の加法定理が成り立つ！

*6　分子に生じる計8項のうち、第1式から出る f^ag^b, −g^af^b と第2式から出る f^bg^a, −g^bf^a は、打ち消し合う。

〔例1〕　バイナッチ数列 U_n の第3項と第5項から第8項を求める。
　　2U₈ = 2U₃₊₅ = U₃V₅ + U₅V₃ = 6 × 152 + 44 × 20
　　両辺を2で割って U₈ = 3 × 152 + 22 × 20 = 456 + 440 = 896

バイナッチ数列とその相棒

n	0	1	2	3	4	5	6	7	8
Un	0	1	2	6	16	44	120	328	896
Vn	2	2	8	20	56	152	416	1136	3104

次に①のバイナッチ版。証明法は、フィボナッチ版①の直接証明とほぼ同じだが、以下で見るように「U_b−1 を含む項が2倍される」という小さな違いが生じる。

スペース節約のため f − g を H と略すと、一般項の公式から:
　　U_a+1U_b = (f^a+1 − g^a+1)/H × (f^b − g^b)/H = (f^af − g^ag)(f^b − g^b)/H²　　《ウ》
　　U_aU_b−1 = (f^a − g^a)/H × (f^b−1 − g^b−1)/H = (f^a − g^a)(f^bf⁻¹ − g^bg⁻¹)/H²
f⁻¹ = −g/2, g⁻¹ = −f/2 という逆数関係^*7を利用すると:
　　U_aU_b−1 = (f^a − g^a)[f^b(−g/2) − g^b(−f/2)]/H² = (f^a − g^a)[½(g^bf − f^bg)]/H²
逆数の分母が 2 なので ½ という因子が発生した。これを解消するため両辺を2倍する:
　　2U_aU_b−1 = (f^a − g^a)(g^bf − f^bg)/H²　　《エ》
《ウ》《エ》について、左辺同士と、展開した右辺同士^*8をそれぞれ足し合わせると:
　　U_a+1U_b + 2U_aU_b−1 = (f^a+bH − g^a+bH)/H² = (f^a+b − g^a+b)/H = U_a+b

〔例2〕　a = 3, b = 5 とすると U₈ = U₃₊₅ = U₄U₅ + 2U₃U₄ = 16 × 44 + 2(6 × 16) = 896

バイナッチ数列の加法定理
　　①　U_a+b = U_a+1U_b + 2U_aU_b−1　　第2項の係数 2 がフィボナッチの①と違う
　　②　U_a+b = (U_aV_b + U_bV_a)/2　　　フィボナッチの②と全く同じ形

*7　直接計算すると fg = (1 + √3)(1 − √3) = 1 − 3 = −2。あるいは x = f と x = g は x² − 2x − 2 = 0 の2解だから、解と係数の関係から、同じ等式 fg = −2 を得る。その両辺の −½ 倍を考えると f⋅(−g/2) = (−f/2)⋅g = 1。

*8　《ウ》《エ》から生じる分子の計8項のうち、4項は打ち消し合い、次の4項が残る:
　　f^a+bf + g^a+bg − f^a+bg − g^a+bf = f^a+b(f − g) + g^a+b(g − f) = f^a+bH − g^a+bH

これで出発の準備は整った！　まずは前回同様、マイナス番目の項を考え、加法定理と組み合わせることで、バイナッチ数列の倍数構造（「星のらせん」）を解明したい。（続く）

2023-01-20　その数列は強いか？　「星のらせん階段」

#数論　#フィボナッチ　#Lucas-Lehmer

ちょうど10段ごとに一周するらせん階段では、10段目・20段目・30段目…が、階段の基点（0段目）の真上になる。そのように、フィボナッチ数列では、第10項・第20項・第30項…が同じ倍数列の上で、きれいにハモっている。
　　F₂₀ = 6765, F₃₀ = 832040, F₄₀ = …
が、全部 F₁₀ = 55 でキッカリ割り切れる^*9のだ！

この性質は、10に限らず任意の周期で成り立つ: F₆, F₁₂, F₁₈, … も倍数列、F₇, F₁₄, F₂₁, … も倍数列。その結果、例えば F₂₀ は「F₄ から始まる倍数列」、「F₁₀ から始まる倍数列」など、複数の周期の「波」に乗っていて、自分自身も F₂₀, F₄₀, F₆₀, … という新たな「波」の出発点となる。

フィボナッチ数で遊んでて、この性質に気付いたときは、ちょ～美しい！と感じ「星のらせん階段」と名付けた。フィボナッチ数の黄金比は、正五角形・星型と縁が深いので「星」。フィボナッチ数には、巻き貝のような「らせん」のイメージもある――スイスのチューリッヒ中央駅には、らせんとフィボナッチ数を題材にした巨大オブジェがある（画像）。

「星のらせん」構造を持つ数列は、正式には divisibility sequence と呼ばれるらしい。フィボナッチのいとこ「バイナッチ」も同じ構造を持つが、フィボナッチは「強い」、バイナッチは「弱い」という違いがある。後学のため「強い・弱い」の意味を具体例で観察しておきたい。

*9　これらの数は 5 の倍数なので、11 の倍数であることさえ確かめれば、55 の倍数と分かる。11 の倍数を素早く見分けるには、奇数番目の桁の和から偶数番目の桁の和を引く方法がある:
　　6765　→　奇数桁の和（7+5=12） − 偶数桁の和（6+6=12） = 0　→　0 は 11 の倍数なので 6765 も 11 の倍数
　　832040　→　奇数桁の和（3+0+0=3） − 偶数桁の和（8+2+4=14） = −11　→　−11 は 11 の倍数なので 832040 も 11 の倍数
「11で割り切れるかどうか」の判定だけなら、逆に偶数桁の和から奇数桁の和を引いてもよく、大きい方から小さい方を引けばいいのだが、奇数桁ひく偶数桁の順で引き算すると、11で割り切れない場合に「11で割った余り」の情報が得られる:
　　（例）　1234 を 11 で割ると (2+4)−(1+3) = 2 余る
「余り」については mod 11 と考えてもいいし、必要なら 11 or 22 or 33 などを加減して0～10の範囲に調整してもいい:
　　（例）　2143 を 11 で割ると (1+3)−(2+4) = −2 余る → プラス11補正して 9 余る

【7】　フィボナッチ数列（各項は直前の2項の和）も、バイナッチ数列（各項は直前の2項の和の2倍）も、同じ「星のらせん」の構造を持っている。つまり、項の番号 n の倍数関係が、項の値 F_n ないし U_n の倍数関係にそのまま反映される――例えば 4, 8, 12, 16, … は 4 の倍数なので、第4項・第8項・第12項・第16項…は第4項の倍数。同様に、10 と 15 はどちらも 5 の倍数なので、第10項と第15項は、どちらも第5項の倍数。

フィボナッチ数・バイナッチ数の因数: 丸かっこ内は新出素数

n	Fn		Un
1	1		1
2	1		2	= (2)
3	2	= (2)	6	= 2⋅(3)
4	3	= (3)	16	= 24
5	5	= (5)	44	= 22⋅(11)
6	8	= 23	120	= 23⋅3⋅(5)
7	13	= (13)	328	= 23⋅(41)
8	21	= 3⋅(7)	896	= 27⋅(7)
9	34	= 2⋅(17)	2448	= 24⋅32⋅(17)
10	55	= 5⋅(11)	6688	= 25⋅11⋅(19)
11	89	= (89)	18272	= 25⋅(571)
12	144	= 24⋅32	49920	= 28⋅3⋅5⋅(13)
13	233	= (233)	136384	= 26⋅(2131)
14	377	= 13⋅(29)	372608	= 27⋅41⋅(71)
15	610	= 2⋅5⋅(61)	1017984	= 27⋅3⋅11⋅(241)
16	987	= 3⋅7⋅(47)	2781184	= 212⋅7⋅(97)
17	1597	= (1597)	7598336	= 28⋅(67)⋅(443)
18	2584	= 23⋅17⋅(19)	20759040	= 29⋅32⋅5⋅17⋅(53)

別の例として、第12項と第18項は、第6項の倍数。逆に言えば、第6項は第12項の約数であり、第18項の約数でもある――つまり、第6項は、第12項と第18項の公約数。ここまではフィボナッチもバイナッチも同じだが、この 6 という項の番号は、12 と 18 の最大公約数だ。フィボナッチの場合 F₆ = 8 自身も F₁₂ = 144 と F₁₈ = 2584 の最大公約数になっている。この「番号の間の最大公約数の関係が、そのまま項の間の最大公約数の関係になる」という性質が strong divisibility というもの。一方、バイナッチ数列の場合、U₁₂ と U₁₈ の最大公約数を計算すると 3840 になる――従って U₆ = 120 は、「最大公約数ではないただの公約数」の一つに過ぎず、バイナッチ数列は strong divisibility を持たないということになる。

イメージ的な説明として、フィボナッチ数 F₁₂ = 2⁴⋅3² と F₁₈ = 2³⋅17⋅19 の因子の共通部分 2³（要するに両者の最大公約数）は、純粋に、共通の先祖 F₆ の「遺伝子」（因子）を受け継いだもの。U₁₂ と U₁₈ も、ご先祖 U₆ の因子を100%受け継ぐ。ところが U₁₂ = 2⁸⋅3⋅5⋅13 と U₁₈ = 2⁹⋅3²⋅5⋅17⋅53 の共通部分 2⁸⋅3⋅5 = 3840 には、「純粋」に U₆ = 2³⋅3⋅5 の遺伝子が100%あるだけでなく「過剰」な部分がある: U₆ と比べ 2 が 5 乗も増えている！

「先祖の遺伝子」ではないものが、どこからともなく入り込んでいるのだ。その理由も明らかだろう。バイナッチ数列では、新しい項を作るとき、直前の2項の和を「2倍する」という操作が行われる。「2倍する」というのは 2 を掛け算することなので、それによって因子「2」が強制追加され、直前の2項のどちらと比べても、「2」の指数が少なくとも 1 増えてしまう。いわば「遺伝子操作」。

〔補足〕　一つ一つの各項は、祖先から受け継いだものではない因子を含む（新出素数、または既出素数の指数が増える場合）。それはその項自体の「個性」であり、その項の子孫（倍数番目の項）たちに継承される。一方、直接の先祖・子孫関係にない二つの項 F_a, F_b について（直近の）共通の先祖 F_d を考えた場合、F_a, F_b の2項が「共通して持つ因子」は、全て F_d から受け継がれている。「共通して持つ因子」を考えることで、F_a, F_b それぞれの「個性の因子」は考察対象外となり、純粋に「遺伝関係」の問題となる。バイナッチの場合も「共通の祖先の因子は100%受け継がれる」点に変わりはないが、U_a, U_b は一般に「それ以外の“過剰”な共通因子」も持っている（具体的に、共通祖先は遺伝子「2」を少ししか持っていないのに、U_a, U_b はどちらも、先祖が持っていた以上の数の遺伝子「2」を持つ）。

先祖から子孫へ「倍数関係」を保存するという観点では、フィボナッチもバイナッチも問題ない。水増しの「2倍」があっても、やたらと大きな倍数になるだけで、倍数関係自体（例えば 7 の倍数が 7 の倍数であるという性質）は破壊されないからだ。一方、逆に子孫から先祖へさかのぼろうとすると、バイナッチ数列には「遺伝子操作」があるので、フィボナッチ数列ほど単純明快な構造にはならない。

【8】　先祖から子孫への「倍数関係」の継承。それは、加法定理が「倍数関係」を保存することの結果。すなわち、第 a 項と第 b 項がどちらも q の倍数なら、第 a+b 項も q の倍数。このことは、フィボナッチ数列に関しては【4】で考察した。バイナッチ数列に関しても同様で、
　　U_a+b = U_a+1U_b + 2U_aU_b−1
なのだから（【7】）、もし U_a が q の倍数なら右辺第2項は q の倍数になり、もし U_b が q の倍数なら右辺第1項は q の倍数になる――その二つの条件が満たされるとき、U_a+b は q の倍数と q の倍数の和に等しく、再び q の倍数。

フィボナッチ数列またはバイナッチ数列の第 n 項が q の倍数だとして、加法定理で a = n, b = n とすれば、第 a 項も第 b 項も q の倍数; 第 a+b 項、つまり第 2n 項も q の倍数。今、あらためて a = 2n, b = n とすれば、再び第 a 項も第 b 項も q の倍数; 第 a+b 項、つまり第 3n 項も q の倍数。今、あらためて a = 3n, b = n とすれば…。と、この議論を必要なだけ繰り返すことで、第 n 項が q の倍数なら、第 kn 項も q の倍数（k: 任意の正の整数）。特に、第 n 項の値自身を q とすれば（そのとき第 n 項は q の 1 倍である）、「第 2n 項・第 3n 項・第 4n 項…がいずれも第 n 項の倍数」という「星のらせん」の性質が生じる。

「ある数が q の倍数」ということは「その数は q で割り切れる」ということなので、倍数関係とは、裏を返せば約数関係ともいえる。

数列における倍数・約数の関係が、最大公約数の関係にまで拡張できるかどうか――つまり strong divisibility が成立するかどうか――は、前記のイメージ的説明からも想像がつくように「子孫から先祖へ、ある種の“逆算”ができるか？」という問題と関連している。具体的には: 加法定理の足し算 a+b を引き算 a−b に置き換えた「減法定理」が、倍数関係を保存するか？

a と b の最大公約数を d としよう。もし第 a 項と第 b 項が q の倍数のときに第 a−b 項も q の倍数になる保証があるのなら、実はその性質を繰り返し使うことで第 d 項も q の倍数になる――このような引き算によって番号 a と b の項から番号 d の項に至ることは、実は「ユークリッドの互除法」というアルゴリズムを使い a と b の最大公約数 d を求めることに当たる。とりあえず、ここでは「減法定理が倍数関係を保存するか？」を考えてみたい。フィボナッチ数列の減法定理について、答えが yes であることは、【4】で考察した^*10。

*10　フィボナッチ数列の「マイナス番目」の項は、対応する「プラス番目」の項と（符号は一致することも逆になることもあるが）絶対値が同じなので、第 b 項を考えても、第 −b 項を考えても、倍数・約数関係には一切影響しないのだった（だから「項の番号の足し算」でも「引き算」でも、結果の倍数・約数関係は全く同様になる）。「互除法」は超重要だが、ここでは必要ないので説明を省く（必要になった時点で分かりやすく説明したい）。

【9】　バイナッチ数列の場合、話はそう簡単にはいかない――マイナス番目の項は、知らないとびっくりするような振る舞いを見せる。

いつものように f = 1 + √3, g = 1 − √3, f⁻¹ = −g/2, g⁻¹ = −f/2 を使って、Binet 形式で第 −n 項を求めると:
　　U_−n = (f⁻ⁿ − g⁻ⁿ) / (f − g)　　《カ》
《カ》の分子は:
　　(f⁻¹)ⁿ − (g⁻¹)ⁿ = (−g/2)ⁿ − (−f/2)ⁿ = gⁿ(−½)ⁿ − fⁿ(−½)ⁿ
　　= (−½)ⁿ × (gⁿ − fⁿ) = −(−½)ⁿ × (fⁿ − gⁿ)
従って《カ》は:
　　U_−n = −(−½)ⁿ × (fⁿ − gⁿ) / (f − g) = −(−½)ⁿ U_n　　《キ》

U₋₁, U₋₂, U₋₃, … は U₁, U₂, U₃, … と比べて、絶対値がそれぞれ 1/2, 1/4, 1/8, … となる（符号は、奇数番目の項がプラス、偶数番目の項がマイナス）。バイナッチ数列のプラス番目の項は 1, 2, 6, 16, 44, … なので、対応するマイナス番目の項は 1/2 = 0.5, −2/4 = −0.5, 6/8 = 0.75, −16/16 = −1, 44/32 = 11/8 = 1.375, …。最初の（素朴な）驚きは、値が整数にならないことだろう。フィボナッチ数は、マイナス番目の項も含めて整数値なので…。けれどすぐ「バイナッチはプラス方向に行くとどんどん2倍されていくのだから、マイナス方向に行けば 1/2, 1/4, 1/8, … となるのは当然かも」と思い付く。ところが、よく検討すると、マイナス方向に行くとどんどん半分になるわけではなく、むしろ絶対値は増える。というのも、バイナッチ数列の増大は、大ざっぱに言えば fⁿ によって支配される: f = 1 + √3 = 2.732… の n 乗は 2ⁿ より大きいので、因子 (½)ⁿ = 2⁻ⁿ による急激な減少より fⁿ 本体の増加の方がでかく、トータルでは増加。

さて、加法定理① U_a+b = U_a+1U_b + 2U_aU_b−1 の b を −b に置き換える:
　　U_a−b = U_a+1U_−b + 2U_aU_−(b+1)　　← U_−b−1 = U_−(b+1)
《キ》を使って:
　　U_a−b = U_a+1[−(−½)^b U_b] + 2U_a[−(−½)^b+1 U_b+1]
右辺第2項は 2U_a[−(−½)(−½)^b U_b+1] = U_a[(−½)^b U_b+1] なので:
　　U_a−b = U_a+1[−(−½)^b U_b] + U_a[(−½)^b U_b+1] = (−½)^b[U_aU_b+1 − U_a+1U_b]　　《ク》

〔例〕　a = 7, b = 4, U_a = 328, U_a+1 = 896, U_b = 16, U_b+1 = 44:
　　U₃ = (−½)⁴[328 × 44 − 896 × 16] = (1/16) × 96 = 6
U_a = 328 も U_b = 16 も最大公約数 8 の倍数だが、「8 の倍数」という性質は U_a−b = 6 では保たれない。

バイナッチの U_a−b は一般には倍数関係を保存しないが、2 と互いに素な整数 q に限って言うと（要するに奇数 q に限って言うと）、U_a と U_b がどちらも q の倍数なら U_a−b も q の倍数（ただし a > b）。実際、《ク》の角かっこ内は（U_a の倍数と U_b の倍数の差なので、仮定により q の倍数同士の差であり、従って）q の倍数。係数 (−½)^b は因子 2 の数を減らすが、2 と互いに素な q の倍数性には影響しない（a−b は正の整数なので U_a−b は整数）。

【10】　整理すると…

項の番号の和は倍数・約数関係を保存　Fibonacci 数列でも Bi-nacci 数列でも、第a項・第b項が両方 q の倍数なら、第a+b項も q の倍数。言い換えれば: q が第a項・第b項の約数なら q は第a+b項の約数。

項の番号の差と倍数・約数関係　第a−b項について: Fibonacci 数列では、第a+b項と同様: 無条件で整除性（倍数・約数の関係）が保存される。Bi-nacci 数列では、項の番号の差に関しては、一般には整除性が保存されない。

どちらの数列も整除性を保存する（divisibility sequence）:
「a が d の倍数なら F_a は F_d の倍数」（a, d は正の整数）
　→　「d が a の約数なら F_d は F_a の約数」
　Fibonacci 数列は整除性を強く保存する（strong divisibility sequence）:
　→　「d が a, b の最大公約数なら F_d は F_a, F_b の最大公約数」

数列というものは、「項の番号から、項の値への写像」…とも解釈可能。例えば μ(n) = F_n としよう。このとき上記の用語は、
　　写像 μ は「定義域における a, b の整除関係」を、値域において、どこまで忠実に保存してくれるか？
…という区別を表す。

（続く）

2023-01-23　LLT: Lehmer’s Lemma 1　ギネスに載る素数…？

#数論　#フィボナッチ　#Lucas-Lehmer

新しいメルセンヌ素数が発見されると、場合によっては「世界最大の既知の素数」として、一般メディアでも話題になる。2023年1月現在の最大 [3] は、2018年に発見された 2^82589933 − 1 で、2500万桁に近い。

計算以前に「数字自体を書く」だけでも大変な巨大さで、1ページに1万桁ずつ書くとしても約2500ページ。毎秒1桁ずつ飲まず食わずで数字を書き続けたとして、書き終わるのは10カ月後だ！

そんなでかい数が素数か素数でないか、どうやって判定されるのか？　一般には困難な問題だが、メルセンヌ数に限っては「LLT」という方法がある。やり方自体はシンプル。「なぜその方法で判定できるの？」という理論についても、基本アルゴリズムを完成させた D. H. Lehmer 自身による初等的な証明 [2] があり、フィボナッチ数列のいとこ「バイナッチ数列」と関係している。一連のメモでは、この証明を最終目的地として各ステップをのんびり検討し、興味を引くような話題があれば寄り道もして、いろんな景色を楽しみたい。

【11】　D. H. Lehmer の証明は 3つの Lemmas（補題＝補助命題）と本体から成り、古典的な整数論の範囲に余裕で収まる。難所があるとすれば、二項定理の「一年生の夢」だが、それは取り組む価値のある話題だし、寄り道で見える景色も楽しい（フィボナッチの「夢のもつれ」のバイナッチ版。これは次回に）。まずは最初の Lemma を…

LEMMA 1　3 以上の任意の素数 p を選んで固定する。バイナッチ数列 U_n の第1項以降について、どれかの項が p の倍数になるとして^*11、p の倍数になる最初の項の番号を w としよう。このとき、w の倍数番目の項はどれも p の倍数。それ以外の項は p の倍数ではない。言い換えると、ある項 U_x が p で割り切れるなら、その項の番号 x は w の倍数。

〔例1〕　p = 5 の倍数になる最初の項は、第6項 U₆ = 120（下の表参照）。つまり w = 6。このとき、第6項・第12項・第18項…は、どれも p = 5 の倍数; それ以外の項は 5 の倍数にならない。言い換えると、第○項が 5 の倍数になるとすれば、その項の番号○は w = 6 の倍数。

〔例2〕　p = 11 の倍数になる最初の項は、第5項 U₅ = 44。つまり w = 5。このとき、第5項・第10項・第15項…は、どれも p = 11 の倍数; それ以外の項は 11 の倍数にならない。言い換えると、第○項が 11 の倍数になるとすれば、その項の番号○は w = 5 の倍数。

*11　実はどんな素数 p を選んでも、バイナッチ数列の第1項以降のどれかの項は p の倍数になる（後述）。第0項 U₀ = 0 も p の倍数だが、ここでは話を第1項以降に限る。

バイナッチ数列（第1項～第18項）
各項は直前の2項の和の2倍

n	1	2	3	4	5	6
Un	1	2	6	16	44	120
n	7	8	9	10	11	12
Un	328	896	2448	6688	18272	49920
n	13	14	15	16	17	18
Un	136384	372608	1017984	2781184	7598336	20759040

証明はフィボナッチ版の【5】と同様――「星のらせん」構造に着目すると、U_w が p の倍数のとき、そのまた倍数 U_2w, U_3w, … も p の倍数ってことは明らかだが、「星のらせん」と無関係に、基礎から考えてみる。

加法定理により:
　　U_2w = U_w+w = U_w+1(U_w) + 2(U_w)U_w−1 = (U_w)(U_w+1 + 2U_w−1)
仮定により U_w は p の倍数だから U_w = p × A と書ける（A: 整数）。つまり:
　　U_2w = (p × A)(U_w+1 + 2U_w−1) = p × (A)(U_w+1 + 2U_w−1)
これは確かに p の倍数だ！　U_2w が p の倍数と確定したので U_2w = p × B と書ける（B: 整数）^*12。再び加法定理により:
　　U_3w = U_2w+w = U_2w+1(U_w) + 2(U_2w)U_w−1 = U_2w+1(p × A) + 2(p × B)U_w−1
　　つまり　U_3w = p × [U_2w+1(A) + 2(B)U_w−1]
これで U_3w も p の倍数と確定したので U_3w = p × C と書ける（C: 整数）。再び加法定理により:
　　U_4w = U_3w+w = U_3w+1(U_w) + 2(U_3w)U_w−1 = U_3w+1(p × A) + 2(p × C)U_w−1
　　つまり　U_4w = p × [U_3w+1(A) + 2(C)U_w−1]
これで U_4w も p の倍数と確定したので…

以下同様、延々と続けられるので、U_2w, U_3w, … は、どれも p の倍数。

*12　上の式と見比べると B = A(U_w+1 + 2U_w−1)。 p = 11, w = 5 のケースで検算すると: U_w = 44 = p × 4 なので A = 4, B = 4(U₆ + 2U₄) = 4(120 + 2⋅16) = 608, p × B = 11 × 608 = 6688。これは確かに U_2w = U₁₀ と一致！

問題は「U_w, U_2w, U_3w, … 以外の項は p の倍数にならない」ことの証明。前回の《ク》の式（減法定理）がその鍵となる:
　　U_a−b = (−½)^b[U_aU_b+1 − U_a+1U_b]
a, b が正の整数で a の方が大きいとすると、a−b は正の整数。つまり、上記の左辺はバイナッチ数列のプラス番目の項なので、整数値を持つ。それと等しい右辺も、もちろん同じ整数。右辺の (−½)^b の部分は、符号を無視すると ½ を b 回掛けること（つまり 2 で b 回割ること）だが、その結果が整数ってことは…？

角かっこ内の整数（それを K としよう）が、因子 2 を b 個以上、含んでる――ってことだ！　つまり、
　　K = 2^○ × 奇数
…の形を持ち、指数 ○ が b 以上なので、2 で b 回割っても大丈夫ってこと。

〔例〕　a = 8, b = 5 の場合、次のように ○ = 6 となる:
　　K = U_aU_b+1 − U_a+1U_b = U₈U₆ − U₉U₅ = 896⋅120 − 2448⋅44 = −192 = 2⁶ × (−3)
だから (−½)^b = (−½)⁵ 倍しても（つまり −2 で5回割っても）結果は整数:
　　U_a−b = U₈₋₅ = (−½)⁵[2⁶ × (−3)] = −(2¹) × (−3) = 6　　←　U₃ に一致

今 U_a, U_b がどちらも p の倍数だと仮定すると（p は 3 以上の素数）、U_a = p × A, U_b = p × B と書ける（A, B は整数。前記の A, B とは無関係）。このとき…
　　K = U_aU_b+1 − U_a+1U_b = (p × A)U_b+1 − U_a+1(p × B) = p × (AU_b+1 − U_a+1B)
…も p の倍数なので、K は次の形を持つ:
　　K = 2^○ × p × 整数^*13
この値を (−½)^b 倍すると、2 の指数 ○ は減少するが、それ以外の部分には影響せず、
　　U_a−b = (−½)^bK = ±2^○−b × p × 整数
…の形になって^*14、結果は依然として p の倍数。

*13　この整数は、「K = 2^○ × 奇数」の「奇数」を p で割った商。K は p の倍数なので、この奇数は必ず p で割り切れる（商は 1 以上の奇数）。

*14　先頭の ± は b の偶・奇による。 U_a−b は正の整数なので、この符号がマイナスの場合、K は負の整数。

要するに U_a, U_b が両方 p の倍数で a > b なら U_a−b も p の倍数。このことから、「w の倍数ではない変な番号の項 U_h が、p の倍数になる可能性」を否定できちゃうよ。だってさー、その変な番号 h を w で割って、商が k 余りが j とするとさー、こーなるじゃん？
　　h = kw + j　　← h は w の倍数でないので w で割り切れず、1 以上 w 未満の余り j が発生
仮定の話として、もしも U_h = U_kw+j が p の倍数になるとしたら、何が起きるか…？　U_kw が p の倍数であることは確定しているので、a = kw+j, b = kw と置けば U_a, U_b は両方 p の倍数になり（a > b）、従って U_a−b = U_j も p の倍数になってしまう！

証明の弁護人「異議あり、矛盾ですッ！　p の倍数になる最初の項の番号が w なんだから、w より小さい番号 j に対して U_j が p の倍数ってことは、あり得ません！」

裁判長「異議を認めます。検察は不合理な仮定の話を撤回しなさい」

…ってなわけで「w の倍数ではない変な番号の項 U_h が p の倍数になる可能性」は、否定されちゃう。証明終わりッ。□

この議論はフィボナッチ数列の場合とほとんど同じだが、フィボナッチの場合、上記の p の代わりに、任意の整数 q を使うことができた。バイナッチの場合、p = 2 とすることは、できない。減法定理では因子 2 の数が変動し、U_a, U_b が両方「2 の倍数」だとしても U_a−b も 2 の倍数になる保証がないから…。

Lemma 1 の p（それは 3 以上の素数である）を一般の整数 q に拡張するとしたら、q は因子 2 を持つことができないので、「任意の奇数」に限る必要がある（フィボナッチ数では、倍数・約数関係について強い保存法則が成り立つが、バイナッチ数列ではそれが弱く、条件付きになる）。

（続く）

2023-01-29　美しいアラベスク　風に揺れるかすみ草

#数論　#フィボナッチ　#Lucas-Lehmer　#二項定理

このメモで紹介する景色は、それ自体も素敵だが、フィボナッチ数の同様のパターンと見比べると「深い何か」が感じられる。整数と無理数が織り成す、繊細なアラベスク。

現象は単純なことなのだが、どうしてそうなるのか？という理由が、なかなか味わい深い。

フィボナッチ数列に比べると、バイナッチ数列は無名に近い存在で、そこに隠されているこのパターンは、ほとんど紹介されることもないだろう。半分寄り道になるけど、この秘密の花園を散策してみたい。

【12】　バイナッチ数列は 1, 2 から始めて（あるいは 0, 1 から始めて）、直前の2項の和の2倍を次の項としたもの:
　　1, 2, 6, 16, 44, 120, 328, 896, …
最初の 1 を第1項、2番目の 2 を第2項、3番目の 6 を第3項…と呼び、それぞれ U₁, U₂, U₃, … で表す（もし 0, 1 から始めた場合には 0 を第0項 U₀ とする）。例えば U₇ = 328 は直前の2項 44, 120 の和の2倍。

2 以上の整数のうち、1 と自分自身でしか割り切れない数を素数という。素数番目のバイナッチ数や、その前後のバイナッチ数には、次のような秘密が隠されている。

n が 5 以上の素数（5, 7, 11, 13, …）のとき、U_n の直前か直後のバイナッチ数が n の倍数になる！

フィボナッチと比べバイナッチは、すぐに数がでかくなり、暗算では倍数関係を見通しにくい。でも、大きな数の割り算のことなんて、気にする必要ない。桁が多い数を見てもびびらず、純粋に「倍数関係のパターン」の存在それ自体に注目すると、何ともきれい…。素数の倍数の出現位置が、その素数番目の項の一つ後になったり一つ前になったりするデリケートなパターン。そよ風に揺れるかすみ草のようだ。

バイナッチ数の秘密

n	Un	観察	Un の値は…
1	1
2	2
3	6
4	16		5★の倍数+1
5★	44	5★ は 12k±5型素数	5★の倍数−1
6	120	120 = 24 × 5★	5★の倍数	7★の倍数+1
7★	328	7★ は 12k±5型素数		7★の倍数−1
8	896	896 = 128 × 7★		7★の倍数
9	2448
10	6688	6688 = 608 × 11☆	11☆の倍数
11☆	18272	11☆ は 12k±1型素数	11☆の倍数+1
12	49920	49920 = 3840 × 13☆	11☆の倍数+2	13☆の倍数
13☆	136384	13☆ は 12k±1型素数		13☆の倍数+1
14	372608			13☆の倍数+2
15	1017984
16	2781184		17★の倍数+1
17★	7598336	17★ は 12k±5型素数	17★の倍数−1
18	20759040	= 1221120 × 17★	17★の倍数	19★の倍数+1
19★	56714752	19★ は 12k±5型素数		19★の倍数−1
20	154947584	= 8155136 × 19★		19★の倍数

詳しく言うと、5 以上の素数 n が12の倍数と1違いのとき（つまり12k±1型のとき）、U_n の直前のバイナッチ数 U_n−1 がその n で割り切れる; 素数 n がそれ以外のとき（つまり12k±5型のとき）、直後のバイナッチ数 U_n+1 がその n で割り切れる。本質的には「夢のもつれ」と同じ現象だが、「もつれ」をほどいて、もう一度整理し直してみたい。

〔イメージ音楽　ドビュッシー「アラベスク」第1番　arabesque_debussy.mkv
　　https://invidious.esmailelbob.xyz/watch?v=Yh36PaE-Pf0&local=true
　　https://invidious.protokolla.fi/watch?v=Yh36PaE-Pf0&local=true　より〕

【13】　バイナッチ数列の一般項は、Binet 形式で…
　　U_n = [(1 + √3)ⁿ − (1 − √3)ⁿ] / (2√3)　　《サ》
…となる（ここで n は正の整数）。フィボナッチやバイナッチのような整数の数列の一般項が、無理数が絡んだこんな変てこな形になるってこと自体、初めは意味不明に思えるかもしれない。素朴に「不思議だなぁ」「面白いなぁ」と思っておこう。

《サ》の分子のようなパターンは、「和の n 乗」の展開と「差の n 乗」の展開の結果、プラスとマイナスが打ち消し合って、半分の項は消滅。打ち消し合わない残りの項は、符号が同じものが2個ずつあるので、それぞれ2倍になる。例えば…
　　(x + y)³ = x³ + 3x²y + 3xy² + y³
　　(x − y)³ = x³ − 3x²y + 3xy² − y³
…の上と下を足し合わせれば、右辺の奇数番目の項だけが残って
　　(x + y)³ + (x − y)³ = 2(x³ + 3xy²)
になるし、上から下を引き算すれば、偶数番目の項だけが残って、こうなる:
　　(x + y)³ − (x − y)³ = 2(3x²y + y³)

この具体例は、落ち着いて考えれば当たり前の単純計算だけど、ここで「一年生の夢」が絡んでくる: n を奇数の素数とすると、《サ》の分子から発生する二項係数は、ほとんど全て n の倍数。上記 (x + y)³ の右辺でいえば（n = 3）、両端の2項以外、係数は 3 の倍数になっている（この場合 3 の 1 倍、つまり 3 自身）。別の例として n = 5 の (x + y)⁵ の場合、両端以外の係数は 5, 10, 10, 5 で 5 の倍数だし、n = 7 の (x + y)⁷ の場合、それらは 7, 21, 35, 35, 21, 7 で 7 の倍数。結果として、
　　(x + y)ⁿ − (x − y)ⁿ
の形の展開では、n の倍数を無視すると、二項展開の最後の項だけが残って ≡ 2yⁿ (mod n) となる。

上記のように、この引き算の形では偶数番目の項だけが残るので、両端の項のうち、左端の第1項はもともと消えている。n は奇数の素数なので、項の数 n+1 は偶数: 右端の最後の項は、偶数番目だから、残っている。両端以外は n の倍数なので（一年生の夢）、無視していい。三本線の合同記号 ≡ と丸かっこ内の mod n の意味は「n の倍数の差を無視すると、等しい」あるいは同じことだが「n で割った余りが等しい」（説明）。例えば 23 ≡ 8 (mod 5)。

《サ》の分子は x = 1, y = √3 のケースなので、もし n が奇数の素数なら、《サ》の分数は mod n でこうなる:
　　U_n ≡ 2(√3)ⁿ / (2√3) = (√3)ⁿ / (√3) = (√3)ⁿ⁻¹

分子・分母の 2 を約分した。(√3) を n 個（例えば 5 個）掛け合わせたものを (√3) で割れば、商は (√3) を n−1 個（例えば 4 個）掛け合わせた積になる:
　　(√3)(√3)(√3)(√3)(√3) / (√3) = (√3)(√3)(√3)(√3)

複雑そうな《サ》が、やけにシンプルになった！　しかも、この n は奇数なので n−1 は偶数で、2 で割り切れる。ってことは…
　　U_n ≡ (√3)ⁿ⁻¹ = (√3)^2×(n−1)/2 = [(√3)²]^(n−1)/2 = 3^(n−1)/2　　《シ》

n = 5 の例では (√3)⁴ = [(√3)²]² = 3² となる。ベタに書けば:
　　(√3)(√3)(√3)(√3)(√3) / (√3) = (√3)(√3)(√3)(√3) = (√3)⁴ = 3²

《シ》の U_n ≡ 3^(n−1)/2 (mod n) の右辺は、オイラーの判定基準の形だ: n を 5 以上の素数とすると、3 が n の平方剰余か非剰余かに応じて ≡ ±1 (mod n)。要するに U_n は n の倍数±1。第三補充法則^*15によれば、素数 n が12k±1型なら 3 は平方剰余、12k±5型なら非剰余なので、前者では U_n は n の倍数より 1 大きく、後者では n の倍数より 1 小さい。前者の例として、U₁₁ は 11_☆ の倍数より 1 大きい。後者の例として、U₅ は 5_★ の倍数より 1 小さい; U₇ は 7_★ の倍数より 1 小さい。【12】で観察した「バイナッチ数の秘密」のうち、（第5項以降の）素数番目のバイナッチ数の性質が、これで明らかになった！

*15　教科書的には、3 の平方性は、平方剰余の相互法則から、記号操作で導出される（「遊ばせて」§6末尾の☆☆参照）。われわれはガウス直伝の方法で、相互法則を介さず、直接これを得た。

【14】　引き続き 5 以上の素数（それを p とする）について、今度は第 p 項の次の項――つまり U_p+1――の値を考えてみよう。「夢のもつれ」にあるような「一年生の夢」のバリエーションが発生し、p+1 乗の二項展開では、左端の2項と右端の2項以外は p の倍数となる。

〔例〕　p = 5 のとき 6 乗の二項係数 1, 6, 15, 20, 15, 6, 1 のうち、左端の 1, 6 と右端の 6, 1 以外（つまり 15, 20, 15）は p = 5 の倍数。
同様に p = 7 のとき 8 乗の二項係数 1, 8, 28, 56, 70, 56, 28, 8, 1 について、両端から2番目までを除く各項は p = 7 の倍数。

要するに (x + y)^p+1 を展開した場合、mod p では、両端から2番目までの計4項だけを考えればいい（それ以外の項は p の倍数なので、無視可能）。

(x + y)ⁿ の展開の二項係数について、両端の係数は 1 であること、端から2番目の係数は n であることに注意する。

ところで n = p+1 なので、もちろん n−1 = p。

さて (x + y)ⁿ の展開では、xⁿ を含む項から x⁰ を含む項まで、計 n+1 個の項が生じる。
　　(x + y)ⁿ − (x − y)ⁿ
という引き算の形では、前半の二項展開と後半の二項展開の相互作用の結果、それぞれの奇数番目の項は打ち消し合い、偶数番目の項の2倍だけが残るのだった。n = p+1 は偶数なので、p+1 乗の二項展開では n+1 = p+2 個（つまり奇数個）の項が発生するけど、奇数番目の項は消えてしまうのだから、最初の項と最後の項は消える。「両端から2番目までの計4項だけ考えればいい」ことと「最初の項と最後の項は奇数番目で消滅」というから、二項展開に関しては、左から2番目と右から2番目の計2項だけを考えればいい。それらの項の二項係数は n つまり p+1 であり（なぜなら端から2番目）、係数が掛かっている x^○y^△ は、左から2番目の項では xⁿ⁻¹y¹ つまり x^py（なぜなら n−1 = p）、右から2番目の項では x¹yⁿ⁻¹ つまり xy^p。以上を総合すると:
　　(x + y)^p+1 − (x − y)^p+1 ≡ 2[(p+1)x^py + (p+1)xy^p] (mod p)
　　共通因数をくくり出すと　≡ 2(p+1)xy[x^p−1 + y^p−1] (mod p)
最後の p+1 の部分は ≡ 1 (mod p) なので（なぜなら p+1 を p で割れば 1 余る）、係数としては 1 と同じで省略可能:
　　(x + y)^p+1 − (x − y)^p+1 ≡ 2xy(x^p−1 + y^p−1) (mod p)　　《ス》

〔例〕　x = 3, y = 1, p = 5 のとき《ス》は:
　　左辺　(x + y)^p+1 − (x − y)^p+1 = 4⁶ − 2⁶ = 4096 − 64 = 4032
　　右辺　2xy(x^p−1 + y^p−1) = 2⋅3⋅1(3⁴ + 1⁴) = 6(81 + 1) = 6 × 82 = 492
どちらも 5 で割ると 2 余るので、確かに 4032 ≡ 492 (mod 5)

今、一般項の公式《サ》の n に p+1 を入れると:
　　U_p+1 = [(1 + √3)^p+1 − (1 − √3)^p+1] / (2√3)
この分子は、《ス》で x = 1, y = √3 としたものだから:
　　U_p+1 ≡ {2⋅1⋅√3[1^p−1 + (√3)^p−1]} / (2√3) = 1^p−1 + (√3)^p−1 = 1 + 3^(p−1)/2 (mod p)
ここで (√3)^p−1 の計算は、【13】の (√3)ⁿ⁻¹ の計算と全く同様で、結果は再びオイラーの基準の形に。従って:
　　p が12k±1型素数なら　U_p+1 ≡ 1 + 1 ≡ 2 (mod p)
　　p が12k±5型素数なら　U_p+1 ≡ 1 + (−1) ≡ 0 (mod p)
前者では U_p+1 は p の倍数より 2 大きく、後者では p の倍数に等しい。前者の例として、U₁₂ は 11_☆ の倍数より 2 大きい。後者の例として、U₆ は 5_★ の倍数; U₈ は 7_★ の倍数。【12】で観察した「バイナッチ数の秘密」のうち、（第5項以降の）「素数+1」番目のバイナッチ数の性質が、明らかになった！

【15】　p が12k±1型の素数なら、【13】から U_p ≡ 1 (mod p)、【14】から U_p+1 ≡ 2 (mod p)。この U_p+1 は、バイナッチ数列の性質上、直前の2項の和の2倍だから、次の関係が成り立つ:
　　2(U_p−1 + U_p) ≡ U_p+1 (mod p)
　　つまり　2(U_p−1 + 1) ≡ 2 (mod p)
両辺を 2 で割ると（2 と p は互いに素なので割ってもいい）:
　　U_p−1 + 1 ≡ 1 (mod p)
　　つまり　U_p−1 ≡ 0 (mod p)
これは U_p の一つ手前の項 U_p−1 が p で割り切れること（言い換えれば p の倍数であること）を意味する。

同様に p が12k±5型の素数なら、【13】から U_p ≡ −1 (mod p)、【14】から U_p+1 ≡ 0 (mod p) なので:
　　2(U_p−1 − 1) ≡ 0 (mod p)
　　これを解くと　U_p−1 ≡ 1 (mod p)
これは U_p の一つ手前の項 U_p−1 が p の倍数より 1 大きいことを意味する。

前者の例として、U₁₀ は 11_☆ の倍数。後者の例として、U₄ は 5_★ の倍数より 1 大きい; U₆ は 7_★ の倍数より 1 大きい。

これで【12】で観察した「バイナッチ数の秘密」は、全て明らかになった！

「LLT」の証明に必要なのは、【13】の結論の U_p (mod p) の値と、それに対応する相棒 V_p (mod p) の値だけで、今回のメモの内容は大部分、無関係な寄り道に当たる。けれど、ここを通りがかって、この素敵な景色を楽しまないのは、もったいない。

フィボナッチ数列は、もともと文字通り Arabesque（アラビア風）だった。学術が停滞していた中世ヨーロッパにおいて、進んでいたイスラム圏の数学が研究され、フィボナッチ数列もその結果の一部だったらしい。三角関数もイスラム文化から移入されたものだし、現在の普通の「数字」のコンセプトもアラビア経由でヨーロッパに伝わったようだ（発祥はインドかもしれない）。当時、イスラム文化が花開く一方、ヨーロッパがいわゆる暗黒時代であった背景については、いろいろな研究があるのだろうが、気候が関係していたという説もある。中世ヨーロッパは平均気温が低く、その影響で食糧事情も不安定で、そこから争いや暴政・迷信、ひいては魔女裁判のような宗教的暴走が生じ、科学はあまり進歩しなかった――という解釈も成り立つ。アラビアは暑いイメージがあるが、寒過ぎる当時のヨーロッパと比べると、温暖で快適だったのかもしれない。

（続く）

2023-01-31　LLT: Lehmer’s Lemmas 2 & 3　広い意味での Lucas 数列

#数論　#フィボナッチ　#Lucas-Lehmer

前回、n が 5 以上の素数なら、U_n はその n の倍数 ± 1 になることを見た。例えば n = 5 の場合、U₅ = 44 は、5 の倍数 45 より 1 小さい。

今回、相棒の数列 V_n について似たことを考え、「相棒」の意味も掘り下げてみたい。バイナッチ数列は単に「フィボナッチ数列をひねった変わり種」というだけでなく、もっと大きな山脈の一角だ。

【16】　バイナッチ数列の相棒 V_n は、次のように 2, 2, 8, 20, … と始まり（最初の 2 は第0項）、やはり「直前の2項の和」の2倍が次の項。

バイナッチ数列の相棒（第0項～第17項）

n	0	1	2	3	4	5
Vn	2	2	8	20	56	152
n	6	7	8	9	10	11
Vn	416	1136	3104	8480	23168	63296
n	12	13	14	15	16	17
Vn	172928	472448	1290752	3526400	9634304	26321408

V₅ = 152 は、5 の倍数 150 より 2 大きい。V₇ = 1136 も 7 の倍数より 2 大きく^*16、V₁₁ = 63296 も 11 の倍数より 2 大きい^*17。
　　p が 5 以上の素数のとき、V_p は、p の倍数より 2 大きい？
と予想したくなる…。確かめると p = 13, p = 17 も予想通りになってるし、5 以上に限らず p = 3 の場合の V₃ = 8 も 3 の倍数より 2 大きい。素数でも p = 2 は駄目だけど…。

*16　「7で割った余り」の暗算法として「左端の桁をぶった切って2倍して、2個下の桁に足す」というトリックもある:
　　1136　→　1 を2倍した 2 を「13」に足すと 「15」6
　　できた 156 に対して同じ処理　→　2 を「56」に足すと 「58」　→　7 の倍数より 2 大きい
一般には普通に割り算した方がむしろ手っ取り早いが、これはこれで面白い。左側の桁が小さい場合（1 や 2）、この考え方が役立つこともある。

*17　奇数桁の和 6+2+6 = 14 から偶数桁の和 3+9 = 12 を引いた 2 が、11 で割った余り。

実際、次が成り立つ。

LEMMA 2　p が 5 以上の素数のとき:
　　U_p ≡ ±1 (mod p), V_p ≡ 2 (mod p)
一つ目の合同式の複号については、素数 p が12k±1型ならプラス、12k±5型ならマイナス^†。

〔付記〕　これは「p が 5 以上の素数なら、そうなる」という意味。「それ以外の場合、そうならない」という意味ではない。U_p ≡ ±1 は p = 209 (=11⋅19), p = 901 (=17⋅53) など一部の合成数に対しても成り立つ。V_p ≡ 2 (mod p) は p = 3, 6, 9, 18, 25, 27 などのときも成立。

†　前者は、3 が mod p で平方剰余の場合、後者は非剰余の場合。前者は12k+1型 or 12k+11型ともいえる。後者は12k+5型 or 12k+7型ともいえる。

証明　U_p については前回見た通り。さて V_p について、Binet 形式で書くと:
　　V_p = (1 + √3)^p + (1 − √3)^p
2個の p 乗を展開すると（p は 5 以上の素数なので奇数）、それぞれ p+1 個（つまり偶数個）の項が発生するが、これは奇数番目の項の2倍が残るパターン。次の形になる:
　　2[1^p + ○⋅1^p−2⋅(√3)² + ○⋅1^p−4⋅(√3)⁴ + ○⋅1^p−6⋅(√3)⁶ + … + ○⋅1¹⋅(√3)^p−1]

二項展開の右端にあったはずの (√3)^p と (−√3)^p は、プラスとマイナスの相互作用により打ち消し合う。打ち消し合う理由については「偶数番目の項なので」ともいえるし「符号が反対の数の奇数乗が因子なので」ともいえる。

ここで ○ に当てはまる一つ一つの係数はケースバイケースだが、具体的な値はどうでもいい――「一年生の夢」によりどれも p の倍数だから、角かっこ内の2項目以降は、全部 ≡ 0 (mod p) であり、無いのと同じ。唯一残る1項目については、もちろん 1^p = 1。結局:
　　V_p = (1 + √3)^p + (1 − √3)^p ≡ 2[1^p] ≡ 2 (mod p)
これが証明したいことだった。□

【17】　「相棒」について。とりあえず Binet 形式で考えて、メインの数列の第 n 項が
　　U_n = (fⁿ − gⁿ) / (f − g)
のとき、相棒は
　　V_n = fⁿ + gⁿ
の形。フィボナッチの場合 f = (1 + √5)/2, g = (1 − √5)/2 で、バイナッチの場合 f = 1 + √3, g = 1 − √3 だが、式の形は全く同じなので、どちらの場合も、例えば…
　　U_2n = (f²ⁿ − g²ⁿ) / (f − g)
　　一方　U_nV_n = (fⁿ + gⁿ)(fⁿ − gⁿ) / (f − g) = [(fⁿ)² − (gⁿ)²] / (f − g) = (f²ⁿ − g²ⁿ) / (f − g)
　　従って　U_2n = U_nV_n
…といった、きれいな関係が成り立つ。

Lucas 数列（広い意味での。「狭義」と断らない限り、以下同じ）では、実はメインの数列・相棒の数列の共通設定として、2種類の定数 P と Q がある（この P は、素数を表す小文字の p とは無関係）。ただし、メインの数列の最初の2項に関しては P, Q と無関係に
　　U₀ = 0, U₁ = 1
と約束する（元祖 Fibonacci でも、Bi-nacci でもそうなっている）。さらに、相棒の数列の第0項も P, Q と無関係に
　　V₀ = 2
と約束する。相棒の数列の第1項に、その数列特有の定数 P が現れる:
　　V₁ = P

第0項からスタートする場合、Fibonacci 数列の相棒――狭義の Lucas 数列 L_n ――は 2, 1 と始まる: 第0項が「2」に固定されているのは、上記の通り; 第1項「1」が Fibonacci の P に当たる。一方、Bi-nacci 数列の相棒は 2, 2 と始まるが、最初の「2」は第0項の固定値、次の「2」が Bi-nacci の P に当たる。

問題は第2項以降だが、n が 2 以上のとき、メインの数列も相棒の数列も、次のような、同じパターンの関係を持つ:
　　U_n = PU_n−1 − QU_n−2
　　V_n = PV_n−1 − QV_n−2
言葉でいえば: 1個前の項の P 倍から、2個前の項の Q 倍を引き算する。

こういうパターンは「再帰的」と呼ばれる。「再帰」ってのは「自分（数列）の古い項を使って、自分の新しい項を次々と定義する。その同じパターンがリピートするぜ！」って意味。

フィボナッチの場合、実は P = 1, Q = −1 であり、上の関係は「2個前の項の 1 倍から1個前の項の −1 倍を引く」要するに「2個前の項と、1個前の項を足す」という、おなじみの意味。バイナッチの場合 P = 2, Q = −2 であり、「2個前の項の 2 倍から1個前の項の −2 倍を引く」要するに「2個前の項の2倍と、1個前の項の2倍を足す」言い換えれば「直前の2項の和を2倍する」という意味。

このような数列について、定数 P, Q を含む2次方程式
　　x² − Px + Q = 0
を考え^*18、その2解を f, g とすると、その数列の一般項（メインの数列の第 n 項と相棒の数列の第 n 項）は、前記のような Binet 形式で表される――この事実について、ここでは一般論には立ち入らないけど、われわれは既に2種類の例について、第 n 項の公式を具体的に確かめている: フィボナッチ数列（P = 1, Q = −1）の Binet の公式は、「黄金比」の2次方程式…
　　x² − x − 1 = 0　　解は x = (1 ± √5)/2　← これが f, g になる（実際の計算では文字 u, v を使った）
…に対応する; バイナッチ数列（P = 2, Q = −2）の場合、その「2倍」のような方程式…
　　x² − 2x − 2 = 0　　解は x = 1 ± √3　← これが f, g になる
…から、同様の式が導かれる。

*18　この方程式の「1次の係数」の符号を変えたものが P、「定数項」が Q に当たる（「2次の係数」は1）。方程式側で P の符号がマイナスになってるところがちょっと紛らわしいが、あえて符号を逆にしておくことで P = f + g というシンプルな関係が成り立ち（後述）、むしろ話がすっきりする。

P, Q の設定を変えれば、同様の数列が無限種類、考えられる！

Fibonacci 数列を「楽しいハイキングコースのある山」に例えるなら、一般の Lucas 数列は、その山を含む「広大な山脈」。実は Mersenne 数 M_n = 2ⁿ − 1 も、この大山脈の一つの山に当たる: P = 3, Q = 2 の場合の U_n が、その正体:
　　M₀ = 2⁰ − 1 = 1 − 1 = 0　　←　第0項の初期値（固定）
　　M₁ = 2¹ − 1 = 2 − 1 = 1　　←　第1項の初期値（固定）
　　M₂ = 2² − 1 = 3 = 3⋅1 − 2⋅0　　←　第1項・第0項からの再帰（P, Q が係数）
　　M₃ = 2³ − 1 = 7 = 3⋅3 − 2⋅1　　←　第2項・第1項からの再帰
　　M₄ = 2⁴ − 1 = 15 = 3⋅7 − 2⋅3　　←　第3項・第2項からの再帰
　　M₅ = 2⁵ − 1 = 31 = 3⋅15 − 2⋅7　　←　第4項・第3項からの再帰
　　………
アッと驚く展望だ！　なぜこの再帰的な定義が Mersenne 数になるのか？　対応する2次方程式は:
　　x² − 3x + 2 = 0　　解は x = (3 ± √1)/2　つまり f = 2, g = 1
従って Binet 形式では M_n = (fⁿ − gⁿ) / (f − g) = 2ⁿ − 1 となり、つじつまは合っている。一方、この M_n の相棒を A_n とすると:
　　A_n = fⁿ + gⁿ = 2ⁿ + 1　　← ここでは f = 2, g = 1
こっちは「アンラッキー・セブン」の Fermat 風数列 2, 3, 5, 9, 17, … に他ならない（最初の 2 は第0項）。P = 3, Q = 2 の場合の V_n だ。

数列 M_n に含まれる素数が Mersenne 素数、A_n に含まれる素数が Fermat 素数であり、前者と後者はそれぞれ 2ⁿ − 1 と 2ⁿ + 1 の形を持つ。これらが「相棒」の関係というのは、感覚的にも納得がいくのでは…

【18】　こんなふうに、広い範囲の再帰数列を統一的に扱う観点は、19世紀のフランスの数学者 Édouard Lucas によって発見された（だから Lucas の数列と呼ばれる）。メインの U と相棒の V は、それぞれ第1種・第2種の Lucas 数列と呼ばれることがある。Fibonacci 数列の相棒 L_n は、しばしば単に Lucas 数列（狭義）と呼ばれるが、正式には…
　　第2種 (1, −1)-Lucas 数列　（あるいは: Fibonacci 数列の同伴 Lucas 数列）
…と呼ぶことができる（丸かっこ内の2個の数は P, Q の値）。Mersenne 数は、
　　第1種 (3, 2)-Lucas 数列
に当たる。同様に、われわれが Bi-nacci 数列と呼ぶ U_n は、正式には…
　　第1種 (2, −2)-Lucas 数列
…ということになる。

Lucas–Lehmer test (LLT) は、n 番目の Mersenne 数 M_n が素数か素数でないかを判定するアルゴリズム。19世紀に同じ Édouard Lucas によって原理が発見され、20世紀に D. H. Lehmer によって内容が整理された。現在の「ギネス級」の（＝世界最大の既知の）素数は、どれもこの「LLT」によって発見され、21世紀に入ってからは、平均2年に1回くらいのペースで記録が更新されている（2023年現在）。誰が最初に1億桁を超える素数を発見するか、賞金も懸かってるらしい。

この「LLT」の正しさは、バイナッチ数列を使って証明可能。それに必要な三つの補助命題のうち、三つ目は…

LEMMA 3　どのような素数 p を考えても、バイナッチ数列の第1項から第p+1項の中には、必ず p の倍数が（少なくとも1個は）ある。言い換えると p の新出位置 w は p+1 以下。

〔例1〕　p = 5 は素数なので、第1項 U₁ から第5+1項 U₆ のどれかは 5 の倍数。実際 この6項のうち U₆ = 120 が 5 の倍数（それ以外の5項は 5 の倍数ではない: 【7】の表参照）。言い換えると p = 5 の新出位置は w = 6 であり、w ≤ p+1 を満たす。

〔例2〕　p = 11 は素数なので、U₁ から U₁₂ のどれかは 11 の倍数。実際、これら12項のうち U₅ = 44 と U₁₀ = 6688 が 11 の倍数。言い換えると p = 11 の新出位置は w = 5 であり、w ≤ p+1 を満たす。

証明　U₂ = 2 は 2 の倍数なので、最初の素数 2 について、命題は正しい。U₃ = 6 は 3 の倍数なので、次の素数 3 についても、命題は正しい。従って、p が 5 以上の素数の場合について、命題を証明すればいい。ところが、p が 5 以上の素数の場合、前回見たように、第 p+1 項または第 p−1 項は p の倍数なので、遅くとも p±1 番目の項までには、p の倍数が現れる。□

具体的に、素数 p が12k±5型なら第 p+1 項が p の倍数になり（【14】参照）、素数 p が12k±1型なら第 p−1 項が p の倍数になるのだった（【15】参照）。これは、必ずしも「その項になって、初めて p の倍数になる」という意味ではない。上記〔例2〕の p = 11 を考えると、確かに第 p−1 項（つまり第10項）は p の倍数だが、もっと前の第5項も p の倍数。

けれど Lemma 1 によって、U_x が p の倍数なら x は w の倍数なので、新出位置 w は x = p±1 の約数に限られる（複号の選択は上記の通り）。もちろん p±1 自体も、自分自身の約数: 〔例1〕の p = 5 の場合のように、w = p±1 になることもある。

Fibonacci 数列においても、任意の素数 p がどこかの項で（遅くとも p+1 番目の項までには）因数として登場する; p が 7 以上の場合、p が10k±3型か10k±1型かに応じて、F_p+1 ないし F_p−1 が p の倍数（「夢のもつれ」）。この場合も p±1 が新出位置 w とは限らないが、出現位置の法則から、やはり w は p±1 の約数。Fibonacci 数列と Bi-nacci 数列では、第 w 項で新出した素因数 p は第 2w, 3w, 4w, … 項でも再出現し、結局、任意の素数 p に対して、p で割り切れる項が無限個、存在する。

同じ Lucas 数列でも、アンラッキー・セブンの数列――P = 3, Q = 2 の場合の V_n――では、永遠に一度も出現しない「不運」な素因数が存在する（p = 7 や p = 23 など）。この場合、どこまで行っても 7 で割り切れる項は一つもない。「どの素因数も出現する」というのは「どの数列でも成り立つ当たり前のこと」じゃなく、特別な性質なんだね！

素数 p が「12k±1」型か「12k±5」型かという繊細な区別に対応して、因数 p の出現位置が、p 番目の項の一つ前・一つ後と微妙にずれる。「そよ風に揺れるかすみ草」といった風情。前回、この風景に見とれて、証明と関係ない場所をフラフラ散策してしまったが、結果的には、その寄り道の副産物として Lemma 3 は自然に得られた（D. H. Lehmer 自身の証明法は、もっとコンパクトにまとまっている）。

（続く）

2023-02-03　Lucas 数列という展望台　「ハイハイ、証明できました。んで？」

#数論　#フィボナッチ　#Lucas-Lehmer

真面目な人は、レシピを頭で覚えようとする。「ラズベリーが2カップ、チアシードが大さじ…え～と何杯だったっけ。それから…う～ん、数がいっぱいあって、覚えられないよぉ。もう1度、料理の本を確認しなきゃ…」

慣れてる人は、むしろいいかげん。感覚的に「これはレモンを加えるべきだな…。濃縮還元なんて駄目駄目。こういうときは、新鮮なレモンをその場で搾って。（計量スプーンなんて使わず目分量で）チアシードを適当に入れてっと…。これで完成、10分でお手軽♪」

肝心なのは「レシピ・公式」より「感覚・観点」だろう。森の構造を理解せず、木の細かい位置を一つ一つ個別に覚えようとしても、森の中で迷うばかり…。見通しが利かず、途方に暮れる。どの道がどこにつながってるか、全体像が分かってれば、木の位置なんて考えるまでもなく、普通に歩ける。

「広い意味での Lucas 数列」は、そんな「森」の一つかもしれない。具体例を通じて、この観点の一端に触れてみたい。題材は、本題の「LLT」の証明でも使われる内容。それ自体が好奇心を刺激するだけでなく、ツールとしても役立って一石二鳥。

【19】　教科書を読んでいると、いろいろな理由から「木を見て森を見ず」の状態を強いられることがある。この話も、そんな「無味乾燥な教科書」のように始まる…

バイナッチ数列の第 a 項 U_a と、第 b 項 U_b の積を考える。Binet 形式で第 n 項は U_n = (fⁿ − gⁿ) / (2√3) だから:
　　U_aU_b = [(f^a − g^a) / (2√3)] × [(f^b − g^b) / (2√3)]
この分数の掛け算を行うと、分母は (2√3)² = 2²(√3)² = 4⋅3 になって:
　　U_aU_b = (f^a − g^a)(f^b − g^b) / 12　　《タ》
両辺を12倍して分母を払うと:
　　12U_aU_b = (f^a − g^a)(f^b − g^b) = f^af^b − f^ag^b − g^af^b + g^ag^b　　《チ》

一方、おなじみ相棒の数列について V_n = fⁿ + gⁿ だから:
　　V_aV_b = (f^a + g^a)(f^b + g^b) = f^af^b + f^ag^b + g^af^b + g^ag^b　　《ツ》
《チ》と《ツ》の左辺同士・右辺同士を足し合わせると、右辺第2・第3項は打ち消し合って、こうなる:
　　12U_aU_b + V_aV_b = 2(f^af^b + g^ag^b) = 2(f^a+b + g^a+b)　　《テ》
ところで V_n = fⁿ + gⁿ に n = a+b を代入すると…
　　V_a+b = f^a+b + g^a+b
…なので、《テ》は次を意味する:
　　12U_aU_b + V_aV_b = 2V_a+b
左辺と右辺を入れ替えて両辺を 2 で割ると、次の公式を得る。

相棒の加法定理（バイナッチ版）　V_a+b = (12U_aU_b + V_aV_b)/2

ハイハイ、なんか公式が証明できました。んで？

（やれやれ、どーせ、今度はこの公式を使った計算練習でもさせられるんだろ…）

【20】　もちろん数値例での確認も大切だが、ここでちょっと別のことを考えてみたい。――この公式の「12」って、結構でかい係数だけど、一体どこからこんな数が出て来たんだろ？

まぁ、大した疑問でもないけど…。導出過程をたどると、《タ》で、Binet 形式の分母^*19の f − g = 2√3 を平方したのが「12」の発生原因。要するに (f − g)² が 12 だから「12」が出てきた。それだけのこと。だが、待てよ…。そもそもこの f, g は、対応する2次方程式…
　　x² − Px + Q = 0　（ここで P = 2, Q = −2）
…の2解だぞ。解と係数の関係^*20を考えると…
　　f + g = P　そして　fg = Q
…となって、次が成り立つ^*21:
　　(f − g)² = (f + g)² − 4fg = P² − 4Q

ってことは、この「12」って数は、2次方程式 x² − Px + Q = 0 の判別式 D = (−P)² − 4⋅1⋅Q の値でもある、ってことか。ふーむ…

*19　一般の場合について、Binet 形式の分母が f − g になることをまだ証明していないが、フィボナッチの公式の分母 √5 は確かに f = (1 + √5)/2 と g = (1 − √5)/2 の差 f − g だし、バイナッチの公式の 2√3 も確かに f = 1 + √3 と g = 1 − √3 の差になってる。

*20　2次式 A(x) = x² − Px + Q が与えられたとして、それを2個の1次式の積に分解したものを B(x) = (x − f)(x − g) とすると、前者と後者は同一なのだから、B(x) = 0 の2解 x = f, g は、もちろん A(x) = 0 の解でもある――ここで x = f が B(x) = 0 の解であることは、実際にその数値を代入すれば明白:
　　B(f) = (f − f)(f − g) = 0⋅(f − g) = 0
同様に x = g も解。今、B(x) を展開すると:
　　B(x) = x² − gx − fx + fg = x² − (f + g)x + fg
これが A(x) と同一なのだから、両者の1次の係数を比較すると P = f + g、定数項を比較すると Q = fg。

*21　借金 2 の「マイナス平方」会社が、さらに 2 を前借りして「プラス平方」に見せかける粉飾決済を行い、後から 4 を返す羽目に！
　　(f − g)² = f² − 2fg + g² = (f² + 2fg + g²) − 4fg = (f + g)² − 4fg
方程式の「解についての式」をその方程式の「係数についての式」に変換したいとき、しばしばこういうパズルみたいな操作が行われる。2次方程式の場合は比較的簡単だが、3次方程式だと大変なことに…ｗ

じゃあ「12」の部分を対応する D に置き換えてやれば、任意の Lucas 数列（広い意味での）について、同様の公式が成り立つんじゃね？

（一般の場合の Binet 形式がまだ確立されてないことに、とりあえず目をつぶれば…だけどｗ）

元祖 Fibonacci 数列 F_n も、広い意味での Lucas 数列の一つ（Fibonacci 数列の相棒 L_n が狭義の Lucas 数列）。Fibonacci の場合、元祖 Binet の公式はハッキリしていて、分母が √5 なので、それを平方すると「5」。【19】と同様に考えると（全く同様なので途中計算略）、「12」が「5」に置き換わって、こうなる。

相棒の加法定理（フィボナッチ版）　L_a+b = (5F_aF_b + L_aL_b)/2

再び分析すると、この f, g は、
　　x² − Px + Q = 0　（ここで P = 1, Q = −1）
の2解なんだから、f + g = P = 1, fg = Q = −1。ってことは:
　　(f − g)² = P² − 4Q = 1² − 4⋅(−1) = 5
この数は、対応する2次方程式 x² − x − 1 = 0 の判別式の値 D に等しい。

なんとなく…何かが見えてきたような…

任意の Lucas 数列について、Binet 形式が同じ U_n = (fⁿ + gⁿ) / (f − g), V_n = fⁿ + gⁿ になることを便宜上、事実と認めるなら、どの数列についても「相棒の加法定理」は次の形になるっぽい。
　　V_a+b = (DU_aU_b + V_aV_b)/2　　《ト》

Binet 形式の分母を考えるまでもなく、最初から単に D = P² − 4Q としてもいい。要するに…【19】のような公式は、上位バージョン《ト》から派生している。フィボナッチでは D = 5、バイナッチでは D = 12（これらの値は対応する P, Q によって決まる）。【19】自体はつまらなくても、この派生関係・舞台裏の構造は、ちょっと面白い。視野が広がる感じ？

実用上の観点から言えば、いちいち【19】の公式や上記の「相棒の加法定理」を覚えるまでもなく、それらは全部、上位互換の《ト》から自然に出てくる。頑張って「木」を一本ずつ覚えるより、「森」の構造を理解した方が早い！

(I)　一般論として x² + bx + c = 0 の判別式 D = b² − 4c は、2解の差の平方（b, c は、その世界での任意の係数）。

(II)　P, Q をパラメーターとする Lucas 数列の一般項は、2次方程式 x² − Px + Q = 0 の2解 f, g を使って Binet 形式で表されるが、それに関連して (f − g)² に由来する数を含む式では、その数は対応する D = P² − 4Q に等しい。

この二つは、もちろん無関係な話じゃなく、(II) は (I) とつながっている。

〔例1〕　フィボナッチ数列は F_n = 1, 1, 2, 3, … その相棒は L_n = 1, 3, 4, 7, …。相棒の第3項 L₃ = 4 と第4項 L₄ = 7 を使うと（a = 3, b = 4）:
　　L₃₊₄ = (5F₃F₄ + L₃L₄)/2 = (5⋅2⋅3 + 4⋅7)/2
　　= (30 + 28)/2 = 58/2 = 29　←　確かに L₇

〔例2〕　バイナッチ数列は U_n = 1, 2, 6, 16, … その相棒は V_n = 2, 8, 20, 56, …。相棒の第3項 V₃ = 20 と第4項 V₄ = 56 を使うと（a = 3, b = 4）:
　　V₃₊₄ = (12U₃U₄ + V₃V₄)/2 = (12⋅6⋅16 + 20⋅56)/2
　　= (1152 + 1120)/2 = 2272/2 = 1136　←　確かに V₇

【21】　今、バイナッチ数列の第 2n 項 V_2n を考える。上記で a = b (= n) となる特別な場合に当たる。
　　V_2n = f²ⁿ + g²ⁿ　　《ナ》
…の右辺は、次の右辺と似ている（項が一つ多いか少ないかだけの違い）:
　　(V_n)² = (fⁿ + gⁿ)² = (fⁿ)² + 2fⁿgⁿ + (gⁿ)² = f²ⁿ + g²ⁿ + 2(fg)ⁿ　　《ニ》
ところが（再び解と係数の関係により） fg = Q = −2 なんだから、《ニ》はこうなるよね:
　　(V_n)² = f²ⁿ + g²ⁿ + 2(−2)ⁿ
右端の項を移項して、左辺と右辺を入れ替えると:
　　f²ⁿ + g²ⁿ = (V_n)² − 2(−2)ⁿ
これを《ナ》に代入して:
　　V_2n= (V_n)² − 2(−2)ⁿ　　《ヌ》

n 乗される (−2) の部分は、積 fg ――つまり数列を特徴付ける定数 Q ――に他ならない（言い換えれば、対応する2次方程式の定数項）。単に「バイナッチというマイナーな数列の相棒の第 2n 項」と思うと、応用範囲の狭い「木の話」のようだが、(−2) を Q に置き換えるだけで、任意の Lucas 数列（広義）についての「森の話」になる。フィボナッチの場合 Q = −1 だから、《ヌ》に当たる式は:
　　L_2n = (L_n)² − 2(−1)ⁿ
(−1)ⁿ は n が偶数なら +1、奇数なら −1。だから −2(−1)ⁿ は、n が偶数なら −2、奇数なら +2。従って、こう書くこともできる。

相棒の第 2n 項（フィボナッチ版）　L_2n = (L_n)² ∓ 2　複号は n の偶・奇に対応

なかなか素敵な式だ！　例えば、奇数番目の項 L₅ = 11 を使って:
　　L₁₀ = (L₅)² + 2 = 11² + 2 = 121 + 2 = 123　←　確かに L₁₀
調子に乗ってもう1回2倍すると（今度は n = 10 が偶数なので）:
　　L₂₀ = (L₁₀)² − 2 = 123² − 2 = 15129 − 2 = 15127
そうしたければ、簡単な計算で、何度でも項の番号を2倍にできる:
　　L₄₀ = (L₂₀)² − 2 = 15127² − 2 = 228826127
　　L₈₀ = (L₄₀)² − 2 = 228826127² − 2 = 52361396397820127

ここで「相棒の加法定理」を使えば L₈₀ と L₂₀ から L₁₀₀ を求めることもできる。「直前の2項の和が次の項」という定義に従って第100項を計算したら100回くらい足し算が必要だけど、この方法なら10ステップくらいの計算で済みそうだ（でかい数の2乗の計算が必要だけど、でかい数の足し算100回よりは良いだろう）。何の役に立つのかなんて関係ない。純粋に面白い！

ところで、式《ヌ》自体は、もう少し整理できる:
　　V_2n= (V_n)² − 2(−2)ⁿ = (V_n)² + (−2)(−2)ⁿ = (V_n)² + (−2)ⁿ⁺¹
n が偶数なら n+1 は奇数で (−2)ⁿ⁺¹ は負、n が奇数ならその反対で (−2)ⁿ⁺¹ は正。従って、こうなる。

相棒の第 2n 項（バイナッチ版）　V_2n = (V_n)² ∓ 2ⁿ⁺¹　複号は n の偶・奇に対応

〔例3〕　n = 3（奇数）の場合。表を見ると V₃ = 20 なので:
　　V₆ = 20² + 2³⁺¹ = 400 + 16 = 416　←　確かに V₆ の値に

〔例4〕　n = 4（偶数）の場合。 V₄ = 56 なので:
　　V₈ = 56² − 2⁴⁺¹ = 3136 − 32 = 3104　←　確かに V₈ の値に

【22】　最後に、デザートの「シャーベット」。

《ニ》で見たように:
　　(V_n)² = f²ⁿ + g²ⁿ + 2(fg)ⁿ
一方、《チ》で a = b = n とすると:
　　12(U_n)² = f²ⁿ + g²ⁿ − 2(fg)ⁿ
左辺同士・右辺同士について、上の式から下の式を引き算すると:
　　(V_n)² − 12(U_n)² = 4(fg)ⁿ　　《ネ》

《ネ》の「12」は、上位バージョンでは D = P² − 4Q だった。フィボナッチ数列の場合、D = 5 そして fg = Q = −1 だから、《ネ》に当たる式は:
　　(L_n)² − 5(F_n)² = 4(−1)ⁿ　つまり n の偶・奇に応じて = ± 4

これは「土星の輪っかとフィボナッチ」で観察した Pell 風の恒等式（シャーベット）に他ならない！　それ自体として美しいばかりか、理論上、重要な意味を秘めているのだった――すなわち、フィボナッチ数（フィボナッチ数列に含まれる数）とそうでない数を見分ける方法を与えてくれる。細かい計算をするまでもなく、Lucas 数列（広義）というより広い文脈の中で、その式が自然に出てきた。

バイナッチ数列の場合、fg = Q = −2 なので、《ネ》はこうなる（4 = (−2)² に注意）。
　　(V_n)² − 12(U_n)² = 4(−2)ⁿ = (−2)²(−2)ⁿ = (−2)ⁿ⁺²

Pell 風の恒等式（バイナッチ版）　(V_n)² − 12(U_n)² = (−2)ⁿ⁺² = ±2ⁿ⁺²　複号は n の偶・奇に対応

かわいい式だ。

〔例5〕　バイナッチ数列は U_n = 1, 2, 6, 16, 44, … その相棒は V_n = 2, 8, 20, 56, 152, …。
第2項について（n = 2 は偶数）:
　　8² − 12⋅2² = 64 − 12⋅4 = 64 − 48 = 16　←　確かに (−2)²⁺² = +2⁴ に等しい
第3項について（n = 3 は奇数）:
　　20² − 12⋅6² = 400 − 12⋅36 = 400 − 432 = −32　←　確かに (−2)³⁺² = −2⁵ に等しい

ゴチャゴチャして分かりにくい現象。より高い観点から眺めるとき、それが突然単純で当たり前のことになって、すっきり透明に見通せる。――数論には、時々そんなカタルシスがある。このメモの例はそこまで感動的でもないけど、「広い意味での Lucas 数列」という展望台から眺めると、雑然とした公式たちを統一的に理解できる。フィボナッチとバイナッチというたった2種類の例を扱っただけだし、理論面も大ざっぱだが、「Lucas 数列」という観点を垣間見ることができた。既に研究し尽くされている初等的な事柄でも、自分で試行錯誤して歩いてみるのは、楽しい！

次回はいよいよ「LLT」の証明へ…。（続く）

2023-02-06　メルセンヌ数と「LLT」（前編）

#数論　#フィボナッチ　#Lucas-Lehmer

2 以上の数（自然数）のうち、1 と自分自身以外の数では割り切れないものを素数という。30 以下の素数は、次の10個:
　　2, 3, 5, 7,
　　11, 13, 17, 19,
　　23, 29

Mersenne（メルセンヌ）数は、「n 個の 2 を掛け合わせて 1 を引く」という形を持つ。
　　n = 3 の場合　2 × 2 × 2 − 1 = 8 − 1 = 7
　　n = 4 の場合　2 × 2 × 2 × 2 − 1 = 16 − 1 = 15
　　n = 5 の場合　2 × 2 × 2 × 2 × 2 − 1 = 32 − 1 = 31
「n 個の 2 の積」を簡略に 2ⁿ と書き、2 の n 乗と呼ぶ。「n 番目」の Mersenne 数 M_n とは、次の数:
　　M_n = 2ⁿ − 1

20世紀中頃まで、人類が知っている最大の素数は M₁₂₇ = 2¹²⁷ − 1 だった。この数は39桁。
　　M₁₂₇ = 170 141183460469 231731687303 715884105727
1876年に Édouard Lucas によって、素数であることが確かめられたという。1952年以降、コンピューターを使って100桁を超える Mersenne 素数が次々と発見され、今現在も愛好家によるさらなる探索が日夜続けられているが、M₁₂₇ は「コンピューターを使わず、筆算で発見された最大の Mersenne 素数」。この記録はまず破られないだろう。

こんな大きな数が素数だってことを Lucas はどうやって調べたのだろうか。「2, 3, 4, 5, … で一つずつ割ってみて、どれでも割り切れないことを確かめる」という単純な方法では、たとえ現代のスーパーコンピューターを使っても時間がかかり過ぎる！

【23】　2番目・3番目・5番目・7番目・11番目…などの、素数番目の Mersenne 数は、それ自身、素数になることがある。トータルでは、素数にならないことの方が多い^*22。
　　M₂ = 2² − 1 = 4 − 1 = 3　これは素数
　　M₃ = 2³ − 1 = 8 − 1 = 7　これは素数
　　M₅ = 2⁵ − 1 = 32 − 1 = 31　これは素数
　　M₇ = 2⁷ − 1 = 128 − 1 = 127　これは素数
　　M₁₁ = 2¹¹ − 1 = 1024 − 1 = 1023 = 11 × 93　これは素数でない（11で割り切れる）

素数番目以外の Mersenne 数は、決して素数にならない。
　　M₄ = 2⁴ − 1 = 16 − 1 = 15　これは素数でない（3や5で割り切れる）
　　M₆ = 2⁶ − 1 = 64 − 1 = 63　これは素数でない（3や7で割り切れる）
　　M₈ = 2⁸ − 1 = 256 − 1 = 255　これは素数でない（3や5で割り切れる）
　　M₉ = 2⁹ − 1 = 512 − 1 = 511 = 7 × 73　これは素数でない（7で割り切れる）

従って「Mersenne 素数を探したい」という観点からは、素数番目の Mersenne 数だけを考えればいい。

*22　　M₁ ～ M₅₀₀ の範囲に「素数番目」のものは95個あるが、そのうち値が素数になるのは12個だけ（Lucas が研究した M₁₂₇ がこの範囲では最大）。13個目の Mersenne 素数は M₅₂₁ で157桁。

今 p を 3 以上の素数として、p 番目の Mersenne 数 M_p が素数かどうか判定したいとする。Lucas–Lehmer test（ルュカ・レーマー・テスト）、略して「LLT」では、この判定の目的で次の「4 から始まる数列」が使われる。
　　S₁ = 4
　　S₂ = 4² − 2 = 16 − 2 = 14
　　S₃ = 14² − 2 = 196 − 2 = 194
　　S₄ = 194² − 2 = 37636 − 2 = 37634
　　S₅ = 37634² − 2 = 1416317956 − 2 = 1416317954
　　………
以下同様に、直前の項の2乗から 2 を引くことで次々と項を作ったとして:
　　◆　この数列の p−1 番目の項 S_p−1 が M_p で割り切れれば、その M_p は素数！
　　◆　割り切れなければ、その M_p は素数ではない！
例えば M₁₂₇ のケース（前述の39桁の数）では p−1 = 126 だから、S₁₂₆ が M₁₂₇ で割り切れれば M₁₂₇ は素数！という結論になる――この判定法が成り立つ理由が、以下の本題。

ところで、上記の数列 S は項ごとに「2乗」という計算があるので、すっごい勢いでどんどん大きくなる:
　　S₂ = 14 > 10 = 10¹
　　S₃ = 14² − 2 = 194 > (10¹)² = 10²
　　S₄ = 194² − 2 = 37634 > (10²)² = 10⁴　以下同様に
　　S₅ = 1416317954 > 10⁸
　　S₆ = 2005956546822746114 > 10¹⁶
　　S₇ = 4023861667741036022825635656102100994 > 10³²
　　………

〔参考〕　「2 を引く」という部分は、10², 10⁴, 10⁸, … との大小関係に影響しない:
　　S₂ = 14 ≥ 10¹ + 4 > 10¹
　　S₃ = 14² − 2 ≥ (10¹ + 4)² − 2 = (10¹)² + 2⋅(10¹)⋅4 + 4² − 2 > 10² + 4 > 10²
　　S₄ = 194² − 2 ≥ (10² + 4)² − 2 = (10²)² + 2⋅(10²)⋅4 + 4² − 2 > 10⁴ + 4 > 10⁴
一般に S_k が 10^2k−2 + 4 以上なら、S_k の2乗は、10^2k−2 の2乗と比べて最低でも +96 なので、−2 があっても不等号は余裕で維持され、S_k+1 も 10^2k−1 + 4 以上（cf. [4], §3, p. 340）。上界も簡単に確かめられ、k = 2, 3, 4, … に対して 10^2k−2 < S_k < 10^2k−1 が成立（これは k = 1 に対しても真: 10^1/2 = √10 < S₁ = 4 < 10）。結局 S_k は 2^k−2 桁より大きく 2^k−1 桁以下。

M₁₂₇ の判定について「S₁₂₆ が M₁₂₇ で割り切れれば素数！」と言っても、S₁₂₆ は、大ざっぱに「10 の 2¹²⁴ 乗」と「10 の 2¹²⁵ 乗」の間にある数。――1兆の1兆倍を1𥝱（じょ）または1秭（し）という。そのまた1兆倍を1澗（かん）という。S₁₂₆ は、ざっと 10 の「25澗」乗。値の桁数が「25澗」。つまり 1 の後ろに 0 を「25澗」個並べたくらいの桁数。1ページに1兆桁ずつ書けるとしても、この数を記すには、1兆ページの本が25兆冊必要！

桁数自体がそれなので、その桁数の数が表す意味…というのは、もはや訳が分からない。数字が宇宙に入り切ることは確かだが、それが表す値は、観測可能な宇宙にある原子の総数（推定 10⁸⁰ ～ 10⁹⁰ 個？）よりはるかにでかい。ちなみに:
　　S₆ = 200京 5956兆 5468 2274 6114
　　S₇ = 4澗 0238溝 6166穣 7741𥝱 0360垓 2282京 5635兆 6561 0210 0994

従って S₁₂₆ をそのまま計算に使うのは、現実的でない。さいわい判定に必要なのは「S₁₂₆ を M₁₂₇ で割った商」ではなく「M₁₂₇ で割り切れるかどうか」だけ。言い換えると「M₁₂₇ で割った余り」が分かれば十分。M₁₂₇ は「たった」39桁の数なので、途中計算でそれより大きな数ができたら、いつでも M₁₂₇ で割った余りで置き換えれば、再び39桁以下になる。この39桁の余りは、2乗しても最大77桁にしかならず、S₁ = 4 から始めて「2乗して 2 を引く → 最大77桁 → 39桁で割った余りを計算して39桁以内にする」というループを 125 回繰り返して S₁₂₆ を求めることは、頑張れば手計算でも可能。Édouard Lucas は（細部は異なるとしても）この種の計算により「M₁₂₇ は素数」と判定したのだろう。

実際に試すと、こんな感じ:
　　S₁ = 4
　　S₂ = (S₁)² − 2 = 14
　　S₃ = (S₂)² − 2 = 194
　　S₄ = (S₃)² − 2 = 37634
　　S₅ = (S₄)² − 2 = 1416317954
　　S₆ = (S₅)² − 2 = 2005956546822746114
　　S₇ = (S₆)² − 2 = 4023861667741036022825635656102100994
　　S₈ = (S₇)² − 2 = 16191462721115671781777559070120513664958590125499158514329308740975788034
この74桁の数を M₁₂₇ で割ると、余りは39桁に:
　　 ≡ 148295852275705128589952510455019292911 (mod M₁₂₇)
同様に進めて:
　　S₉ ≡ (S₈)² − 2 ≡ 17934813421766634732012365957609373869 (mod M₁₂₇)
　　………
　　S₁₂₄ ≡ (S₁₂₃)² − 2 ≡ 87676307088191859152273331489412200665 (mod M₁₂₇)
　　S₁₂₅ ≡ (S₁₂₄)² − 2 ≡ 18446744073709551616 (mod M₁₂₇)
この右辺の20桁の数（余り）はちょうど 2⁶⁴ なので、最後にもう1回、2乗して 2 を引くと:
　　S₁₂₆ ≡ (S₁₂₅)² − 2 = (2⁶⁴)² − 2 = 2¹²⁸ − 2
これは M₁₂₇ = 2¹²⁷ − 1 のちょうど 2 倍なので S₁₂₆ は ≡ 0; つまり M₁₂₇ で割り切れる。

【24】　なぜこの方法で「Mersenne 数が素数かどうか」判定できるのか？

その研究がこのハイキングの目的地だが、歩き始める前に、コースの概要やポイントを把握しとくのが賢明だろう。
　　「山を登る時　ルートもわからん！　頂上がどこにあるかもわからんでは　遭難は確実なんじゃ！」

「LLT」の証明には、次の二つの要素がある。似てるようで紛らわしいが、この二つを区別しないと混乱が生じる。

第一に、M_p が素数なら「素数だ！」という Yes 判定が出る（つまり S_p−1 が M_p で割り切れる）――ということ。

第二に、Yes 判定が出た場合（つまり S_p−1 が M_p で割り切れる場合）、M_p は素数だと言い切れる――ということ。

第一を証明しただけだと「素数なら Yes 判定が出るのはいいとして、素数でなくても Yes 判定が出るケースがあるかも…」という疑惑が残る。つまり、素数でないくせに、この素数判定テストに合格してしまうニセ素数――正式名称、擬素数（ぎそすう）――の問題が生じる。

第二を証明できれば、Yes 判定は100%信頼できることになり、例えば M₁₂₇ が素数であることは確定する。でも第二だけだと、今度は逆に「Yes 判定で素数確定はいいとして、本当は素数なのに No 判定が出てしまうことがあるかも…」という疑惑が残る。

医学検査っぽい用語で言えば、前者は偽陽性の問題、後者は偽陰性の問題。教科書っぽい用語で言えば、S_p−1 が M_p で割り切れることの必要性と十分性。

すなわち、われわれの進むべきルートは縦走コースで、二つの山に登る。まず M_p が素数と仮定して（p ≥ 3）、そのときには S_p−1 が M_p で割り切れることを示す――これが第一の山で「Mersenne 素数は必ず LLT で検出される＝偽陰性の心配はない」という証明。次に S_p−1 が M_p で割り切れると仮定して、そのときには M_p が素数であることを示す――これが第二の山で「LLT で検出されるのは Mersenne 素数だけ＝偽陽性の心配はない」という証明。

どっちの証明でも、フィボナッチ数列のいとこ「バイナッチ数列」が活躍する。

【25】　実は、数列 S_n は、バイナッチの「相棒」数列 V_n と「ある意味で同じ」ものだが、項の番号が、急激に加速される: S の第1項・第2項・第3項・第4項…は、因子 2 の個数の違いを無視すると、V の第2項・第4項・第8項・第16項…に当たる。

数列 S の最初の5項と数列 V の関係

n	Sn	B = 2n	VB	VB は Sn の何倍？
1	4	2	8	2 = 21
2	14	4	56	4 = 22
3	194	8	3104	16 = 24
4	37634	16	9634304	256 = 28
5	1416317954	32	92819813433344	65536 = 216

この表から容易に予想がつくだろうが、次の番号 n = 6 に対応する項 S₆ は、V₆₄ に等しい――2³² 倍の違いを無視すると。ここで V₆₄ という項の番号「64」は、2ⁿ つまり 2⁶ に当たる。2³² 倍という指数「32」は、2ⁿ⁻¹ つまり 2⁵ に当たる。

さらに次の番号 n = 7 に対応する項 S₇ は、V₁₂₈ に等しい――2⁶⁴ 倍の違いを無視すると。ここで V₁₂₈ という項の番号「128」は、2ⁿ つまり 2⁷ に当たる。2⁶⁴ 倍という指数「64」は、2ⁿ⁻¹ つまり 2⁶ に当たる。

以下同様で、一般に S_n は V の第 2ⁿ 項に等しい――倍率 2^C の違いを無視すると。ここで C = 2ⁿ⁻¹。

〔注〕　「M_p で割り切れるかどうか？」という判定に関しては、「2倍・4倍・8倍・16倍…などの違い」を無視しても、判定結果に影響しない（後述）。つまり S のある項が M_p で割り切れるかどうかを考える代わりに、その項に対応する V の項が M_p で割り切れるかどうかを考えてもいい…ってこと。

数列 S と数列 V の上記の関係は、次のように整理される（ここでは、この等式を暫定的に認めておき、次回にちゃんと証明する）。
　　(2^C)S_n = V_B　ただし C = 2ⁿ⁻¹, B = 2ⁿ　　《ハ》
　　　　B は V の「項の番号」で 2, 4, 8, 16, … という値を持つ
　　　　「V_B は S_n の何倍？」という「倍率」が 2^C

【26】　第一の山に登るため、M_p が素数だと仮定しよう（p は 3 以上の素数）――山頂に当たる目的地は「S_p−1 は M_p で割り切れる！」ってのを示すことだった。《ハ》で n = p−1 とすると:
　　(2^C)S_p−1 = V_B　ただし C = 2^(p−1)−1 = 2^p−2, B = 2^p−1

仮定により M_p は 7 以上の素数。S_p−1 がその素数 M_p で割り切れるなら、S_p−1 を2倍・4倍・8倍・16倍…（一般に 2^t 倍。t は 0 以上の整数）したものも同じ素数で割り切れるし、S_p−1 がその素数で割り切れないなら、S_p−1 を 2^t 倍したものも、その素数で割り切れない（例えば x が 7 で割り切れなければ――つまり素因数 7 を持たなければ――、2x や 4x や 8x も依然として素因数 7 を持たず、7 で割り切れない）。つまり S_p−1 が M_p で割り切れることは、V_B が M_p で割り切れることと同値で（V_B は S_p−1 の 2^C 倍）、前者の代わりに後者を示せば、われわれの目的は達成される。

〔例1〕　p = 3 のときの Mersenne 素数 M₃ = 7 は S₂ = 14 を割り切る。それを 4 倍した (2²)S₂ = V₄ = 56 も 7 で割り切れる。この場合 C = 2^p−2 = 2, B = 2^p−1 = 4。

〔例2〕　p = 5 のときの Mersenne 素数 M₅ = 31 は S₄ = 37634 を割り切る。それを 256 倍した (2⁸)S₄ = V₁₆ = 9634304 も 31 で割り切れる。この場合 C = 2^p−2 = 8, B = 2^p−1 = 16。

以下、M_p のことを単に M と書く。M = 2^p − 1 だから 2^p = M + 1、両辺を 2 で割って B = 2^p−1 = (M + 1)/2。従って:
　　V_B = V_(M+1)/2
が成り立つ。それが M で割り切れること――言い換えれば次の関係――を示したい:
　　示したいこと　V_(M+1)/2 ≡ 0 (mod M)　　《ヒ》

《ヒ》左辺の項の番号は (M+1)/2 だけど、分数の形のままより、シンプルに M+1 になってくれた方が考えやすいかも。試しに第 2n 項の公式…
　　V_2n= (V_n)² − 2(−2)ⁿ　　← 【21】の《ヌ》
…に n = (M+1)/2 を入れてみると:
　　V_M+1 = [V_(M+1)/2]² − 2(−2)^(M+1)/2 = [V_(M+1)/2]² − 2(−2)(−2)^(M−1)/2　　《フ》
2番目の等号の意味: 指数が (M−1)/2 なら Euler の基準を使えるので、(−2) の右肩の指数 (M+1)/2 を 1 減らし、代わりに (−2) を 1 個、外に出した。この Mersenne 数 M は「2 を 3 個以上掛けて 1 を引いたもの」＝「8 の倍数から 1 を引いたもの」なので「8k−1」型; だから M−1 は「8k−2」型; その半分の (M−1)/2 は「4k−1」型の奇数; (−2) の奇数乗 (−2)^(M−1)/2 は、負の数 −2^(M−1)/2 だ。要するに《フ》は、こうなる。
　　V_M+1 = [V_(M+1)/2]² − 2(−2)[−2^(M−1)/2]
右辺第2項の符号は、マイナスが3重にあるので負。Euler の基準を使うと:
　　V_M+1 = [V_(M+1)/2]² − 4⋅2^(M−1)/2 ≡ [V_(M+1)/2]² − 4 (mod M)　　《ヘ》
なぜなら 2 は、8k−1型素数 M を法に平方剰余（第二補充法則）。

〔参考〕　(M−1)/2 の偶奇判定・紛らわしい符号処理を避け、《フ》をこう整理してもいいだろう:
　　V_M+1 = [V_(M+1)/2]² + 4(−2)^(M−1)/2
−2 は、8k−1型素数 M を法に非剰余; Euler の基準から、直ちに《ヘ》と同じ結論が出る:
　　V_M+1 ≡ [V_(M+1)/2]² + 4(−1) (mod M)

ところで p ≥ 3 に対応する Mersenne 素数 M = 2^p − 1 は、2 の奇数乗^*23から 1 を引いたもの; 2 ≡ −1 (mod 3) なので M ≡ (−1)^p − 1 ≡ −2 ≡ 1 (mod 3) となり、3 の倍数より 1 大きい（7, 31, 127, etc.）。同時に、上記のように「8k−1」型でもあり、それは「4k+3」型の一種なので^*24、7 以上の Mersenne 素数は「12k+7」型。

《ヘ》によると: もし《ヒ》が成り立つなら V_M+1 ≡ −4 となり、逆に V_M+1 ≡ −4 なら《ヒ》が成り立つ。要するに V_M+1 ≡ −4 を示せば《ヒ》を示したのと同じこと。相棒の加法定理を使い、数列の第1項の値 U₁ = 1, V₁ = 2 に注意すると:
　　V_M+1 = (12U_MU₁ + V_MV₁)/2 = (12U_M⋅1 + V_M⋅2)/2 = 6U_M + V_M
M は仮定により 7 以上の素数で、上記のように「12k+7」型なので、Lemma 2 から: U_M ≡ −1, V_M ≡ 2 (mod M)。結局:
　　V_M+1 = 6U_M + V_M ≡ 6(−1) + 2 ≡ −4 (mod M)
これが示したいことだった。□

*23　3 以上の素数 p は奇数。なぜなら 4, 6, 8, … などの偶数は 2 で割り切れるので、素数でない。

*24　「8 の倍数から 1 を引いたもの」は「4 の倍数から 1 を引いたもの」ともいえる。だから「4k−1」型、言い換えれば「4k+3」型。簡単に確かめられることだが、「4k+3」型の数は、3 で割った余りが 0, 1, 2 のどれになるかに応じて、それぞれ 12t+3, 12t+7, 12t+11 の形を持つ（t は整数）; 「8k−1」型、言い換えれば「8k+7」型の数は、3 で割った余りが 1, 0, 2 のどれになるかに応じて、それぞれ 24t+7, 24t+15, 24t+23 の形を持つ。7 以上の Mersenne 素数は「24t+7」型だが、それは「12(2t)+7」型なので、「12k+7」型ともいえる（2t=k は整数）。ここでは Lemma 2 との関連で、この「12k±○」という分類が好都合。

今回、第一の山への登頂ルートを偵察したが、出発点となる《ハ》が未証明なので、後からそのギャップを埋める必要がある。このルートは D. H. Lehmer 自身が1930年代に記したもの [2]。次回は第二の山にも登り、証明を完成させよう。

（続く）

2023-02-12　メルセンヌ数と「LLT」（中編）

#数論　#フィボナッチ　#Lucas-Lehmer

前編では、メルセンヌ数（それは一般には巨大な数である）というものを紹介し、その素数判定法「LLT」がなぜうまくいくのか、検討を始めた。証明を完結させ、一応、全体像の展望を得たい。

【27】　証明は二つの部分から成る。前回は、第一の山の麓から頂上までルートを作ったものの、肝心のベースキャンプ（出発点）が未完成。次のことを示す必要がある:
　　「LLT」で使われる数列 S_n = 4, 14, 194, … は、
　　バイナッチの「相棒」数列 V_n = 2, 8, 20, … と本質的には同じ（加速されたバージョン）

S_n は 4 から始めて、「2乗して 2 を引く」という操作で次々と項を作ったもの。 V_n は 2, 8 から始めて「直前の2項の和の2倍」という操作で次々と項を作ったもの。「本質的には同じ」というのは「因子2の個数の違いを無視すれば同じ」という意味。

数値の観察によると、これら二つの数列は次の関係を満たすようだ。

ベースキャンプ　(2^C)S_n = V_B　ただし B = 2ⁿ, C = 2ⁿ⁻¹

〔注〕　B は「n 個の 2 の積」、C は「n−1 個の 2 の積」なので、B は C の 2 倍（言い換えると、C は B の半分）。例えば n = 4 の場合:
　　B = 2⁴ = 2 × 2 × 2 × 2 = 16
　　C = 2³ = 2 × 2 × 2 = 8

ベースキャンプの等式を証明するため、n = 1, 2, 3, … に対して、左辺 (2^C)S_n の値を σ₁, σ₂, σ₃, … とし、右辺 V_B の値を ℓ₁, ℓ₂, ℓ₃, … としよう。
　　σ_n = (2^C)S_n = (2²ⁿ⁻¹)S_n
　　ℓ_n = V_B = V_2ⁿ　　《ホ》
ここで σ はギリシャ文字の小文字のシグマ、ℓ は L の小文字の筆記体だが、どちらも「宙返りコースターのように、ものすごい勢いで加速する数列」を暗示する字形！…とイメージしてもいいだろう。

〔注〕　多重の指数は、右から（上から）計算される: 2²ⁿ⁻¹ は「2 の 2ⁿ⁻¹ 乗」の意味。「2² の n−1 乗」ではない。

ものすごい勢いで増加する数列 σ　（最初の5項）

n	Sn	B = 2n	C = B/2	2C	σn = (2C)Sn
1	4	2	1	21 = 2	8
2	14	4	2	22 = 4	56
3	194	8	4	24 = 16	3104
4	37634	16	8	28 = 256	9634304
5	1416317954	32	16	216 = 65536	92819813433344

表にある最初の5項について、σ_n の値は、ℓ_n つまり V_B の値と等しいのだが、同じ関係が第6項以降も続くことを示したい。番号 k をある一定の正の整数として、n = k のとき、σ の定義から、こうなる:
　　σ_k = (2^C)S_k　ただし C = 2^k−1　　《マ》
一方 n = k+1 のときは、こうなる:
　　σ_k+1 = (2^B)S_k+1　ただし B = 2^(k+1)−1 = 2^k　　《ミ》
ところで C の2倍は B なので、次の関係が成り立つ^*25:
　　2^C × 2^C = 2^2C = 2^B　　《ム》

*25　　2^C というのは「C 個の 2 の積」なので、それを自分自身に掛けると、「C 個の 2」と「C 個の 2」で合計「2C 個の 2 の積」。例えば C = 4 なら B = 8 だが、そのとき:
　　2^C × 2^C = (2 × 2 × 2 × 2) × (2 × 2 × 2 × 2) = 2⁸ = 2^B

さて、数列 S の定義によると:
　　S_k+1 = (S_k)² − 2
両辺を 2^B 倍すると:
　　(2^B)S_k+1 = (2^B)[(S_k)² − 2] = (2^B)(S_k)² − (2^B) × 2
右辺第1項について、《ム》の関係を使うと:
　　(2^B)S_k+1 = (2^C × 2^C)(S_k)² − 2(2^B)　　《メ》
《メ》の左辺は、《ミ》によって σ_k+1 に等しい。一方、《メ》の右辺第1項について、《マ》の関係に注意すると:
　　(2^C × 2^C)(S_k)² = 2^C × 2^C × S_k × S_k
　　= (2^C)S_k × (2^C)S_k = σ_k × σ_k = (σ_k)²
結局、《メ》は全体としてこうなる:
　　σ_k+1 = (σ_k)² − 2(2^B)　　《モ》

他方 ℓ について、定義《ホ》から ℓ_k = V_B だが（ただし B = 2^k）、数列 V は次の性質を持つ（【21】の《ヌ》）:
　　V_2B = (V_B)² − 2(−2)^B　　《ヤ》
《ヤ》の右辺について: V_B = ℓ_k というのは上記の通り; B = 2^k は「2 の1乗・2乗・3乗…」だから偶数、従って −2 の偶数乗 (−2)^B は、正の数 2^B に等しい。一方、《ヤ》の左辺は（2B = 2 × 2^k = 2^k+1 なので）…
　　V_2^k+1
…を意味し、定義《ホ》によって、それは ℓ_k+1 に他ならない。結局、《ヤ》は全体としてこうなる:
　　ℓ_k+1 = (ℓ_k)² − 2(2^B)

これは――数列を表す文字の違いを別にすれば――《モ》と同一の関係: 数列 σ でも数列 ℓ でも、全く同じ規則によって、ある項（第 k 項とする）から次の項（第 k+1 項）が作られる。しかも、それぞれの第 1 項は等しい値を持つ:
　　σ₁ = (2¹)4 = 8　　　ℓ₁ = V_2¹ = V₂ = 8
最初の項が等しく、同じ規則によって第2項以降が次々と作られるのだから、二つの数列は（任意の第 k 項において）互いに等しい値を持つ。

すなわち《ホ》の二つの数列は、名前が違うだけで中身は同じ。ベースキャンプの等式が示されたのである。□

ベースキャンプから第一の山頂までのルートは前回に確立している。だからこれで、証明の前半は完成。結論として: M = 2^p − 1 が Mersenne 素数なら（p ≥ 3）、S_p−1 は M で割り切れる。

【28】　これだけでは、一体何がどう証明されたのか、あまり実感が湧かないかもしれない。まずは第二の山に登ってみて、それから全体の展望を考えよう。話をスムーズに進めるため、あらかじめ次のことを観察しておく。

LEMMA 4　バイナッチ数列 U_n とその相棒 V_n の「等しい番号の項」が、3 以上の奇数の公約数を持つことはない。

〔例〕　U₄ = 16 と V₄ = 56 は「等しい番号の項」（どちらも第 4 項）。従って、両者が同時に 3, 5, 7, 9 などで割り切れることはない。U₅ = 44 と V₅ = 152 についても同様; U₆ = 120 と V₆ = 416 についても同様。等しい番号の U_n と V_n が、別々の奇数の約数を持つことは可能（例えば U₅ = 44 は奇数の約数 11 を持ち、V₅ = 152 は奇数の約数 19 を持つ）; けれど、同じ奇数の約数を持つことは不可能。

証明　「ある等しい番号 n に対して、U_n と V_n が、3 以上の奇数の公約数 d を持つことがある」と仮定して、矛盾を導く。仮定によると U_n = dx, V_n = dy と書ける（x, y: 整数）。Pell 風の恒等式…
　　(V_n)² − 12(U_n)² = (−2)ⁿ⁺²
…にこれを代入すると（両辺は正とは限らない）:
　　(dy)² − 12(dx)² = (−2)ⁿ⁺²
　　つまり　d²(y² − 12x²) = (−2)ⁿ⁺²
この左辺の整数は d で割り切れるので、それと等しい右辺の整数も d で割り切れるはず。でも右辺の整数は（符号を無視すると）素因数として「2」しか持たず、奇数 d で割り切れるわけない。矛盾。□

〔付記〕　n = 1, 2, 3, … に対して U_n と V_n の最大公約数は 2^t の形を持つ（t は 0 以上の整数）。

【29】　第ニの山に登るため、「3 以上の素数 p に対応する Mersenne 数 M = 2^p−1 が、S_p−1 を割り切る」と仮定する。この仮定の下で、M が必ず素数になることを示す。

今、Mersenne 数 M の任意の素因数を q とする。つまり:
　　M は q の倍数　　‥‥①
M = 2^p − 1 は 7 以上の奇数なので、2 では割り切れない: M の素因数 q は 3 以上（奇数の素数）。

〔本音〕　建前は「任意の」素因数だが、もし M 自身が素数なら、その素因数は自分自身しかないので、現実には q = M という選択肢しかない。「事実そうなることを今から証明してやるぜ！」という魂胆。

仮定によって:
　　S_p−1 は M の倍数　　‥‥②

定義によって σ_p−1 = (2^C)S_p−1 だから、σ_p−1 は S_p−1 の倍数（ここで C = 2^(p−1)−1 = 2^p−2 だが、この値はどーでもいい）。 σ_p−1 = ℓ_p−1 = V_2^p−1 だから^*26、こう言っても同じこと:
　　V_2^p−1 は S_p−1 の倍数　　‥‥③

*26　　σ と ℓ の対応する項が等しいことは、【27】の「ベースキャンプ」において確定済み。

ところで、バイナッチ数列においては（より一般的に、広い意味での Lucas 数列においては）、
　　U_2n = U_nV_n　　《ユ》
が成り立つ（【17】）。従って:
　　U_2n は V_n の倍数

その特別な場合として: n = 2^p−1 のとき 2n = 2 × 2^p−1 = 2^p なので…
　　U_2^p = U_2^p−1 V_2^p−1
…が成り立つ^*27。つまり:
　　U_2^p は V_2^p−1 の倍数　　‥‥④

*27　《ユ》の項の番号 2n として 2^p を使い、n として 2^p−1 を使った。

①②③④をまとめると:
　　3 以上のある素数 q　→　q の倍数 M　→　M の倍数 S_p−1　→　そのまた倍数 V_2^p−1　→　そのまた倍数 U_2^p
…という関係があり、q の倍数の倍数の倍数の倍数 U_2^p は、もちろん q の倍数。言い換えれば:
　　U_2^p は、3 以上の素数 q で割り切れる　　‥‥⑤

Lemma 1 により、ある項 U_x が q で割り切れるなら、その項の番号 x は、q の新出位置の倍数（新出位置とは、U₁, U₂, U₃, … のうち q で割り切れる最初の項の番号）。⑤について言えば、q の新出位置を w とすると、2^p は w の倍数; 言い換えると w は 2^p の約数。2^p の素因数は「2」だけなので、2^p の約数は「1」か「2」か、または複数個の「2」の積だけで構成される。すなわち w は、次の集合のどれかの要素に等しい:
　　E = {1, 2, 4, 8, 16, …, 2^p−2, 2^p−1, 2^p}

再び Lemma 1 によると、もしも例えば w = 4 だとすると、その倍数番目の項は、どれも q で割り切れる; 特に U₄, U₈, U₁₆, …, U_2^p−1 は、どれも q の倍数になるはずだ。同様に考えて、もしも w ≠ 2^p なら（つまり、集合 E の要素のうち、2^p 以外のどれかが w として選ばれるとすれば）、そのとき w は 2^p−1 以下で、U_2^p−1 は q の倍数になるはず。ところが、その状況は実際にはあり得ない。というのも、V_2^p−1 が q の倍数ということは（①②③によって）確定しているので、U_2^p−1 も q の倍数になるとしたら、U と V の「等しい番号の項」（第 2^p−1 項）が共通の素因数 q ――つまり 3 以上の奇数の公約数 q ――持つことになってしまう; Lemma 4 によって、それは不可能。

ゆえに w = 2^p でなければならない。

最後に、Lemma 3 によると、q の新出位置 w は、不等式 q + 1 ≥ w を満たす。両辺から 1 を引くと q ≥ w − 1 だが、上記のように w = 2^p だから、この不等式は次を意味する:
　　q ≥ 2^p − 1 = M

つまり q は M 以上。しかし M の約数（素因数） q は、当然 M 以下。「M 以上」と「M 以下」というこれら二つの条件から、q = M という選択肢しかない。結局、M の「任意の」素因数を q として選んでいいにもかかわらず、実際には（M が S_p−1 を割り切るという仮定の下では）必ず M 自身が選ばれる。M の素因数として M 自身が選ばれる…というのは、M 自身が素数だから。この結論こそ、示すべき事柄だった。□

証明自体は、これで完成！

【30】　全体的な展望について。

今回の内容を整理すると: 「LLT」では、理論上、
　　バイナッチ数列の相棒の「巨大な番号の項」が M で割り切れるか否か？
を基準に、M = 2^p − 1 が素数か否かが判定される; この判定には、巨大な番号 n = 2^p−1 に対する V_n の値が必要。ところが、
　　S₁, S₂, S₃, S₄, S₅, …
として計算される値は、
　　n を 2, 4, 8, 16, 32, … のように増やした場合（次々に 2 倍する）の V_n の値〔☆〕
と本質的に同じなので、実際には代わりに S_p−1 を使って判断できる――ここで「本質的に同じ」とは「前者と後者の対応する項が 2^t 倍の違いしかない」という意味（t は 0 以上の整数^*28）: 数が何回 2 倍されても（あるいは逆に因子 2 が何個省かれても）、その数が奇数 M で割り切れるかどうか？という性質は変わらないので、この判定の目的では同じこと。われわれは〔☆〕を数列 ℓ として、それが数列 σ に一致することを確かめた。数列 σ は、数列 S の第 k 項を 2^2k−1 倍したものなので（k = 1, 2, 3, …）、数列 S から見た数列 σ の対応する各項は、ちょうど 2^t 倍の値を持つ（t = 2^k−1）。

*28　　t = 0 でも構わないが、この場合、実際には t は 1 以上（【27】《マ》の C に当たる）。

S₁, S₂, S₃, … は1項ずつ計算するしかないとしても、それぞれ V_n の第2項・第4項・第8項…と本質的に同じなので、この原理によって V_n の第 2^p−1 項を高速に計算できる。例えば p = 31 に対しては、V の 2³⁰ 番目つまり10億7374万1824番目の項が必要だが、それが S ではたったの第30項 S_p−1 = S₃₀ で済む。その S₃₀ の値が M = 2³¹ − 1 で割り切れるかどうかで、この Mersenne 数が素数かどうか判定できる。

ところで M = 2^p − 1 だから 2^p = M + 1。従って、バイナッチ数列の第 2^p 項 U_2^p を第 M+1 項 U_M+1 と呼んでもいい。

〔例〕　p = 5 とすると M = 2^p − 1 = 31; 2^p = M + 1 = 32。このとき U_2^p も U_M+1 も、数列の第 32 項。

第一の山によると、もし Mersenne 数 M が素数なら、M は対応する S_p−1 を割り切る（ただし p ≥ 3）――つまり Lucas–Lehmer test に合格する。第二の山によると、逆に M が対応する S_p−1 を割り切るなら、M は素数である。要するに、M が「LLT」に合格することと M が素数であることは同値。

この「M が S_p−1 を割り切る」という状況下においては、③④によって、U_2^p = U_M+1 も M で割り切れる。合同式で書けば:
　　U_M+1 ≡ 0 (mod M)　　《ヨ》

見覚えのある風景だ。寄り道して「美しいアラベスク」と呼んでいた光景を思い出すと、そこには含まれていた――「Mersenne 素数に限らず、何でもいいから m が12k+7型（言い換えれば12k−5型）の素数である場合、U_m+1 は m で割り切れる」という命題が。「LLT」の証明では、Lemma 2 などを通して「アラベスク」のロジックの一部が利用されるので、「LLT」が「アラベスク」と絡み合っていることは必然だろう。

Mersenne 素数に限らない一般の場合について、「m が12k+7型素数なら U_m+1 ≡ 0 (mod m)」という命題の逆は、保証されない（この種の命題ではよくあることだが）。例えば m = 2911 = 41 × 71 は U_m+1 ≡ 0 (mod m) を満たす12k+7型の数だが、素数ではない。従って、一般論としては、こういう場合「割り切れるかどうか？」だけを基準に「素数であること」の確実な判断はできない。2911 のように、「素数でないのに合同式を満たすニセ素数」（擬素数）があり得るから。

ではなぜ「LLT」では、擬素数の心配がなく、確定判断ができるのか？　【29】を振り返ると、その理由は、U_M+1 = U_2^p の項の番号が 2^p であることと関係あるようだ。この項の番号 2^p は「2」以外の素因数を含まない――非常に特殊で限定的なタイプの数。その結果、M の任意の素因数 q を考えた場合、Lemma 1 による q の新出位置 w の条件に関連して、③④などを軸に特別な制限がかかり、q = M が強制される。

もっとも、第一の山・第二の山どちらの証明でも、《ヨ》の関係は、直接的には一度も使われていない（その関係は、証明を通して、後から見えてきた）。Lemma 2 に含まれる U_M ≡ −1 (mod M) は、同じ「アラベスク」模様の一部だが、別の現象。「LLT」で重大なのは V_(M+1)/2 ≡ 0 であり、《ヨ》の U_M+1 ≡ 0 は、そこから派生する。

「LLT」の仕組みについては、後編の末尾で、もう一度整理してみたい。（続く）

2023-02-22　メルセンヌ数と「LLT」（後編）

#数論　#フィボナッチ　#Lucas-Lehmer

1から30兆までの自然数の中には、ちょうど1兆個^*29くらいの素数がある。1兆――それは、天の川銀河に散らばる星々の数と、同じくらいの大きさの数。だがその1兆個の素数の中で、Mersenne 素数は、たったの8個しかない。

「完全数」との関連もあり、Mersenne 数は、古来、さまざまな研究の対象となってきた。その動機の一部は純粋数学ではなく、神秘思想や娯楽だった。今この瞬間にも、世界中の愛好家たちが、分散コンピューティングによって、新しい素数や素因数を探しまくってることだろう。

有名な「チョコレート・ソフィーの定理」と、あまり有名でないその逆の定理を紹介したい。

*29　正確には 1兆 1億 2166万 8853個 [6][7]。誤差0.02%以内で、ちょうど1兆個といえる。ところで、天の川銀河の星の数は100億とも500億ともいわれるが、大ざっぱに「1兆くらい」ということにしておこう。

【31】　p が 20 以下の素数（2, 3, 5, 7; 11, 13, 17, 19）のとき、p = 11 を唯一の例外として、M_p は全て素数（つまり、この範囲には7個の Mersenne 素数がある）。最初の四つは:
　　M₂ = 2² − 1 = 3　　M₃ = 2³ − 1 = 7
　　M₅ = 2⁵ − 1 = 31　　M₇ = 2⁷ − 1 = 127

それぞれ完全数 2¹⋅3 = 6, 2²⋅7 = 28, 2⁴⋅31 = 496, 2⁶⋅127 = 8128 に対応し、紀元前のユークリッドの時代から知られていた――完全数とは、次のように、真約数（自分自身より小さい約数）の和が自分自身に等しい数:
　　6　⇒　真約数 1, 2, 3　⇒　1 + 2 + 3 = 6
　　28　⇒　真約数 1, 2, 4, 7, 14　⇒　1 + 2 + 4 + 7 + 14 = 28
これ以降の数も含めて、任意の Mersenne 素数 M_p は、完全数 2^p−1M_p = 2^p−1(2^p − 1) に対応する（実は、偶数の完全数はこの形のものに限られる）。古代には「ユダヤ神話の天地創造が6日間なのも、月の公転周期が28日なのも、6 と 28 が完全数だからだ」といった神秘思想もあったらしい。Mersenne 自身、数学者というより宗教家だった。

5番目の Mersenne 素数 M₁₃ = 2¹³ − 1 = 8191 は、ヨーロッパでは15世紀までに発見されていた（当時、学問が進んでいたインドやイスラム圏では、もっと早く知られていたかもしれないが、記録がはっきりしない）。6番目の M₁₇ = 2¹⁷ − 1 = 131071 と 7番目の M₁₉ = 2¹⁹ − 1 = 524287 が素数と確認されたのは1580年代。――この状況で1640年ごろ、有名な Mersenne の大予言ｗが出た（本人が予想したというより、他人の予想を引用したという説もある）。いわく:
　　「p = 31, 67, 127, 257 のときも M_p は素数。この範囲のそれ以外の M_p は合成数」

「Mersenne 数」という名前の由来となったこの予想は、全くの大外れでもなく p = 31, 127 については当たっていたが、p = 67 と 257 については間違いだった。「それ以外は合成数」という部分も間違いで、真相は p = 61, 89, 107 のときも M_p は素数。このように根拠薄弱で不正確な予想ではあったが、約300年にわたって熱い検証の対象となり、数論の発展を促す刺激ともなった。8191番の小惑星は、この貢献を記念して Mersenne と命名されている。

Lucas がこの分野の研究を行い、39桁の M₁₂₇ についてややこしい計算をしたのも、Mersenne の予想があったからこそだろう。もっとも、関連する Lucas の研究の一部は、著書 Récréations Mathématiques（数学の娯楽）で発表されている。主観的には「楽しい遊び」だったのかもしれない。

M₁₀₀ までの範囲には、前記7個の他、次の3個の（従って合計10個の）Mersenne 素数がある:
　　8番目　M₃₁ = 2³¹ − 1 = 21億 4748万 3647
　　9番目　M₆₁ = 2⁶¹ − 1 = 230京 5843兆 0092 1369 3951
　　10番目　M₈₉ = 2⁸⁹ − 1 = 618𥝱 9700垓 1964京 2690兆 1374 4956 2111

大ざっぱな数の感覚として、1個の銀河には星が1兆個くらいあり、宇宙には銀河が1兆個くらいある; 1兆個の星から成る銀河が1兆個あるときの星の合計数が1𥝱（じょ）。

1𥝱バイト（＝1ヨタバイト）のデータを保存するには、1テラバイト（＝1兆バイト）の容量のデバイスが1兆個必要！

水素原子を1𥝱個、集めるとざっと1グラム（正確には約1.7グラム）。言い換えると、水素原子は、1兆個でようやく1ピコグラム（＝1兆分の1グラム）のオーダー。

8番目の M₃₁ = 2147483647 は、1億0509万7565番目の素数であり、最初の1兆個の素数に含まれる最後の Mersenne 素数。「32ビット符号付き整数」で表現できる最大の数でもある――この限界は、単なる理論上のものではなく、リアルな「2038年問題」の原因となる。関係ないが「宇宙世紀0079」とかいうガンダム・ユニバースでは、そのうち「宇宙世紀9999」問題が起きるのでは…ｗ

11番目は M₁₀₇。Lucas が筆算で素数性を確かめた39桁の M₁₂₇ は、大きさの順序では12番目の Mersenne 素数（発見の順序と大きさの順序は異なる）。人類が（コンピューターを使わず）筆算で発見した Mersenne 素数はこの12個。筆算の時代には、13番目の Mersenne 素数 M₅₂₁ には到達できず、電算機の時代となった。

【32】　なぜ最初の8個の素数（p = 2, 3, 5, 7; 11, 13, 17, 19）のうち、p = 11 の場合だけ M_p が Mersenne 素数にならないのだろうか？

説明の便宜上、ある数の2倍に1を足したものを、その数の姉と呼ぶことにしよう。例えば 6 の姉は 13。

実は p が 11 のような4k+3型の素数（4で割って3余る素数）のとき、もし p の姉 A = 2p+1 も素数なら、M_p は姉 A で割り切れる。p = 11 の例では、姉 A = 2⋅11+1 = 23 が素数なので、M₁₁ は 23 で割り切れる（2047 = 23 × 89）。

自分の姉 2p+1 も素数であるような素数 p を Sophie Germain（ソフィー・ジェルマン）素数^*30という（素数の姉妹の妹）。4k+1型、4k+3型の数をそれぞれ「バニラ」「チョコレート」と呼ぶと（もちろん正式な用語ではないが）:
　　p がチョコレート素数で、しかもその姉も素数である場合、M_p は姉で割り切れる。
簡潔に: p がチョコ・ソフィーなら M_p は合成数（2p+1 で割り切れる）。

*30　「Mersenne 素数」「Fermat 素数」のように、普通、人名にちなむ用語では研究者の名字が使われる。Sophie Germain に限って、わざわざフルネームを使うのは「女性の数学者」ということを強調する意図。当時は女性の数学者は非常にまれで、Sophie Germain の活躍は、驚嘆と賛美の対象として（良い意味で）特別視された。裏を返せば「ほとんどの女は頭が悪い」という考え方の女性蔑視ではあるが（Gauß 自身、そのような一般的偏見の存在に言及している）、200年以上前の社会の実情・歴史的背景も考慮する必要がある。現代の価値観では、女性の研究者だからといって別扱いするのは不適切だろうから「Sophie」を外して「Germain 素数」と呼ぶべきかもしれない。

チョコレート・ソフィーの定理　p を4k+3型の素数とする（p ≥ 3）。もし p の姉 2p+1 が素数なら（従って、妹 p は Sophie Germain 素数）、姉 2p+1 は Mersenne 数 M_p = 2^p − 1 を割り切る。

〔例〕　100以下の素数のうち、チョコ・ソフィーは次の4個: p = 3, 11, 23, 83（これらはチョコレート素数で、それぞれの姉 A = 7, 23, 47, 167 も素数）。 p = 3 のとき M₃ = 2³ − 1 = 7 は A = 7 で割り切れるが、この約数 7 は M₃ 自身なので、M₃ が素数であることには変わりない（M₃ だけの特殊な状況）。M₁₁ = 2047 は前記のように A = 23 で割り切れ、合成数。 p = 23 のとき M₂₃ = 2²³ − 1 = 8388607 は A = 47 で割り切れ、合成数。最後に p = 83 に対する次の25桁の数は、計算するまでもなく 2p+1 = 167 で割り切れることが事前に分かり、従って LLT で判定する必要もない。
　　M₈₃ = 2⁸³ − 1 = 9𥝱 6714垓 0655京 6917兆 0333 9764 9407

証明　p = 4k+3 を素数（k は 0 以上の整数）、A = 2p+1 = 8k+7 も素数だと仮定して、M_p = 2^p − 1 が A で割り切れることを示す。仮定により A−1 = 8k+6、従って (A−1)/2 = 4k+3 = p。だから次を示せばいい:
　　2^p − 1 = 2^(A−1)/2 − 1 ≡ 0　つまり　2^(A−1)/2 ≡ 1 (mod A)
8k+7 型の素数 A を法として 2 は平方剰余なので（第二補充法則）、Euler の基準によりこの合同式は確かに成立。□

注意　姉 2p+1 が素数でない場合には、上記の性質は成り立たない。例えば p = 7 のとき 2⋅7+1 = 15 は素数でないので、M₇ = 2⁷ − 1 = 127 は 15 で割り切れない（M₇ は Mersenne 素数）。p = 19, A = 39 や p = 31, A = 63 の場合も同様。一方、M₄₃ は Mersenne 合成数だが、A = 87（それは 3 の倍数であり素数ではない）では割り切れない。さらに、たとえ姉 2p+1 が素数でも、妹 p がチョコレート素数でない場合（バニラ・ソフィーまたは 2 の場合）、上記の性質は成り立たない。他方、妹 p が 11 以上のチョコ・ソフィーの場合には、判定するまでもなく M_p は合成数であり、姉 2p+1 で割り切れる。――これが定理の重要な意味。

〔参考〕　p = 11 に対して A = 2p+1 = 23 も素数なので 11 は Sophie Germain 素数だが、この A をあらためて p = 23 と置くと、A = 2p+1 = 47 も素数なので、23 も Sophie Germain 素数（23 は 11 の姉素数だが、その 23 には 47 という姉素数が存在する――11 から見れば姉の姉）。このような素数の連鎖を（第一種の）Cunningham chain という。2 → 5 → 11 → 23 → 47 は、長さ 5 の連鎖だが、次の 2⋅47+1 = 95 は素数でないので、この chain はここで途切れる。

〔注〕　「姉素数」は、文献上「安全素数」（safe prime）と呼ばれることがある。詳細は省くが「安全素数」という用語は内容的に問題があるので、使わない方がいい。「姉・妹」は正式な用語ではないが、簡潔で、大小関係も分かりやすい。

【33】　上記「チョコ・ソフィー番目の Mersenne 数」の性質は有名なもので、Mersenne 数を扱った多くの文献に記載されている。一方、それほど有名ではないが、次の意味で逆も成り立つ。

あまり有名でない定理　p を4k+3型の素数とする（p ≥ 3）。もし姉 2p+1 が Mersenne 数 M_p = 2^p − 1 を割り切るなら、姉 2p+1 は素数（従って、妹 p は Sophie Germain 素数）。

証明　背理法による: 定理の前提の下で 7 以上の奇数 A = 2p+1 を合成数と仮定し、矛盾を導く。A の一つの素因数を q としよう。素数 q は奇数 A の約数なので、もちろん奇数だが、仮定により A 自身は素数でないので q = A はあり得ず q < A。のみならず奇数 A = 2p+1 は 2 で割り切れないので q = A/2 もあり得ず q < A/2。従って q ≤ A/3 = (2p+1)/3 < p。要するに q < p。

〔注〕　単に A の最小の素因数を q として q ≤ √A とする方法 [8] もあるが、q < p と縛ってしまう方が話が早いように思われる。

q は A を割り切り、定理の前提によって A は M_p = 2^p − 1 を割り切るのだから、q も 2^p − 1 を割り切る:
　　2^p − 1 ≡ 0　つまり　2^p ≡ 1 (mod q)
従って、mod q での 2 の位数 e は p の約数だが、p は素数なので、約数といっても、可能性は 1 と p 自身のどちらかしかない: e = 1 or p。

一方、Fermat の小定理から、素数 q は次の合同式を満たす:
　　2^q−1 ≡ 1 (mod q)
従って、mod q での 2 の位数 e は q−1 の約数でもある。ところが上記のように q < p 従って e ≤ q−1 < p であり（なぜなら e は q−1 の約数）、すなわち e < p。この不等式を満たす e は e = 1 しかない（なぜなら e = 1 or p）。

結局、位数 e は 1、つまり 2¹ ≡ 1 (mod q) となるが、これはばかげている！　矛盾。□

〔参考〕　別解として、もし q ≤ √A と縛った場合、e は素数 p の約数なので 1 or p だが、e = 1 は上記のように不合理なので、e = p。この e = p は q−1 の約数でもあるので、p ≤ q−1 つまり p < q。ところが q ≤ √A なので q² ≤ A つまり q² < A + 1 = (2p+1) + 1。これは（p < q なので） p² < q² < 2p + 2 を含意。両辺を p で割ると p < 2 + 2/p だが、その右辺は 3 未満（なぜなら p ≥ 3）、すなわち p < 3。矛盾。――最初の証明の q < p は、位数に関連して直ちに矛盾を発生させる。別解における反対向きの不等式 p < q は、それ自体としては不合理ではないが、q ≤ √A とは両立できない。現実には A 自身が素数、真相は p < q = A。もしも A が「素数でない」と無理やり仮定すれば、どっちにしても、つじつまが合わなくなる。

【34】　小さい Mersenne 数については実用上 LLT を使うまでもないが（例えば 127 が素数であることは、2, 3, 5, 7, 11 で割り切れないことから明らか）、数列の「感じ」をつかむため、関連する実際の数値例を観察しておく。

〔その1〕　p = 3 のとき S_p−1 = S₂ = 14 は M₃ = 7 で割り切れるので、M₃ は素数。

この S₂ = 14 の 2^2p−2 = 4 倍が V_2^p−1 = V₄ = 56 であり、V₄ = 56 が M₃ = 7 で割り切れると言っても、本質的に同じこと。

〔その2〕　p = 5 のとき S_p−1 = S₄ = 37634 は M₅ = 31 で割り切れるので、M₅ は素数。

この S₄ = 37634 の 2^2p−2 = 256 倍が V_2^p−1 = V₁₆ = 9634304 であり、V₁₆ が M₅ で割り切れると言っても、本質的に同じ。

〔その3〕　p = 7 のとき S_p−1 = S₆ = 200京 5956兆 5468 2274 6114 は M₇ = 127 で割り切れるので、M₇ は素数。

この S₆ の 2^2p−2 = 2³² 倍が V_2^p−1 = V₆₄ = 8615𥝱 5177垓 6580京 0787兆 2685 4108 7744。 V₆₄ が M₇ で割り切れると言っても、本質的に同じ。

〔その4〕　p = 11 のとき S_p−1 = S₁₀ は293桁の数だが、これは M₁₁ = 2047 で割り切れないので、M₁₁ は素数でない。実際 2047 = 23⋅89。

この S₁₀ の 2^2p−2 = 2⁵¹² 倍が V_2^p−1 = V₁₀₂₄ であり（それは447桁の数）、V₁₀₂₄ は M₁₁ で割り切れないと言っても、本質的に同じ。

原理的には以下同様に進めることができるが、V_2^p−1 も、簡略化した S_p−1 も、判定したい Mersenne 数（M₁₁ = 2047 なら、たった4桁）に比べて、桁数があまりにも急激に増大する。必要なのは商ではなく、割り切れるかどうか（つまり余りが 0 になるかどうか）の情報だけ。以下の例のように、実際の計算では、途中で値が M_p 以上になったら、それを M_p で割った余りで置き換えて構わない。

〔例〕　M₇ = 127 について判定する場合、S₁ = 4, S₂ = 4² − 2 = 14, S₃ = 14² − 2 = 194 の次のステップにおいて、ばか正直に
　　S₄ = 194² − 2 = 37634★
とせず、194 を「それを 127 で割った余り」の 67 で置き換えていい:
　　194 ≡ 67 (mod 127)
　　S₄ ≡ 67² − 2 ≡ 4487 ≡ 42 (mod 127)
★も 127 で割れば余りは 42 なので、どちらのバージョンでも結果は同じ。同様に:
　　S₅ ≡ 42² − 2 ≡ 1762 ≡ 111 (mod 127)
　　S₆ ≡ 111² − 2 ≡ 12319 ≡ 0 (mod 127)
つまり 12319 が 127 で割り切れるので、素数と判定される。

このように、途中計算で大きな数ができたら、その都度、余りで置き換えていい: ある数 s について、s² − 2 を M で割った余りを知りたいとき、先に s を M で割って、その余りを r とすると、小さい数 r² − 2 によって大きい数 s² − 2 を代用できる。理由は単純で、s = Mq + r とすると（q は s を M で割った整数商）:
　　s² − 2 = (Mq + r)² − 2 = (Mq)² + 2(Mq)r + r² − 2
この右辺の第1・第2項は M の倍数なので、M で割った余りという観点からは 0 に等しく、従って右辺を M で割った余りは、第3・第4項の r² − 2 を M で割った余りに等しい。この右辺は全体として左辺の s² − 2 と等しい値なので、結局 s² − 2 を M で割った余りと、r² − 2 を M で割った余りは一致。

〔付記〕　「余りで置き換えていい」というのは概念上の話。実装上「どうやってその余りを求めるか」が問題。Mersenne 数 M は、2進法では非常に特徴的な形をしているため（サイズ分の全ビットが1）、コンピューター上では、ビット演算を利用して――実際に割り算をすることなく――「M で割った余り」を高速に求めることができる。数論の問題ではなくプログラミングの問題なので内容には立ち入らないが、「余りの計算」を高速化できる結果として、LLT の実装では「2乗の計算」の部分がボトルネックとなる。「どうやって巨大整数の掛け算を少しでも速くするか」という問題は、突き詰めると難しい。

【35】　まとめとして、前編・中編で歩いた道を簡単に振り返ってみよう。

Lucas–Lehmer test (LLT) で使われる数列 S_n = 4, 14, 194, … は、バイナッチ数列の相棒 V_n の第2項・第4項・第8項…を素早く計算するためのショートカットに過ぎないのだった。「バイナッチ数列」とは、Lucas 数列の一種（P = 2, Q = −2 の場合）。

理論上の本質は、Mersenne 数 M = M_p = 2^p − 1 について V_(M+1)/2 = V_2^p−1 が M で割り切れるか調べることにある。それは U_(M+1)/2 = U_2^p が M で割り切れるか調べることとも同値（なぜなら U_2n = U_nV_n）。

2倍番号の公式 V_2n = (V_n)² − 2(−2)ⁿ から、
　　[V_(M+1)/2]² = V_M+1 + 4
となるが（【26】《ヘ》参照）、もし M が素数なら、Lemma 2 により
　　V_M+1 = 6U_M + V_M ≡ −6 + 2 ≡ −4 (mod M)
なので、それを上の式に代入すると V_(M+1)/2 ≡ 0 (mod M) となり、V_(M+1)/2 は M で割り切れなければならない――それは S_p−1 が M で割り切れることと同値。ゆえに S_p−1 が M で割り切れることは、M が素数であるための必要条件。

逆に V_(M+1)/2 が M で割り切れるなら、V_(M+1)/2 も U_M+1 も M で割り切れるが、そのとき M の「任意の」素因数 q の新出位置は M+1 より小さくなれない。なぜなら、もしも小さくなれたとすると、M+1 の素因数分解から（それは単に = 2^p というだけだが、その単純さが鍵）、U_(M+1)/2 も M で割り切れることになってしまい、Lemma 4 に反する。つまり q の新出位置は M+1 であり、これは M = q が素数であることを意味する。ゆえに S_p−1 が M で割り切れることは、M が素数であるための十分条件。

結論として、7 以上の Mersenne 数 M_p が素数になるためには、対応する S_p−1 が M_p で割り切れることが必要であり、またそれで十分！

〔付記〕　m を Mersenne 数に限らず、12k+7型の一般の自然数とした場合、バイナッチ数列における m (= q) の新出位置が m+1 であることは、m が素数であるための十分条件だが、必要条件ではない。例えば m = 607 はこの型の素数で、U₆₀₈ は 607 で割り切れるが、新出位置は 608 ではなく、その19分の1の 32（ここで 608 = 2⁵⋅19）。つまり、次の数は既に 607 で割り切れる:
　　U₃₂ = 26兆 7947 7213 5936
このように、一般のケースでは、新出位置と素数判定の関係は単純ではない。m が Mersenne 数という特殊なケースにおいては、m+1 の素因数が「2」しかないため、上述のシンプルな判定が成り立つのである。

与えられた整数 m が素数か否かを判定するアルゴリズムを「素数性テスト」「素数性（の）判定法」などという。LLT は Lucas 数列を使う判定法の一種で、7 以上の Mersenne 数 m = 2^p − 1 の判定に特化されている。Lucas 数列を利用して m の素数性判定を行う場合、m+1 の因数分解が重要な意味を持つ（Mersenne 数の場合 m+1 = 2^p であることは、最初から分かっている）。

気まぐれに Fibonacci 数列で遊び始め、遊びがこじれて（？）「バイナッチ数列」なるものに手を出し、おのずと一般の Lucas 数列も視野に入ってきた。Lucas–Lehmer Land は楽しい遊園地だが、バイナッチ数列という一つの例だけでは、Lucas 宇宙の全体像はまだよく分からない…。バイナッチの銀河を探検し、銀河の果てまで来たものの、広大に思えたこの銀河、実は無数に散らばる銀河系の中のたった一つに過ぎなかったようだ！

参考文献　（✖印については末尾の〔注〕参照）
[2] D. H. Lehmer (1935): On Lucas’s Test for the Primality of Mersenne’s Numbers
https://primes.utm.edu/mersenne/LukeMirror/lit/lit_007s.htm
 for σ_k = V₂, read σ_k = V_2^k
[3] List of Known Mersenne Prime Numbers
https://www.mersenne.org/primes/ ✖
[4] Wacław Sierpiński (1964): Elementary Theory of Numbers, Chap. X
https://eudml.org/doc/219306 ✖
 p. 338, Eq. (10): for 2^2p−1s_p−1, read 2^2p−2s_p−1
 p. 340: for s_k ≥ 10^2k−2 + 4, read s_k ≥ 10^2k−2 + 4
 p. 340: while it has more than 10²⁷ digits is a correct statement, S₁₀₀ has more than 10²⁹ (and less than 10³⁰) digits
 p. 342: for n = kl, read m = kl
 p. 173: for 2⁸(2⁷ − 1), read 2⁶(2⁷ − 1)
[5] Ribenboim (1996): The New Book of Prime Number Records (3rd ed.), Chap. 2, Sect. VII
 p. 91: for If suffices, read It suffices
 p. 92: for 4(−1)^(N+1)/2, read 4(−2)^(N+1)/2
 p. 93: for V_2^k+1+2^2k+1 in the numerator, read V_2^k+1 + 2^2k+1
[6] PrimePage Primes: The Nth Prime Page
https://primes.utm.edu/nthprime/index.php ✖
[7] A080122 - OEIS: Number of primes less than n*10^13
https://oeis.org/A080122
[8] Euler and Lagrange on Mersenne Divisors
https://primes.utm.edu/notes/proofs/MerDiv2.html ✖
The claim that the order of 2 modulo q divides both p and q-1, hence p divides q-1 may not be transparent enough; technically the order could be 1 instead. One may simply note, “Clearly q < (2p+1)/2, so q < p.” Then the order 1 will be forced, which would be absurd, immediately concluding the demonstration.
〔注〕　✖印のURLは、内容としては参考になるのだが、ページの構造上、プライバシー侵害（トラッキング＝ウェブ上の行動監視）の要素が比較的高い。悪意があるわけではなく、管理者が「これは便利なツール」と考えたのだろう、好ましくない外部サイトを読み込んでしまっている（資本主義の営利企業が「絶対的な意味で無料」のツールなど提供するわけがなく、そこに隠れたトレードオフがあるわけだが…）。どのページもCookie不要、JavaScript不要、Referer不要なので、自己判断で自己防衛を。Tor Browser でも閲覧可能だが、その場合 [4] からPDFをダウンロードするとき、デフォルトの HTTPS-only mode では警告が出る（HTTPSに対応していないだけで、本質的な問題ではないので、この警告は無視していい）。2023年2月現在。

2023-03-02　メルセンヌ数の分解　もしも願いが一つかなうなら…

#数論　#第二補充法則　#メルセンヌ数

2, 4, 8, 16, 32, … と倍々になる数から 1 を引いた Mersenne 数:
　　1, 3, 7, 15, 31, …
そのうち素数番目のもの（M₂ = 3 や M₃ = 7 や M₅ = 31 など）は、それ自身、素数になることがある。世にいう Mersenne 素数。

だが、以下では「素数番目だが、値が素数にならない Mersenne 数」に注目したい。例えば 11 は素数だが、11番目の Mersenne 数 2047 は素数ではない（23 で割り切れる）。一般論として、素数でないからには、もっと小さい素数の積に分解できるわけだが、この分解は難しい。巨大な数を分解できたときの喜びは、実際に体験してみないと分からないだろう。

【36】　M_p は p = 2, 3, 5, 7; 13, 17, 19 のときは素数だが、p = 11 のときは素数にならない:
　　M₁₁ = 2¹¹ − 1 = 2047 = 23 × 89
「LLT」で判定するまでもなく、p = 11 がチョコレート（4の倍数より1小さい）ということと、p の姉（2倍して1を足したもの）つまり 23 も素数ということから、M₁₁ = 2047 が姉 23 で割り切れることは、一目瞭然（その証明は前回参照）。89 は素数なので、M₁₁ は上記の形で分解完了。

p = 19 の次の素数は p = 23 だが、
　　M₂₃ = 2²³ − 1 = 8388607
も、同じ理由から、素数ではない。姉 47 で割り切れる:
　　M₂₃ = 8388607 = 47 × 178481
でも、これで分解完了なのだろうか…。つまり、47 で割った商（余因数）の 178481 は素数なのだろうか？

さらに p = 23 の次の素数は p = 29 だが（そして姉 59 も素数だが）、29 はチョコレート素数ではないので、チョコ・ソフィーの定理を使えない。
　　M₂₉ = 2²⁹ − 1 = 536870911
この5億台のでかい数は「LLT」によれば合成数。だが、因数が1個も分からない。一体どーやって、分解すりゃぁいいんだ、こんなでかい数。約数を見つけるため 3, 5, 7, … などで一つずつ割ってみる？

「とりあえず試しに割ってみる」というのは重要で、実用的なアイデアではあるが、じゅうたん爆撃のような「割り算」攻撃を仕掛ける前に、状況を冷静に分析してみたい。

【37】　合成数 M_p = 2^p − 1 が素因数 x を持つっつーことは…。要するに 2^p − 1 が素数 x で割り切れるってことだが…。x で割ると余りが 0 ってことなんで、式で書くとこーなる:
　　2^p − 1 ≡ 0 (mod x)　両辺に 1 を足すと
　　2^p ≡ 1 (mod x)
チョコ・ソフィーの逆と同じで、mod x での 2 の位数 e は p の約数ってことが分かる。これは重要な手掛かり…。p は素数なんだから、p の約数は 1 or p しかない。位数が 1 のわけないので e = p 確定。一方、毎度おなじみ Fermat の小定理から、
　　2^x−1 ≡ 1 (mod x)
なんで、mod x での 2 の位数 e は x−1 の約数でもある。e = p が確定しているので:
　　p は x−1 の約数
言い換えれば:
　　x−1 は p の倍数
つまり x−1 = ap と書ける（a は何らかの整数）。両辺に 1 を足すと:
　　x = ap + 1

これはすごい発見だぞッ！　M_p が x で割り切れるなら、その x って数は「p の倍数プラス1」の形を持つ！

〔例1〕　M₁₁ = 2¹¹ − 1 = 2047 は 23 で割り切れる（チョコ・ソフィーの定理）。23 は、もちろん 11 の倍数（2倍）プラス 1。それが「姉」の定義だもん。…チョコ・ソフィーの定理は、上記の一般的性質のうちの「一番シンプルな例」（2倍）ってことになる。

〔例2〕　M₂₉ = 2²⁹ − 1 = 536870911 の約数は「29 の倍数プラス1」の形でなければならないのだから、次のようなどれかの数ってことになる:
　　2⋅29+1 = 59, 3⋅29+1 = 88, 4⋅29+1 = 117, 5⋅29+1 = 146, …
けれど奇数 M₂₉ が、偶数で割り切れるわけないんで、このうち「29の奇数倍プラス1」（それは偶数である）って可能性はない。「29 の偶数倍プラス1」だけが、約数になる可能性がある。
　　29 の 2 倍は 58。プラス1で 59。　536870911/59 = 9099506.966…　割り切れない☆
　　29 の 4 倍は 116。プラス1で 117。　536870911/117 = 4588640.264…　割り切れない★
　　29 の 6 倍は 174。プラス1で 175。　536870911/175 = 3067833.777…　割り切れない★★
　　29 の 8 倍は 232。プラス1で 233。　536870911/233 = 2304167　割り切れたっ！！！

これで M₂₉ = 233 × 2304167 と分解できたのだが、これで分解完了なのかどうかは、まだ分からない（余因数 2304167 が素数なら分解完了だが、2304167 がもっと小さい素数の積に分解可能という可能性もある）。

ところで、例2の★★は、本当は試しに割ってみるまでもない。175 は明らかに 5 の倍数。だから、もしも 536870911 が 175 で割り切れるなら、536870911 は 175 の倍数で、それは 5 の倍数になるはずだが、536870911 が 5 の倍数じゃないことは一目瞭然。同じ理由から、★の計算も必要ない。117 は明らかに 3 の倍数（桁の和 1+1+7 = 9 が 3 の倍数だから）、だが 7 以上の Mersenne 数は 12N+7 の形なんで 3 の倍数のわけない。

ってゆーか、そもそも M₂₉ を割り切る素数 x を探してるんだから、x が合成数（175 や 117）のわけないじゃん！

ここまでで分かったこと:
　　①　M_p の素因数 x は ap+1 の形を持つ（p の倍数プラス1）
　　②　その a は偶数でなければならない。a = 2k とすると、x = 2kp+1 と書ける
　　③　当たり前のことだが、素数 x を考えているのだから、x の候補 2kp+1 が合成数の場合、無視してもいい

結局 k = 1, 2, 3, … に対する 2kp+1 という数が x の候補となる（合成数の場合は無視してもいいが、2kp+1 が素数か合成数か判定するのもそれなりに面倒なので、無視しなくてもいい。どちらにしても結果は変わらない）。

〔注〕　後述するように、実は、例2の☆も試す必要がない。

【38】　k = 1, 2, 3, … と書くのは簡単だが、実際問題、一体どこまで k を増やせばいいのだろうか？　一般に自然数 N が N = A × B と分解されるとき、A と B の両方が √N より大きくなることはあり得ない…よね？

〔証明〕　もしも A > √N かつ B > √N なら:
　　A × B > √N × √N = N　つまり　A × B > N
これは N = A × B という前提に反する。□

だから、もし N = A × B という分解が可能なら、A と B のうち小さい方を選ぶと（A = B ならどちらを選んでもいい）、その数は √N 以下。要するに、試しに割ってみて素因数を見つける場合、√N 以下の範囲の素因数候補を考えれば十分であり、またそれが必要でもある（例えば N = 289 を分解するには √289 = 17 以下の範囲を考える必要がある: 実際 289 = 17 × 17）。その範囲に（1以外の）約数がなければ、どこにも約数はない＝その数は素数ってこと。

最初に考えた M₂₃ = 8388607 = 47 × 178481 に戻って、178481 は果たして素数なのか、それとももっと分解できるのか。√178481 = 422.4… なので、もっと小さい素数の積になる可能性があるとすれば、その素数の一つは 422 以下。ところが素数の候補 x は 46k+1 の形を持たねばならないのだった。可能性がある候補は、次の3つだけ:
　　46⋅1+1 = 47, 46⋅2+1 = 93*, 46⋅3+1 = 139, 46⋅4+1 = 185*, 46⋅5+1 = 231*,
　　46⋅6+1 = 277, 46⋅8+1 = 323$, 46⋅8+1 = 369*, 46⋅9+1 = 415*, (46⋅10+1 = 461#)

*印は明らかに素数ではないので無視。$印の 323 = 17 × 19 も素数でないが、それを認識せず無視しないとしても（どのみち割り切れないだけで）実害はない。#印の 461 は、大き過ぎる。

178481/47 = 3797.468…, 178481/139 = 1284.035…, 178481/277 = 644.335… はどれも割り切れない。だから、M₂₃ には 178481 より小さい素因数はない。

結論: M₂₃ = 8388607 = 47 × 178481 については、これで分解が完了してる。

「おまえは もう 分解されている…」

同様に考えて M₂₉ = 233 × 2304167 の余因数 2304167 は、もし合成数なら √2304167 = 1517.9… 以下の素因数を持つ。2kp+1 = 58k+1 という形の数だけを考えればいいのだから、たとえ 58k+1 が合成数になるケースを無視しないとしても、候補は26個しかない（58⋅27+1 = 1567 は範囲外）。素数表を利用して、この範囲内の58k+1型素数だけを抜き出すと:
　　59, 233, 349, 523, 929, 1103, 1277, 1451
順に試すと 6 番目で割り切れる！
　　2304167/1103 = 2089
そして √2089 = 45.7… は（もうこれ以上、この型の小さい素数で割り切れないので）素数。

結論: M₂₉ = 233 × 1103 × 2089 と分解される。

〔参考〕　最後の余因数 2089 自身も（M₂₉ の素因数なのだから当然だが）、同じ58k+1の型を持つ（k = 36）。

【39】　3, 5, 7, … などで片っ端から割ってみる野蛮な方法と比べると、上記の「ピンポイント攻撃」は、なかなかいい感じ。第二補充法則を使うことで、これをさらに改善（高速化）できる。素数 x は、
　　x = 2kp + 1　つまり x − 1 = 2kp
という関係を満たすのだった。そのことから、遅かれ早かれ、次のアイデアが浮かぶだろう:
　　「指数が半分の (x − 1)/2 なら Euler の基準を使える」
都合がいいことに x − 1 = 2kp は2の倍数なので、半分にできるし。

さっそく自然数 (x−1)/2 = kp を考えて、それを 2 の指数とすると:
　　2^(x−1)/2 = 2^kp = (2^p)^k
2^p ≡ 1 (mod x) なんで（【37】参照）、(2^p)^k ≡ (1)^k ≡ 1 (mod x) となり、上の式はこーなる:
　　2^(x−1)/2 ≡ 1 (mod x)
Euler の基準から 2 は mod x の平方剰余。第二補充法則から x は 8n±1 の形を持つ（n は正の整数）。

Mersenne 数の素因数の概要　M_p = 2^p + 1 の素因数 x は 2kp+1 の形を持ち、しかも 8 の倍数より1大きいか1小さい。

〔例3〕　M₂₉ = 233 × 1103 × 2089 について、既に見たように、どの素因数も 58k+1 の形を持つ。233 は 8 の倍数より1大きい（200 は 8 の倍数なので、200 単位の部分を無視して、下2桁の 33 だけを考えればいい）。1103 は 8 の倍数より1小さい（この場合、下3桁の 103 = 80+23 だけを考えればいい）。2089 は 8 の倍数より1大きい（下2桁だけ考えればいい）。

前のセクションでは、M₂₉ の（1517 以下の）素因数の候補として、次の58k+1型素数を考えた:
　　59, 233, 349, 523, 929, 1103, 1277, 1451
「8の倍数プラマイ1」って条件も加えると、これらの候補の約半数は条件を満たさず、候補は次の3個に絞られる。
　　233, 929, 1103
攻撃目標がさらにピンポイントってところか。

2kp+1型の数（p は奇素数）が、同時に 8n±1 の形になる条件を整理すると、次の通り。表記を簡潔にするため、a = 2k として ap+1 の形の数を考える。4am = 4(2k)m = 8km が 8 の倍数であること、つまり 4am ≡ 0 (mod 8) という事実を途中で使う。

第一に、a が 8 の倍数であればもちろん ap も 8 の倍数なので、ap+1 は 8n+1 の形になる。逆に ap+1 がこの形なら、つまり ap+1 ≡ 1 (mod 8) なら、ap ≡ 0 (mod 8) だが、その両辺を p で割ると a ≡ 0 (mod 8)。この割り算は p と法 8 が互いに素なので、許される。――要するに a が 8 の倍数であるとき、そしてそのときに限って、ap+1 は 8n+1 の形に。

第二に、ap+1 が 8n−1 の形になる条件は、p の型によって異なる。p が「4m+1型」の素数の場合、ap+1 = a(4m+1)+1 = 4am + (a+1) が ≡ −1 (mod 8) になることは、a+1 ≡ −1 (mod 8) つまり a ≡ −2 (mod 8) と同値（なぜなら上述のように 4am ≡ 0）。他方 p が「4m+3型」の素数の場合、ap+1 = a(4m+3)+1 = 4am + (3a+1) が ≡ −1 (mod 8) になることは、3a+1 ≡ −1 ≡ 7 (mod 8) つまり a ≡ 2 (mod 8) と同値。

Mersenne 数の素因数の詳細　M_p = 2^p + 1 の素因数 x は ap+1 の形を持つ（a は正の整数）。p が4m+1型の素数なら、a は 8 の倍数であるか、または 8 の倍数より 2 小さい。p が4m+3型の素数なら、a は 8 の倍数であるか、または 8 の倍数より 2 大きい。

p が 4m+3型（チョコレート素数）なら、a は「8 の倍数より 2 大きい」可能性があり、特に a = 2 の可能性がある（既に見たように、a = 2 は 2p+1 が素数の場合に限って可能）。一方、p が 4m+1型（バニラ素数）なら、a が「8 の倍数より 2 大きい」可能性はなく、特に a = 2 は不可能。すなわち p が「チョコレート・ソフィー」の場合の Mersenne 数（必ず 2p+1 で割り切れる）と違い、p が「バニラ・ソフィー」の場合（より一般的に p がバニラ素数の場合）、M_p は決して 2p+1 では割り切れない。

〔例4〕　例2では、バニラ・ソフィー p = 29 に対する M_p を考えた。そして a = 2☆, 4★, 6★★, 8 を試して a = 8 で分解に成功した。上記の考察によれば、（ソフィーかどうかと関係なく）バニラ素数というだけで、a = 2☆, 4★ という可能性は消滅する。

〔例5〕　「LLT」で判定すると M₃₁ は素数、M₃₇ は合成数。後者を分解したい。M₃₇ の素因数は 37a+1 の形を持ち、a は 8 の倍数か、またはそれマイナス2。つまり、以下のような形の数が候補となる:
　　37⋅8+1 = 297*, 37⋅16+1 = 593, 37⋅24+1 = 889*, …
　　37⋅6+1 = 223, 37⋅14+1 = 519*, 37⋅12+1 = 445*, …
このうち*印は 3, 5, 7 のどれかで割り切れるので、無視していい。それ以外の候補を試すと、何と最初の 223 がいきなりヒット！
　　2³⁷ − 1 = 137438953471 = 223 × 616318177
余因数 616318177 の平方根は 24825.7…。手計算ではちょっと面倒な大きさだ: a = 83⋅8 = 664 は範囲内（37⋅664+1 = 24569）、a = 84⋅8 = 672 は範囲外なので、合成数込みだと 83 × 2 = 166 個も因数候補がある。24825以下の全素数を含む素数表を持っているとして、それを使って素数だけを抜き出すと、候補は次の33個に絞られる:
　　a ≡ 0 (mod 8) に対する 37a+1型　18個　（言い換えれば「296N+1型」素数）
　　a ≡ 6 (mod 8) に対する 37a+1型　15個　（言い換えれば「296N+223型」素数）
そのどれも 616318177 を割り切らないので、M₃₇ は上記で分解完了。

ここまでの成果をまとめると: p ≤ 40 の素数について、M_p が合成数になるのは、p = 11, 23, 29, 37 だが、最初の2個については、チョコレート・ソフィーの性質によって直ちに分解完了する（余因数は既に素数）。M₂₉ は3個の素因数から成り、233 と 1103 で割り切れる。M₃₇ は2個の素因数から成り、223 で割り切れる。

〔コメント〕　2, 3, 23, 223, 233 はどれも Mersenne 数の因数となる（M₁₁ は 23 で割り切れる）。「10進法でたまたまそうなるだけ」のパターンだが、ちょっと面白い。

同様にして、M₄₁, M₄₃, M₄₇, M₅₃ も分解できるはずなので、幾つか試してみてもいいだろう（こーゆーことは何度説明を読んでも真意が分からないもんだが、試しに自分でやってみると、感覚的に納得がいくかと…）。M₅₉ より先の分解は、難易度が上がる。一般には「P−1法」というテクニックが役立つ。そして、その「P−1法」を使っても M₁₄₉ の分解は不可能に近い（「楕円曲線法」を使えば分解できる）。現代の最先端の知見・最高速のコンピューターを利用しても、残念ながら p が3～4桁以上の Mersenne 合成数は、一般には分解できない。

「たった」1000桁の数が分解できないのに、何千万桁もある素数を見つけて喜んでいるのは、ある意味、むなしいことだ。魔法のランプから精霊が出てきて、願いを何でも一つかなえてくれるというのなら、ぜひ――「世界最大の素数を発見させてほしい」などという、くだらないことではなく――任意の整数に対する最も速い（既存のコンピューターで利用可能な）素因数分解のアルゴリズムをオープンソースで公開してほしい…。浮世離れした願いのようだが、因数分解の効率が十分に高まるとRSAベースの暗号化は無意味になるので、パスワード認証やオンライン決済などにおいて、俗世にも影響が生じるであろう。けれど、それは楕円に移行すればいいだけの話で、応用上の枝葉における一時の混乱に過ぎない。数論の発展の方が重要だ。数論の王子様（？）の Gauß 自身、この点を強調している（DA 329）。「かくもエレガントにして著名なる問題（＝素数性判定と素因数分解）の解明のためには、あらゆる方策が懸命に探求されねばなるまい。これは、科学の尊厳に関わる要求だと思われる」と。

Gauß 先生の境地に達するのは無理かもしれないが、整数論のエレガンスを「自分に分かる範囲」でささやかに探求することは、誰にでも許されるぜいたくだろう。

---