妖精現実

[ 新着記事 | 数学・プログラミング | 天文・暦
| シリア語・Unicode・詩 | ジョーク | 漫画・アニメ
| 字幕 | 哲学・ファンタジー | 全記事 | チラ裏 ]

チラ裏

2021-10-25　「ゴルゴ13」分解計画（その2）　ユークリッドの互除法

10.　互除法は、最大公約数を求める有力なツール。「最大公約数なんて、小学校の算数。分かり切ったこと」…と油断してはならない。ガウス整数（別名: 複素整数）のような「より一般的な世界」においては、そもそも最大公約数とは何か？が問題となり、「この二つの数には、最大公約数がない」という奇妙な現象さえ起こり得る。

具体例として、自然数の範囲で gcd(1326, 570) を求めてみる。

1. ①　1326 を 570 で割ると 186 余る。
2. ②　570 を 186 で割ると 12 余る。
3. ③　186 を 12 で割ると 6 余る。
4. ④　12 を 6 で割ると、割り切れる。

最後の余り 6 が 1326 と 570 の最大公約数。計算の仕方は、「A を Ｂ で割ると C 余る。B を C で割ると D 余る。C を D で割ると E 余る…」という単純な繰り返しを割り切れるまで、続けるだけ。

④ から、12 は 6 の倍数（言い換えれば 6 は 12 の約数）。③ は
　　【ア】　186 = 12c + 6　…ここで c は 186 を 12 で割った整数商（つまり15）
という意味だが、12 は 6 の倍数であり（④で確認済み）、それを c 倍した 12c も当然 6 の倍数。さらに、6 自身はもちろん 6 の倍数なので、
　　186 = 12c + 6 = 6の倍数 + 6の倍数
…も、6 の倍数。これで 186 も 6 の倍数であることが確認された。

同様に ② は
　　【イ】　570 = 186b + 12　…ここで b は 570 を 186 で割った整数商（つまり3）
という意味だが、186 は 6 の倍数（③で確認済み）、12 も 6 の倍数（④で確認済み）なので、それらの和 570 も 6 の倍数であることが分かる。

さらにさかのぼって ① は
　　【ウ】　1326 = 570a + 186　…ここで a は 1326 を 570 で割った整数商（つまり2）
という意味だが、570 は 6 の倍数（②で確認済み）、186 も 6 の倍数（③で確認済み）なので、それらの和 1326 も 6 の倍数であることが分かる。

以上によって、1326 も 570 も 6 の倍数、言い換えると 6 は両者の公約数。…ここまでは簡単だが、それが「最大」公約数だという証拠は、どこにあるのか。

今 1326 と 570 に、何らかの公約数 x があったとしよう（実際 x=2 などがあるが、もっと大きい公約数もあるかもしれない）。言い換えると、1326 と 570 はどちらも整数 x の倍数だと仮定する。このとき【ウ】から
　　186 = 1326 − 570a
となるが、仮定により 1326 も 570a も x の倍数なので、それらの差 186 も x の倍数（☆）。なぜなら
　　1326 = mx, 570a = nx とすると 186 = mx − nx = (m − n)x　…ここで m, n, m − n は整数。

同様に【イ】から
　　12 = 570 − 186b
となるが、仮定により 570 は x の倍数、（☆）より 186b も x の倍数なので、それらの差 12 も x の倍数（☆☆）。さらに【ア】から
　　6 = 186 − 12c
となるが、（☆）より 186 は x の倍数、（☆☆）より 12c も x の倍数なので、それらの差 6 も x の倍数。

結局、1326 と 570 にどんな公約数 x があるにせよ、必ず 6 は、その x の倍数。言い換えれば x は 6 の約数であり、従って 6 以下。これで 6 が「最大」公約数であることが分かった。

1326 と 570 に限らず、数値が何であっても、同様の議論が成り立つので、上記の方法（ユークリッドの互除法）によって、自然数の範囲であれば、最大公約数を求めることができる。

以上をきちんとした証明の形にすると、商 q₁, q₂, q₃, … と余り r₁, r₂, r₃, … についての数学的帰納法になる。きちんとしたい方は、自分で書いてみるか、教科書などを見てください…。本題はそれではなく「同じことがガウス整数の世界でも通用するのか」。

11.　上記の例に倣って「最大公約数」を再定義しよう。要素の間で、足し算・引き算・掛け算ができる世界 W を考える。W の2要素 a, b の最大公約数 g = gcd(a, b) とは、W における a と b の公約数のうち、次の性質を持つものである。
　　性質　「a と b の任意の公約数 x は、g の約数である」

