妖精現実

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

チラ裏

2021-10-14　複素整数「ゴルゴ13」　565+13i

g = 565+13i はガウス整数の範囲で素数だろうか、それとも分解されるのか？

a = 123+45i と g の最大公約数は何か？　（もし 1 でないとすれば、もちろんゴルゴ13は素数でない。）

まずは準備体操として、普通の整数の範囲での「ユークリッドの互除法」を思い出そう。

【例題】　3195億7869万7969 と 6385億0876万1014 の最大公約数は何か？

【互除法＝ユークリッドのアルゴリズム】　2個の整数が与えられる。大きい方を M、小さい方を N としよう。M と N の最大公約数を求めたい。

ステップ1　M を N で割る。割り切れれば、もちろん最大公約数は N そのものだが、割り切れない場合を考える。M の方がでかいのだから、商は1以上だが、商はとりあえず無視。問題は余り。余りが r₁ だったとする。

ステップ2　今度は N を割る。何で割る？　直前のステップの余り r₁ で割る。今度は余りが r₂ だったとしよう。

ステップ3　r₁ を r₂ で割って、余りを r₃ とする。

ステップ4　r₂ を r₃ で割って、余りを r₄ とする。

ステップ5　r₃ を r₄ で割って、余りを r₅ とする。

以下同様に、割り切れるまで（余りがゼロになるまで）続ける。ゼロでなかった最後の余りが、M と N の最大公約数。

さっそく上の例題に適用。

N = 319578697969
M = 638508761014
MをNで割る → 余り r1 = 318930063045
Nをr1で割る → 余り r2 = 648634924
r1をr2で割る → 余り r3 = 450315361
r2をr3で割る → 余り r4 = 198319563
r3をr4で割る → 余り r5 = 53676235
r4をr5で割る → 余り r6 = 37290858
r5をr6で割る → 余り r7 = 16385377
r6をr7で割る → 余り r8 = 4520104
r7をr8で割る → 余り r9 = 2825065
r8をr9で割る → 余り r10 = 1695039
r9をr10で割る → 余り r11 = 1130026
r10をr11で割る → 余り r12 = 565013
r11をr12で割る → 余り r13 = 0　割り切れた

従って、ゼロでなかった最後の余り r12 = 565013 が gcd(M,N) ということに。比較として、素因数分解を強行するなら…
　M = 2 × 565013 × 565039
　N = 565013 × 565613
…となって、同じ結論が得られるが、この分解を試行除算で行うと、何万回も割り算する必要がある。ユークリッドの互除法なら、たった13回の割り算で答えが出るのだから、桁違いに効率が良い。

もちろん重要なのは「なぜこのアルゴリズムでうまくいくのか」。

普通の整数の範囲での互除法の証明は、ウィキペディアなど、多くの場所で見ることができるだろう。例えばオンライン教科書『Elementary Number Theory: Primes, Congruences, and Secrets』
https://wstein.org/books/ent/ent.pdf
では、§1.1.2に当たる。同じアルゴリズムが一般の整域で通用するかどうかは、ケースバイケースで微妙だが、ガウス整数に関しては、それほど難しくない。

2021-10-13　123+45i と 678+90i の最大公約数

ピタゴラス・トリオも、フェルマーの最終定理の n=4 の場合も、ガウス整数の問題として考えるのが正道だろうし、多くの教科書に必ず出る話題だろうが、普通に群・環から始めると、結構だるい。

ここでは具体的な問題を考えてみたい。

【問題】　ガウス整数 a = 123+45i と b = 678+90i の最大公約数は何か？

これらの数を凝視すると「実部も虚部も3で割り切れる」。だから 3+3i が公約数だろうけど、それは最大だろうか？

そもそもガウス整数の大小とは…？　素朴な発想は、a と b をそれぞれ素因数分解してみることだろう。それで共通の素因数を全部抜き出して、それらを掛け算すれば、それが最大公約数に違いない。ただし、素因数分解は易しくない。

a = −i⋅3(1+i)(13+28i)

b = −i⋅3(1+i)(8+3i)(8+5i)

もし上記の分解を事実と認めるなら、単数倍の違いを無視して、最大公約数は 3(1+i) だろうが、どうやって上記のように分解されるのか。そもそも一意分解が成り立つのか…。