少し分かりにくい…。まず「約数」とは何だろうか。「d が a の約数」ということは「a は d の倍数」ということであり、つまり d を何倍かすると a になるという意味。言い換えると、a = dq を満たすような q ∈ W が存在する、という意味。例えば、自然数の世界 N において 2 が 12 の約数であるということは、12 = 2q を満たす q ∈ N が存在するということ。そのような q は、もちろん存在する（q = 6）。同様に、12 = 3q も 12 = 4q も自然数の解を持つから、3 も 4 も 12 の約数だが、一方 12 = 5q は N の範囲に解を持たないから、自然数の世界において 5 は 12 の約数ではない。

a と b の公約数とは、「a の約数であり、b の約数でもあるような要素」。

当たり前のことをややこしく言ってるようだが、ここで思わぬ展開が…

「足し算・引き算・掛け算ができる世界」を考えているのだから、自然数の世界は、その前提を満たしていない（自然数の世界では、例えば 2 − 5 が定義されない）。もうちょっと広く、整数の世界 Z で考える必要がある。そうすると、1326 と 570 の最大公約数は最初に見たように 6 でもいいのだが、−6 も「1326 と 570 の最大公約数」の定義を満たす。1326 と 570 の任意の公約数 x は −6 の約数だから。

つまり「最大」公約数の「最大」は、もはや単純な大小関係ではない。そうではなく、親分・子分のような関係なのだ。

チンピラ「おれさまは 2。おれさまの空手を受けてみろ。1326 も 570 も割れてしまうぜ」

別のチンピラ「おれさまは 3。おれさまの空手を受けてみろ。1326 も 570 も割れてしまうぜ」

親分「おれさまは 6。てめえらは全員、おれさまの約数、雑魚だぜ。1326 と 570 を割ることにかけては、おれさまがボスだ」

もちろん −6 も同じことを言えるのだが、−1 倍の違いについては、こだわらない。このポリシーを「単数倍の違いを無視」と表現する。ここで「単数」とは 1 の約数のこと。通常の整数では 1 と −1 が単数であり、ガウス整数ではそれらに加えて i と −i も単数。整数の世界では、約数にせよ、素因数分解にせよ、単数倍の違いについてはあまり気にしない。自然数の世界でも、1 は単数。「なぜ 1 は素数でないのか」「素因数分解のとき × 1 を付け加えてはいけないのか」というのは、よくある疑問だが、これも「単数倍の違いについては考えない」ということに他ならない。1 は素数でもなく合整数でもなく単数というわけ。

新しい意味での最大公約数は、公約数のボス。「公約数のボス」とは、どんな公約数も自分の約数（いわば子分）として従属させているような存在。複素数であるガウス整数の世界では、例えば「−2 + 2i と −4 は、どちらが大きいのか」といわれても、簡単には答えようがない…「数が大きい・小さい」というコンセプトに執着して「最大」を定義しようとすると、無理が生じる。

これで、ガウス整数の互除法を考える準備が、半分整った。565+13i すなわち複素整数「ゴルゴ13」が完全にバラバラになる日も、そう遠くあるまい…。

2021-10-23　「ゴルゴ13」分解計画　565+13i

8.　諸行無常、万物は流転する。有名な殺し屋ゴルゴにも、ついに自分がバラされる日が…？　それとも 565+13i は、分解不可能な複素整数だろうか。

われわれは極秘裏に調査を開始した（謎）。

ミッション1　13 は 2² + 3² に等しい。565 も 2個の平方数の和として書けるか？

ミッション2　素数2は、複素整数の範囲では (1+i)(1−i) と分解される。G = 565+13i は、複素整数の範囲では分解可能か？

最初のミッションは、フェルマーの「2平方の定理」の一般形に当たる。4k+1型の素数（愛称: バニラ素数）は2平方数の和として書けるが、4k+3型の素数（愛称: チョコレート素数）は2平方数の和として書けない。565は、5の倍数。素数じゃないので、判定法はもう少しややこしい。「こんな小さい数、全数検索だっ！」…と言いたいところだが、まぁスナイパーのゴルゴに敬意を払い、ここはブルートフォースでなく、精密に考察する方向で…

まずは、普通に有理素数に分解: 565 = 5 × 113。どちらの因子もバニラ素数なので、ガウス整数の範囲では、さらに分解される:
　　　5 = 1² + 2² = (1 + 2i)(1 − 2i)
　　　113 = 7² + 8² = (7 + 8i)(7 − 8i)