普通の整数の場合もそうだが、最大公約数を知りたいだけなら、素因数分解よりユークリッドの互除法の方が、単純で、効率が良い。ガウス整数でも、同じ方法を試してみたい。

複素数の範囲で　b/a = 5.0975… − i1.1332…

ガウス整数としては、b を a で割ると、割り切れずに、商が 5−i で余りが発生すると予想される。この余りを r₁ とすると…

b = a(5−i) + r₁ つまり r₁ = b − a(5−i) = 18−12i

同様に a/r₁ = 3.5769… + i4.8846… だから

a = r₁(4+5i) + r₂ つまり r₂ = a − r₁(4+5i) = −9+3i　余りが r₁ より「小さく」なった。良い兆候。

次に r₁/r₂ = −2.2 + 0.6i だから

r₁ = r₂(−2+i) + r₃ つまり r₃ = r₁ − r₂(−2+i) = 3+3i　余りが r₂ よりさらに「小さく」なった。

最後に r₂/r₃ = −1 + 2i　これで余りがゼロ、割り切れた！

互除法によれば、割り切れる1個手前の余り r₃ = 3+3i が a と b の最大公約数。ユークリッドのありがたみがよく分かる。素因数分解と比べると単純計算だし、厳密化も比較的簡単そうだ。まずは「最大公約数」の意味を定義して、次にガウス整数でも互除法ができることを示せばいいだろう。上記の例から「互除法を使うと、余りの絶対値がだんだん小さくなる。余りはガウス整数なので、有限の値からだんだん小さくなるとしたら、いつかはゼロになるしかない」ということが分かる。

2021-10-05　フェルマーの最終定理: n=4 の場合　ピタゴラス・トリオで遊んじゃえっ

3² + 4² = 5² や 5² + 12² = 13² のような性質を満たすトリオ (3, 4, 5), (5, 12, 13), …。トリオたちの一般的性質は、それ自体として面白いだけでなく、もっと深い事柄と結び付いている。前回、ガウス整数の方向に行きかけたが、気まぐれに方向転換して、今回は「フェルマーの最終定理の n=4 の場合」を考えてみたい。

4.　x⁴ + y⁴ = z⁴ を満たす正の整数 x, y, z は存在しない。

【証明】　「そのような x, y, z が存在して、次の関係を満たす」と仮定し、矛盾を導く。

1. x⁴ + y⁴ = z⁴　………　①
2. 言い換えれば　(x²)² + (y²)² = (z²)²　………　②

一般性を失うことなく x と y は互いに素と仮定できる（もし x と y の最大公約数 g が 1 でないなら、x/g, y/g, z/g をあらためて x, y, z と置けばいい）。

②において (x², y², z²) は互いに素なピタゴラス・トリオなので、前回の考察から、こう書ける:

1. x² = m² − n²
2. y² = 2mn
3. z² = m² + n²

ここで m, n は互いに素な正の整数で、一方が奇数・他方が偶数であり、m > n を満たす。x² が奇数、y² が偶数と仮定しているが、そのことによって一般性は失われない（もし偶奇が逆だったら、単に x と y の名前を入れ替えればいい）。

さらに（これも前回、具体的に経験したことだが）、ピタゴラス・トリオ (A, B, C) は C の大きさによってソートできる。そこで、上記の (x², y², z²) について、「①つまり②を成り立たせるような、最小の z² を選択した」と仮定しよう。もし正の整数解が一つ以上あるなら、当然その中で最小のトリオを見つけることができるので（解がたまたま一つ見つかったとして、最悪、それより小さい範囲を全数検索すればいい）、それを①②の解としよう。

以下で見るように、実際には「トリオの第3要素 C が平方数 z²」という条件を外してさえ、(x², y², C) の形のピタゴラス・トリオは一つも存在しない。

5.　奇数の平方は「4で割ると1余る数」。上記の x² は奇数なので、x は奇数、x² は「4で割ると1余る数」。そのためには、m が奇数で n が偶数でなければならない（そのとき m² は「4で割ると1余る数」、n² は4の倍数）。なぜならば、m と n の偶奇がその逆だとすると m² − n² は「4で割ると3余る数」になってしまい、x²（それは「4で割ると1余る数」である）と等しくなり得ない。今、偶数 n を n = 2k と書くと:

1. y² = 2mn = 2m(2k) = 4mk　　これは4の倍数
2. 両辺を4で割って　y²/4 = (y/2)² = mk

m と n は互いに素だから、m と k = n/2 も互いに素。ところが mk = (y/2)² は平方数だから、m と k もそれぞれ平方数。m = c², k = d² と書くと:

1. x² = m² − n² = (c²)² − (2k)² = (c²)² − (2d²)²
2. 移項して　x² + (2d²)² = (c²)²

従って、(x, 2d², c²) も互いに素なピタゴラス・トリオであり、x は奇数、2d² は偶数。だからこう書ける（M, N は、互いに素な正の整数）:

1. x = M² − N²
2. 2d² = 2MN　つまり　MN = d²
3. c² = M² + N²

6.　MN = d² は平方数だが、M と N は互いに素なので、M と N もそれぞれ平方数。M = a², N = b² と書くと:

1. c² = M² + N² = a⁴ + b⁴
2. つまり　a⁴ + b⁴ = c²　………　③

③から、(a², b², c) もピタゴラス・トリオ。しかし、それは矛盾である！　実際、上記の式変形を振り返ると:

1. c ≤ c² = m < m² + n² = z²

トリオの最後の数 c について、①では、この形の式を満たす最小の z² を選んだ。だから、z² より小さい正の整数 c が③の形を持つ…というのは、議論の前提に反する。

「①②を満たす最小の正の整数 z² を選んだとき…」と考えると、矛盾が生じる…。でも、①②の形のピタゴラス・トリオが一つ以上存在するなら、もちろんその中で最小のものを選べる。つまり、もっとさかのぼって、「①②の形のピタゴラス・トリオが一つ以上存在する」ということ自体が不可能なのである。これが示したいことだった。□

これは本当の意味での、フェルマーの定理であり、フェルマー自身によって、同様の考え方によって証明されたらしい。

フェルマーは n=4 以外の一般の場合についても証明できると考えたが、実際には「その証明を書くには、この余白は狭過ぎる」という有名な言葉を記したにすぎない。フェルマーの最終定理と呼ばれるものは、正確には「フェルマーの予想」だった。のほほんとした「余白が狭過ぎる」発言を出発点に、フェルマー自身の考えさえ超越して、数論は大発展。フェルマーの予想は、漫画で言えば手塚治虫の「火の鳥」のようなものだった。

そこから派生した数論的技術は、純粋にそれ自体として面白いだけでなく、現代のネット社会を裏で支えるツールとして、日常的に活用されている（セキュアな通信で使われる楕円曲線暗号のように）。フェルマーの最終定理がそうだったように、現代のネットを支える計算量の理論にも、核心部には「予想」が交じっている。証明されてない予想に基づいて、オンライン決済とかをしている…というのは、理論的には怖いことだが、予想の裏をかける数学の天才の発生確率より、人間をだます詐欺師の発生確率の方が桁違いに高いので、相対的に前者の心配は小さい。数学側の本音としては、むしろ予想が間違っていたと判明する方がエキサイティング。予想がきちんと証明されれば、それはそれで気持ちがいい。

2021-10-04　ピタゴラス・トリオで遊んじゃえっ　勉強だって遊んじゃえっ

1.　どの辺の長さも50以下の整数であるような直角三角形は、何種類あるか。言い換えると、x² + y² = z² を満たす50以下の正の整数の組み合わせは、何種類あるか。

ただし (x, y, z) と (y, x, z) については、同じ組み合わせと考える。例えば、
　　3² + 4² = 5² と 4² + 3² = 5²
…については、別の組み合わせとは考えず、同じトリオの順番を変えただけ、と見なす。

ピタゴラス・トリオそのものは古典的な問題で、本質的に異なる全てのトリオは

• (x, y, z) = (m² − n², 2mn, m² + n²)　………　（☆）

の形を持つことが知られている。ここで m, n は互いに素な正の整数で、偶奇が異なり、m > n。

ゴチャゴチャ考えるより、とりあえず全数検索！