バラバラになったゴルゴ。5を分解した因子と、113を分解した因子を一つずつ組み合わせて、例えば、こう書ける:
　　　(1 + 2i)(7 + 8i) = −9 + 22i
　　　(1 − 2i)(7 − 8i) = −9 − 22i
　　　つまり　5 × 113 = (−9 + 22i)(−9 − 22i) = (−9)² + 22² = 81 + 484 = 565

もう1パターンの組み合わせ方を使うと:
　　　(1 + 2i)(7 − 8i) = 23 + 6i
　　　(1 − 2i)(7 + 8i) = 23 − 6i
　　　つまり　5 × 113 = (23 + 6i)(23 − 6i) = 23² + 6² = 529 + 36 = 565

結論として、足す順序と平方される数の符号を無視すると、565 は2通りの方法で2平方数の和となるようだ: 6² + 23² = 9² + 22²。

これで第1のミッションは一応完了。「普通の整数の問題でも、あえてガウス整数などの広い範囲で考えることで、簡単になる場合がある」という好例だろう。

9.　上記の議論を検討すると、バニラ素数を2平方数の和にする部分が、透明になっていない。5 = 1² + 2² はともかく、113 = 7² + 8² はそれほど明らかではない。任意の大きいバニラ素数、例えば 565013 について、全数検索せずに、2平方の和の形…
　　　565013 = 238² + 713²
…にするアルゴリズムが欲しい。ここで役立つのが、フェルマーの小定理の考え方: p が素数なら、2以上 p 未満の任意の整数 b について
　　　b^p−1 ≡ 1 (mod p)
が成り立つが、このような b の中には、p−1乗して初めて ≡ 1 になる数（原始根）がある。そのような b を選んで固定する。今、p を奇数とすると、(p−1)/2 は整数であり、
　　　q ≡ b^(p−1)/2 と置くと q² ≡ b^p−1 ≡ 1 (mod p)
ここで b は、p−1乗して初めて ≡ 1 になるのだから、(p−1)/2乗では ≡ 1 にならない。つまり q は ≡ 1 ではないが、2乗すると ≡ 1 になる数であり、要するに q ≡ −1 だろう［※注1］。さらに、p を4k+1型の素数（バニラ素数）に限定した場合、(p−1)/4 も整数であり、上記と同様に
　　　r ≡ b^(p−1)/4 と置くと r² ≡ q ≡ −1 (mod p)
　　　つまり　r² + 1 ≡ 0 (mod p)
これは
　　　自然数 r² + 1 を p で割ると 0 余る
　　　つまり　r² + 1 = (r + i)(r − i) は p の倍数　………　（☆）
という意味。

［※注1］　q² ≡ 1 つまり q² − 1 = (q + 1)(q − 1) ≡ 0 なので、(q + 1)(q − 1) は p の倍数。p は素数なので、(q + 1) または (q − 1) は p の倍数（下記参照）。後者が p の倍数なら q − 1 ≡ 0, q ≡ 1 だが、仮定よりそうではない。だから前者が p の倍数で q + 1 ≡ 0, q ≡ −1。…素数位数の有限体という観点からは、
(q + 1)(q − 1) ≡ 0
の時点で「整域には零因子がないので、どちらかの因数が ≡ 0」とも言える。

p = x² + y² の整数解を使って、ガウス整数の範囲では
　　　p = (x + yi)(x − yi)　………　（☆☆）
　　　α = x + yi, β = x − yi と置くと　p = αβ
という素因数分解が成り立つ。問題は、どうやって x, y の値を決定するか。

拡張された世界での「素数の定義」を思い出そう。α が素数ということは、その世界において、
　　　任意の積 AB が α の倍数のとき、必ず A または B が α の倍数になる
という意味だった。A = r + i, B = r − i と置くと、（☆）から
　　　AB = (r + i)(r − i) は p の倍数
ここで p は α の倍数なので、AB も α の倍数。α はガウス整数の素数だから、素数の定義から A または B は α の倍数。必要に応じて y の符号を逆にすることにより「A が α の倍数」と決め付けて差し支えない。すなわち…
　　　A = r + i は α = x + yi の倍数
　　　言い換えると　α = x + yi は A = r + i の約数

（☆☆）によると α = x + yi は p の約数でもあるので、α の値を得るためには、A = r + i と p の公約数を考えればいい。A と p の最大公約数は、互除法により機械的に決定され、それが求める α。

なぜ「最大」公約数と言い切れるか。…仮に α が最大公約数でないとすると、A/α と p/α = β には、まだ単数以外の公約数が残っている。けれど β は素数なので、単数倍の違いを無視すると、約数は β 自身しかない。だから、公約数があるとすれば A/α も β で割り切れる（言い換えると A が αβ = p で割り切れる）。それは不可能。というのも A = r + i を自然数 p で割ると r/p + i/p になるが、その虚部は整数でない。つまり、ガウス整数として割り切れない。