\\pari
{
 c = 0; \\ counter
 for( x=1, 50,
  for( y=x, 50,
   if( issquare( x^2+y^2, &z ) && z <= 50,
    printf( "[%2d] %d^2 + %d^2 = %d^2\n", c++, x, y, z )
   )
  )
 )
}

…実行すると、ちょうど20種類、ぞろぞろ出てくる:

[ 1] 3^2 + 4^2 = 5^2
[ 2] 5^2 + 12^2 = 13^2
[ 3] 6^2 + 8^2 = 10^2
[ 4] 7^2 + 24^2 = 25^2
[ 5] 8^2 + 15^2 = 17^2
[ 6] 9^2 + 12^2 = 15^2
[ 7] 9^2 + 40^2 = 41^2
[ 8] 10^2 + 24^2 = 26^2
[ 9] 12^2 + 16^2 = 20^2
[10] 12^2 + 35^2 = 37^2
[11] 14^2 + 48^2 = 50^2
[12] 15^2 + 20^2 = 25^2
[13] 15^2 + 36^2 = 39^2
[14] 16^2 + 30^2 = 34^2
[15] 18^2 + 24^2 = 30^2
[16] 20^2 + 21^2 = 29^2
[17] 21^2 + 28^2 = 35^2
[18] 24^2 + 32^2 = 40^2
[19] 27^2 + 36^2 = 45^2
[20] 30^2 + 40^2 = 50^2

[3] は [1] の各項を2倍しただけ、[6] は [1] の各項を3倍しただけ、[8] は [2] の各項を2倍しただけ…この種の、つまらないトリオが多い。(x, y, z) がピタゴラス・トリオなら、任意の正の整数 k について (kx, ky, kz) もピタゴラス・トリオになるに決まってるのだから、互いに素なトリオだけを考えた方が良さそうだ。

そこで z <= 50 の後ろに && gcd(x,y)==1 を追加すると:

[ 1] 3^2 + 4^2 = 5^2
[ 2] 5^2 + 12^2 = 13^2
[ 3] 7^2 + 24^2 = 25^2
[ 4] 8^2 + 15^2 = 17^2
[ 5] 9^2 + 40^2 = 41^2
[ 6] 12^2 + 35^2 = 37^2
[ 7] 20^2 + 21^2 = 29^2

50までの範囲には、本質的に違うトリオは7種類しかない。こうなると、なかなか貴重品のように思えてくる。20以下の小さいトリオは:

3^2 + 4^2 = 9 + 16 = 25 = 5^2
5^2 + 12^2 = 25 + 144 = 169 = 13^2
8^2 + 15^2 = 64 + 225 = 289 = 17^2

美しい！！

互いに素という制約を付けた場合、上記の数値例から、「x と y は一方が偶数、他方が奇数で、偶奇が一致しない」と予想される（だとすると、z² は偶数と奇数の和で奇数、従って z は奇数）。実際、互いに素なのだから、両方偶数ということはあり得ない。両方奇数という可能性も排除するため、「奇数の平方を4で割ると1余る」ことに注目しよう。x² と y² が両方とも「4で割ると1余る数」だとすると、それらの和は「4で割ると2余る数」になるが、「4で割ると2余る数」を素因数分解した場合、素因数2が奇数個。そのような数は平方数ではなく、つまり z² の形を持ち得ない。

2.　ピタゴラス・トリオは、単位円上の「有理点」と結び付いている。ここで「有理点」とは、x-座標 と y-座標がどちらも有理数になるような点。

実際、条件 x² + y² = z² の両辺を z² で割ると:

(x/z)² + (y/z)² = 1　ここで p = x/z, q = y/z と置くと、ピタゴラス・トリオ (x, y, z) は単位円上の有理点 (p, q) に対応する。

逆に (p, q) が有理点なら、有理数の定義から、整数 x, y, z があって (p, q) = (x/z, y/z) と書けるのだから、ピタゴラス・トリオを見つけることは、単位円上の有理点を見つけることと本質的に同じ。ただし、例えば、トリオ (3, 4, 5) と (6, 8, 10) は、どちらも単位円上の同じ点 (3/5, 4/5) = (6/10, 8/10) に対応していて、1対1対応にはなっていない。1対1対応にしたければ「互いに素なトリオ」だけを考えればいい。