このアルゴリズムでは、q ≡ b^(p−1)/2 ≡ −1 (mod p) が必要条件。b が原始根であることは、（十分条件だが）必要条件ではない。例えば p = 13 のとき b = 5 は条件を満たす: q ≡ 5^12/2 ≡ −1 (mod 13)。この場合、5⁴ ≡ 1 (mod 13) なので 5 は原始根ではないが、それでも構わない: r ≡ 5^12/4 ≡ 8 を使って gcd(r + i, p) = 3 + 2i から 3² + 2² = 13 が得られる。

これで大ざっぱな見通しは立ったが、まだ細部は穴だらけ。大前提となる「ガウス整数の世界でも最大公約数が存在して、互除法が通用する」ということも、メインの武器となる2平方の定理も、証明が必要。それらは後回しにして、とりあえず具体例で結果の確認。113 = 7² + 8² を上記のアルゴリズムで求めてみる。

b = 2 は、条件を満たさない: q ≡ 2^112/2 ≡ 1 (mod 113)。

b = 3 は、条件を満たす: q ≡ 3^112/2 ≡ −1 (mod 113)。このとき r ≡ 3^112/4 ≡ 98。

＜検算＞　r² = 98² = 9604 = 85 × 113 − 1 ≡ −1 (mod 113)

あとは 98 + i と 113 の最大公約数を求めればいい:

1. 113 を 98 + i で割る → 商は 1、余り 15 − i
2. 98 + i を 15 − i で割る → 商は 6、余り 8 + 7i
3. 15 − i を 8 + 7i で割る → 商は 1 − i で割り切れる

最後の余りが最大公約数 α = 8 + 7i なので、x = 8, y =7。これで 113 = 8² + 7² = 7² + 8² が得られた。ガウス整数の互除法は、決定論的ではない。例えば、こうしてもいい:

1. 113 を 98 + i で割る → 商は 1、余り 15 − i
2. 98 + i を 15 − i で割る → 商は 7、余り −7 + 8i　［※注2］
3. 15 − i を −7 + 8i で割る → 商は −1 − i で割り切れる

複素数の範囲で (98 + i) / (15 − i) = 6.5 + 0.5i なので、ガウス整数としての商（の近似値）は、実部が 6 or 7、虚部が 0 or 1 のどれでも、誤差は等しい。

［※注2］　ここで得られた最大公約数 −7 + 8i は、最初に得られた 8 + 7i と少し異なるが、後者を i 倍すると前者、前者を −i 倍すると後者。つまり両者の違いは単数倍の違いにすぎず、どちらでも本質的に同じ。

チラ裏より

「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。

• 2021-10-04　ピタゴラス・トリオで遊んじゃえっ　勉強だって遊んじゃえっ
• 2021-10-05　フェルマーの最終定理: n=4 の場合　ピタゴラス・トリオで遊んじゃえっ
• 2021-09-05　思い出の漫画（3）　篠有紀子「パラレル」
• 2021-09-01　メール・プロバイダの安全性　あなたのメアドは何点？　定量的分析の一例
• 2021-08-23　思い出の漫画（2）　岩館真理子「街も星もきみも」
• 2021-08-22　思い出の漫画（1）　岡田あーみん「ルナティック雑技団」
• 2021-07-16　アボガドロ定数の音楽　6020垓（がい）　602 sextillion
• 2021-06-29　ProtonMail からの乗り換え先　プライバシー重視のウェブメール
• 2021-05-29　動画注意報: madVRの色スケールがTV（16-235）になってしまう
• 2021-05-08　log (1 + i) とか　複素関数って値の変数名がwで草
• 2021-04-09　¼↑↑∞ = ½　有理数に収束する無限タワー
• 2021-04-10　目で見る i 乗　テツコのベルギーワッフル
• 2021-04-14　ω 乗
• 2021-04-04　目で見る複素三角関数cos　赤いリボンもキリリッと
• 2021-03-01　∫sec x dx　グーデルマン関数とか
• 2021-03-29　【動画作成】注意報　Vorbis/Opus音声はリスキー　直してほしいVLCのバグ
• 2021-02-12　2項定理　ばかばかしいけど分かりやすい（？）説明
• 2021-02-07　「シェルバトフの名著」とは
• 2021-01-10　フィボナッチ数列の一般項の公式　一番簡単な方法？
• 2020-12-22　木星・土星は外惑星なのに、太陽のそばで合になりたがる？
• メモ（チラ裏）一覧