【疑問】　単位円上の有理点とは、どのような点か？

図を描くのが面倒なので、「倍角の公式（その2）」の図を再利用。

第一象限にある点 P の座標 (p, q) が有理数なら、青い直線 CP の傾き u も有理数: 実際 u = q/(1 + p) である。

（CP の傾きが u = OD に等しい理由は、C から D まで横座標が 1 増加するとき、縦座標が u 増加するから。）

逆に、青い直線の傾き u が有理数なら、P は有理点である。

【証明】　緑の単位円の方程式を x² + y² = 1 とする。青い直線の式は y = ux + u なので、前者に後者を代入すると、2次方程式になる。それを解くと（途中計算は、「倍角の公式（その2）」の「幾何学的な方法」参照）:

• p = (1 − u²) / (1 + u²)
• q = 2u / (1 + u²)

仮定により u は正の有理数なので、正の整数 m, n が存在して u = n/m と書ける。すなわち:

• p = (1 − (n/m)²) / (1 + (n/m)²) = (m² − n²) / (m² + n²)
• q = 2(n/m) / (1 + (n/m)²) = 2mn / (m² + n²)

p も q も、それぞれ2整数の比だから有理数。□

p = x/z, q = y/z なのだから、ピタゴラス・トリオは、
　　(m² − n², 2mn, m² + n²)
の形を持つ（x と y の大小関係は一定していない）。

これで冒頭の主張（☆）が確認された。

「m, n が互いに素」という条件は、そうでなければ (x, y, z) が互いに素にならないことから。従って m, n は両方とも偶数ということはない。また両方奇数だとすると (x, y, z) は全部偶数になってしまうので、それもない。つまり本質的に異なるピタゴラス・トリオだけを考えたい場合、言い換えれば (x, y, z) が互いに素という条件と付ける場合、必然的に m, n は互いに素で、偶奇が異なる。仮定より x = m² − n² は正の整数なので、m > n。

3.　ピタゴラス・トリオは、具体的にどのように、単位円上の有理点と対応しているか？

まず (3, 4, 5) だが…。上記の文脈においては「(3/5, 4/5) は単位円上の点」という意味。
　(3/5)² + (4/5)² = 25/25 = 1
なので、事実としては明白だが、三角関数的には…

arccos (3/5) = 0.927295218…
sin 0.927295218… = 4/5

θ = 0.927295218… ラジアンは、53.1301…度に当たる。何だか見覚えのある角度のような…？

(x, y, z) = (3, 4, 5) のとき、傾き u は？

このトリオを生成するのは (m, n) = (2, 1) なので、u = n/m = 1/2 となる。つまり:

θ/2 = arctan (1/2) = 0.463647609…
θ = 2 arctan (1/2) = 0.927295218…

見覚えのあるような θ = 0.927295218… の正体は、arctan (1/2) の2倍であった。

それは、もちろん複素数 3 + 4i の偏角でもある！

arg (3+4i) = 0.927295218…

他のピタゴラス・トリオも同様であり、ピタゴラス・トリオをガウス整数の問題として扱えることが示唆される（ありがちな展開）。ピタゴラス・トリオの性質は「原点からの距離が整数になるような、整数格子点」。言い換えると「ノルムが平方数であるようなガウス整数」。

何だか面白くなってきた。何して遊ぼっか？　ここからどこに行こっか？

チラ裏より

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

• 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-18　1 の √2 乗は単位円上で稠密　整数の偏角も稠密
• 2021-04-28　「宇宙の実装」と日常生活　助からないと思っても助かっている
• 2021-04-07　双曲線の計算地獄…と天国（その2）
• 2021-04-04　目で見る複素三角関数cos　赤いリボンもキリリッと
• 2021-04-06　√1−z² = √1+z√1−z はOK、√z²−1 = √z+1√z−1 は駄目
• 2021-03-21　cot の逆関数　びっくり！！ 君の教科書もまっ赤なうそ！
• 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　木星・土星は外惑星なのに、太陽のそばで合になりたがる？
• メモ（チラ裏）一覧