チラ裏バッファ: 数学4

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

数学 / 2 / 3 / 4 / Curios / 野蛮

***

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

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

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

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

の形を持つことが知られている。ここで 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 は一方が偶数、他方が奇数で、偶奇が一致しない」と予想される(だとすると、z2 は偶数と奇数の和で奇数、従って z は奇数)。実際、互いに素なのだから、両方偶数ということはあり得ない。両方奇数という可能性も排除するため、「奇数の平方を4で割ると1余る」ことに注目しよう。x2 と y2 が両方とも「4で割ると1余る数」だとすると、それらの和は「4で割ると2余る数」になるが、「4で割ると2余る数」を素因数分解した場合、素因数2が奇数個。そのような数は平方数ではなく、つまり z2 の形を持ち得ない。

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

実際、条件 x2 + y2 = z2 の両辺を z2 で割ると:

(x/z)2 + (y/z)2 = 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対応にしたければ「互いに素なトリオ」だけを考えればいい。

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

PNG画像32: 原点Oを中心とする半径1の緑の円を考える。点(−1, 0)をC、円周上の別の点をPとし、CPは青い直線で結ばれているとする。OPと正のx-軸が成す角をθとする。Pからx-軸に下ろした垂線の足をTとする。CPとy-軸の交点をDとし、線分ODを「赤い部分」と呼ぶ。点Dの座標を(0, u)とすると、「赤い部分」はuに当たる。

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

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

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

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

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

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

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

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

これで冒頭の主張(☆)が確認された。

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

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

まず (3, 4, 5) だが…。上記の文脈においては「(3/5, 4/5) は単位円上の点」という意味。
 (3/5)2 + (4/5)2 = 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-10-05 フェルマーの最終定理: n=4 の場合 ピタゴラス・トリオで遊んじゃえっ

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

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

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

  1. x4 + y4 = z4 ……… ①
  2. 言い換えれば (x2)2 + (y2)2 = (z2)2 ……… ②

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

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

  1. x2 = m2 − n2
  2. y2 = 2mn
  3. z2 = m2 + n2

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

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

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

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

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

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

  1. x2 = m2 − n2 = (c2)2 − (2k)2 = (c2)2 − (2d2)2
  2. 移項して x2 + (2d2)2 = (c2)2

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

  1. x = M2 − N2
  2. 2d2 = 2MN つまり MN = d2
  3. c2 = M2 + N2

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

  1. c2 = M2 + N2 = a4 + b4
  2. つまり a4 + b4 = c2 ……… ③

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

  1. c ≤ c2 = m < m2 + n2 = z2

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

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

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

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

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

***

2021-10-13 123+45i と 678+90i の最大公約数 「ゴルゴ13」分解計画への前奏曲

7. ピタゴラス・トリオも、フェルマーの最終定理の 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 で余りが発生すると予想される。この余りを r1 とすると…

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

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

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

次に r1/r2 = −2.2 + 0.6i だから

r1 = r2(−2+i) + r3 つまり r3 = r1 − r2(−2+i) = 3+3i 余りが r2 よりさらに「小さく」なった。

最後に r2/r3 = −1 + 2i これで余りがゼロ、割り切れた!

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

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以上だが、商はとりあえず無視。問題は余り。余りが r1 だったとする。

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

ステップ3 r1 を r2 で割って、余りを r3 とする。

ステップ4 r2 を r3 で割って、余りを r4 とする。

ステップ5 r3 を r4 で割って、余りを r5 とする。

以下同様に、割り切れるまで(余りがゼロになるまで)続ける。ゼロでなかった最後の余りが、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-23 「ゴルゴ13」分解計画 565+13i

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

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

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

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

***

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

まずは、普通に有理素数に分解: 565 = 5 × 113。どちらの因子もバニラ素数なので、ガウス整数の範囲では、さらに分解される:
   5 = 12 + 22 = (1 + 2i)(1 − 2i)
   113 = 72 + 82 = (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)2 + 222 = 81 + 484 = 565

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

結論として、足す順序と平方される数の符号を無視すると、565 は2通りの方法で2平方数の和となるようだ: 62 + 232 = 92 + 222

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

***

9. 上記の議論を検討すると、バニラ素数を2平方数の和にする部分が、透明になっていない。5 = 12 + 22 はともかく、113 = 72 + 82 はそれほど明らかではない。任意の大きいバニラ素数、例えば 565013 について、全数検索せずに、2平方の和の形…
   565013 = 2382 + 7132
…にするアルゴリズムが欲しい。ここで役立つのが、フェルマーの小定理の考え方: p が素数なら、2以上 p 未満の任意の整数 b について
   bp−1 ≡ 1 (mod p)
が成り立つが、このような b の中には、p−1乗して初めて ≡ 1 になる数(原始根)がある。そのような b を選んで固定する。今、p を奇数とすると、(p−1)/2 は整数であり、
   q ≡ b(p−1)/2 と置くと q2 ≡ bp−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 と置くと r2 ≡ q ≡ −1 (mod p)
   つまり r2 + 1 ≡ 0 (mod p)
これは
   自然数 r2 + 1 を p で割ると 0 余る
   つまり r2 + 1 = (r + i)(r − i) は p の倍数 ……… (☆)
という意味。

[※注1] q2 ≡ 1 つまり q2 − 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 = x2 + y2 の整数解を使って、ガウス整数の範囲では
   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 ≡ 512/2 ≡ −1 (mod 13)。この場合、54 ≡ 1 (mod 13) なので 5 は原始根ではないが、それでも構わない: r ≡ 512/4 ≡ 8 を使って gcd(r + i, p) = 3 + 2i から 32 + 22 = 13 が得られる。

***

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

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

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

<検算> r2 = 982 = 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 = 82 + 72 = 72 + 82 が得られた。ガウス整数の互除法は、決定論的ではない。例えば、こうしてもいい:

  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-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 を B で割ると 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)
という意味だが、186b は 6 の倍数(【ア】で確認済み)、12 も 6 の倍数(④で確認済み)なので、それらの和 570 も 6 の倍数であることが分かる。

さらにさかのぼって ① は
  【ウ】 1326 = 570a + 186 …ここで a は 1326 を 570 で割った整数商(つまり2)
という意味だが、570a は 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 に限らず、数値が何であっても、同様の議論が成り立つので、上記の方法(ユークリッドの互除法)によって、自然数の範囲であれば、最大公約数を求めることができる。

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

11. 上記の例に倣って「最大公約数」を再定義しよう。要素の間で、足し算・引き算・掛け算ができる世界 W を考える。W の2要素 a, b の最大公約数 g = gcd(a, b) とは、W における a と b の(0以外の)公約数のうち、次の性質を持つものである。
  性質 「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-30 「ゴルゴ13」分解計画(その3) ガウス整数での互除法

12. 自然数の互除法が、必ず終了(成功)する理由は単純: 自然数 a を自然数 b で割ったとき、余り r は、割る数 b より小さくなる。

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

「その r で割ったときの、そのまた余り」は r よりさらに小さくなる。…こうして、余りたちは、先へ行くほどだんだん小さくなるけど、負にはならないのだから、いつかは 0 になるしかない(つまり余りゼロで割り切れる)。この考え方は、負の整数を含めた整数の範囲の互除法でも、ほとんどそのまま成り立つ。けれど、ガウス整数の範囲で、
  「α を β で割ると ρ 余る」「そして ρ は β より小さい」
というコンセプトを成立させることは可能だろうか…。

例えば 10 + 5i を 5 で割ると、割り切れて、商は 2 + i。そのことから、直観的に、例えば:
  【ア】 10 + 8i を 5 で割ると、商が 2 + i で 3i 余る
  【イ】 そして 3i は 5 より「小さい」

この考えで正しいか?

13. 複素整数 α を複素整数 β で割ったとき、商が ϙ で余りが ρ になるということは:
  α = βϙ + ρ ここで ϙ, ρ も複素整数

注 ϙ(コッパ)は q に当たる古いギリシャ文字。

例えば 11 を 4 で割ると商が 2 で余りが 3。そのくらいなら簡単に暗算できるが、この「商が 2」という部分は、11/4 = 2.75 の端数を切り捨てた近似値と考えることもできる。

同様に、複素整数の商 ϙ としては、複素数 α/β に一番近い複素整数を近似値として選ぶことができる。【ア】の例では…
  (10 + 8i) / 5 = 2 + 1.6i に一番近い複素整数は 2 + 2i
…なのだから、次のように考えた方が「近似精度が高い」:
  【ウ】 10 + 8i を 5 で割ると、商が 2 + 2i で −2i 余る
  (余りは 10 + 8i から 5 を 2 + 2i 回、引いたもの)
  【エ】 そして −2i は 5 より「小さい」

【ア】【イ】の計算も間違ってないが、その余り 3i より【ウ】【エ】の余り −2i の方が、絶対値が小さい。アルゴリズムとしては…
  複素数の範囲で α = A + Bi を β = C + Di で割る(A, B, C, D は普通の整数)。
  ゴチャゴチャするが、ただの割り算なので、次のように(分母を有理化して)普通に計算できる。
  α/β = (A + Bi) / (C + Di) = [(A + Bi)(C − Di)] / [(C + Di)(C − Di)]
  = [(AC + BD) + (BC − AD)i] / (C2 + D2)
  = (AC + BD) / (C2 + D2) + [(BC − CD) / (C2 + D2)]i

結果の実部 s = (AC + BD) / (C2 + D2) も虚部 t = (BC − AD) / (C2 + D2) も有理数。それらに一番近い整数をそれぞれ S, T として
  ϙ = S + Ti
を「ガウス整数の世界での α 割る β の整数商」とすればいい。s または t にちょうど 0.5 の端数がある場合、「一番近い整数」の意味が曖昧だが、便宜上、そのときは絶対値が小さい方を選ぶ、とでもしておこう。いずれにしても、α 割る β の商を ϙ とすると、自動的に余りは、
  ρ = α − βϙ
となる。その意味は…
  「余りが“最小”になるように α から β を何回引けますか?」
  「ϙ回、引けますよ。ϙ回、引けば余りは α − βϙ ですね」
ρ は(さらに“小さく”できないという意味において)最善の余り。

14. ここで「余り ρ が、割る数 β より“小さく”なる」という意味を明確にしよう。素朴に考えると、絶対値で大小を区別できる。例えば、複素整数 β = C + Di の絶対値は
  |β| = √(C2 + D2)

このアイデアは「大小の区別」という点ではパーフェクトだが、値が実数。実数の世界では「だんだん小さくなるが、負にならないので、いつかは0になる」という「互除法の証明の仕方」が通用しない。例えば
  5.1, 5.01, 5.001, 5.0001, 5.00001, …
という列は、だんだん小さくなるものの、無限に続けても0にはならない。そこで一工夫して、絶対値の2乗を大きさの基準としよう。
  size(β) = |β|2 = C2 + D2
邪魔くさい根号もなくなり、すっきり。

複素整数を考えているので C, D などは整数。すると、関数 size() の値は、整数の2乗と整数の2乗の和なので 0以上の整数。余り ρ が 0 なら(そしてそのときに限って)、size(ρ) = 0 となる。この size() で測った「余りのサイズ」が、割る数 β のサイズより必ず小さくなることを示せば、ガウス整数の世界でも互除法が成立する。実際、0以上の整数の範囲で、だんだん小さくなるものは、いつかは0になるしかない。つまり、互除法を続けると、いつかは余りがゼロになって割り切れる!

前記のように α = A + Bi を β = C + Di で割って、こうなるとしよう:
  複素数としての商 α/β = s + ti (割り算が成立する前提として β ≠ 0 とする
  ガウス整数としての商 ϙ = S + Ti
  余り ρ = α − βϙ  ……… (☆)

size(ρ) < size(β) を示したい。大ざっぱには、余りと割る数の比 ρ/β のサイズが1未満で、「余り ρ から、もうこれ以上 β を引けない」みたいな状況(引き算自体はできるが、引き算すると、余りのサイズがかえってでかくなり逆効果)。α, β の定義と(☆)から:
  ρ/β = (α − βϙ) / β = α/β − ϙ
  = (s + ti) − (S + Ti) = (s − S) + (t − T)i
  要するに ρ/β = (s − S) + (t − T)i  ……… (☆☆)

S, T は、それぞれ s, t に一番近い整数なので、s − S も t − T も、絶対値 ½ 以下。従って(☆☆)の両辺の絶対値の2乗を考えると:
  |ρ/β|2 = (s − S)2 + (t − T)2 ≤ (½)2 + (½)2 = ½
  両辺を |β|2 倍して |ρ|2 ≤ ½ × |β|2 < |β|2  (15.参照)
   注: |β|2 = 0 の可能性があるなら、最後の < は ≤ になるが、
   β ≠ 0 なので、その可能性はない

  つまり size(ρ) < size(β)

これが示したいことだった!

幾何学的イメージとしては、ガウス整数は、複素平面上の格子点(格子は、辺の長さ1の正方形)。複素数の範囲での商 α/β は、α と β−1 の積で、どこだか分からないけれど、とにかく複素平面上のどこかの点に当たる。そして、複素平面全体が正方形の格子で覆われているのだから、その点がどこにあるとしても、必ず近くに格子点(=ガウス整数)がある。最悪のパターン(格子点があまり近くにない)は、正方形のど真ん中に点がある場合だが、その場合でも、最寄りの格子点とのずれは、実部・虚部それぞれ ½ を超えない。

15. 上記では |ρ/β|2 ≤ ½ の両辺を |β|2 倍して
  |ρ|2 ≤ ½ × |β|2
を得た。この計算の根拠は「絶対値同士の積は、積の絶対値」ということ(そして不等式の両辺に正の数を掛けても、不等号の向きは変わらない)。…それは実数の範囲では、当たり前: 例えば ±2 と ±3 の積は、符号次第で 6 または −6 だが、いずれにせよ絶対値は 6。先に絶対値を考えても、±2 の絶対値は 2、±3 の絶対値は 3、両者の積は 6。…複素数の範囲でも、機械的計算で、この事実を確かめることができる。任意の2個の複素数
  X = A + Bi, Y = C + Di
について:
  |X| = √(A2 + B2), |Y| = √(C2 + D2) なので
  |X| |Y| = √[(A2 + B2)(C2 + D2)]
  …根号内を展開すると A2C2 + A2D2 + B2C2 + B2D2 (★)
一方、先に積を計算すると:
  XY = (A + Bi)(C + Di) = (AC − BD) + (AD + BC)i なので
  |XY| = √[(AC − BD)2 + (AD + BC)2]
  …根号内を展開すると A2C2 − 2ABCD + B2D2 + A2D2 + 2ABCD + B2C2
  ±2ABCD は打ち消し合ってなくなるので、これは(★)と等しい。

要するに |X| |Y| = |XY|  (絶対値同士の積は、積の絶対値)

従って(X = ρ/β, Y = β とすると):
  |ρ/β|2 × |β|2 = |ρ/β| × |ρ/β| × |β| × |β|
  = (|ρ/β| × |β|) × (|ρ/β| × |β|)  ← 丸かっこ内は絶対値同士の積
  = |(ρ/β) × β| × |(ρ/β) × β|  ← 積の絶対値
  = |ρ| × |ρ| = |ρ|2

ところで、(★)の計算と全く同様に、次の二つの値は等しい:
  |X|2 |Y|2 = (A2 + B2)(C2 + D2)
  |XY|2 = (AC − BD)2 + (AD + BC)2
絶対値の2乗を「サイズ」と定義したのだから、次のように書くことができる:
  size(X) size(Y) = size(XY)

この size() は、ノルム(norm)と呼ばれるもので、ガウス整数の場合は「絶対値の2乗」だが、もう少し一般化した議論では、通例「ノルムとは、共役の数との積」と定義される。任意のガウス整数
  α = x + yi (x, y は普通の整数)
について言えば、その共役複素数 x − yi もガウス整数であり、両者の積…
  (x + yi)(x − yi) = x2 + y2
…つまり α のノルムは、絶対値の2乗 size(α) = |α|2 と同じ値。定義だけでは、何の役に立つのかピンとこないコンセプトだけど…。「ノルム」という名前も、初めて聞くと難しそうな感じがするかもしれないが、「絶対値のようなものだけど、値が整数に限られるので扱いやすい」と考えればいいだろう。上記の
  norm(X) と norm(Y) の積は norm(XY) に等しい
という性質は、シンプルだけどすごく役に立つ(次回参照)。

2021-11-01 「ゴルゴ13」分解計画(その4) ユークリッド最強

16. 複素整数 G = 565 + 13i と a = 123 + 45i の最大公約数は何か?

最大公約数を求めるには、互除法(別名: ユークリッドのアルゴリズム)を使うことができる。前回、ガウス整数の範囲でも互除法が成り立つことを(一応)証明したので、その確認も兼ねて、上の例題を考えてみよう。昔のアニメでも「計算しても、経験しなきゃ、ぜんぶ分からない」と言ってた…。前回の計算によると、有理数の範囲では:
  (A + Bi) ÷ (C + Di) = (AC + BD) / N + i(BC − AD) / N
ここで分母の N は C2 + D2 の略で、割る数 C + Di のノルム。分子は、実部が「実実・虚虚の和」、虚部が「内内マイナス外外」つまり、内側の積から外側の積を引いたもの。

実部  虚部   実部  虚部       実実=AC  虚虚=BD
A + Bi   C + Di
外側  内側   内側  外側       内内=BC  外外=AD

(別にこの公式を暗記しなくても、13.の方法で普通に計算すれば同じ結果になる。)

実際に経験してみよう。G ÷ a の場合、こうなる:
  A = 565, B = 13, C = 123, D = 45
  N = C2 + D2 = 1232 + 452 = 17154
  AC + BD = 565 × 123 + 13 × 45 = 70080
  BC − AD = 13 × 123 − 565 × 45 = −23826
だから:
  G ÷ a = (70080 / 17154) − (23826 / 17154)i
これに一番近いガウス整数は何だろう? 実部は、ざっと 70/17 なので 4(なぜなら 17 × 4 = 68)、虚部は一見して −1。つまり、整数商を q1 とすると:
  q1 = 4 − i
余りを b とすると:
  b = G − aq1 = (565 + 13i) − (123 + 45i)(4 − i)
  = (565 + 13i) − (492 − 123i + 180i + 45)
  = (565 + 13i) − (537 + 57i) = 28 − 44i

これは G ÷ a が q1 余り b になること、つまり G = aq1 + b を意味している(検算として aq1 + b を求めてみよう)。重大なポイントとして:
  割る数 a のノルム 1232 + 452 = 17154 よりも
  余り b のノルム 282 + 442 = 2720 の方が小さい!

同様に a ÷ b を計算すると、商 q2 = 2i、余り c = 35 − 11i。余り c のノルム 352 + 112 = 1346 は、さらに小さい。検算として a = bq2 + c を確かめよう。計算苦手でも、電卓でやっちゃえばいいし~

続けて b ÷ c を計算すると、商 q3 = 1 − i、余り d = 4 + 2i。余り d のノルム 42 + 22 = 20 は、ますます小さい。検算は b = cq3 + d。

続けて c ÷ d を計算すると、商 q4 = 6 − 6i、余り e = −1 + i。余り e のノルム 12 + 12 = 2 は、もう後がないくらい小さい。検算は c = dq4 + e。

続けて d ÷ e を計算すると、商 q5 = −1 − 3i で割り切れる(つまり余りのノルム 0)。検算は d = eq5

さすがは信頼のユークリッド。最後の余り e = −1 + i が、G と a の最大公約数。

複素整数 G = 565 + 13i は、虚部が素数だし「これ以上分解できない」ようにも思えるが、実は e = −1 + i という約数を持っている。

17. ホントにそれが約数なのか、実際に G を e で割ってみよう。割る数のノルムは 2、「実実・虚虚の和」は −565 + 13 = −552、「内内マイナス外外」は −13 − 565 = −578 なので:
  G / e = (−552 / 2) + (−578 / 2)i = −276 − 289i
  すなわち G = 565 + 13i = (−1 + i)(−276 − 289i)

複素整数「ゴルゴ13」は、分解されてしまった! 殺し屋のカルマだろうか…

しかし、上記の分解表現、やたらとマイナスだらけで美しくない。せめて第2因子から −1 をくくり出して
  −(−1 + i)(276 + 289i) = (1 − i)(276 + 289i)
と書いてあげるのが、仁義というものだろう。さらに
  1 − i = i4 + i3 = i3(i + 1)
なのだから、次のように書けば、単数以外の全因子からマイナスをなくせる:
  565 + 13i = −i(1 + i)(276 + 289i)

単数倍の違いは本質と無関係だが、本質的な問題として、この分解は素因数分解だろうか? 276 + 289i は、さらに分解できるかもしれないような感じだが…?

この種の疑問にはノルムが有効。α = βγ と分解できる場合(どの因子も単数以外とする)、両辺のノルムを考えると…
  norm(α) = norm(βγ) = norm(β) norm(γ)
…となって、ノルムも分解できる(ここで前回の「積のノルムは、ノルムの積」という性質が威力を発揮)。まず (1 + i) のノルムは 2 なので、(普通の意味では)1 × 2 という「分解」しかできない。けれどノルム 1 に対応するガウス整数は ±1 または ±i に限られ、どれも単数。つまり、ノルム 1 の因数では、本当の分解にならない。従って、ガウス整数 α のノルムが(普通の意味での)素数なら、α 自身もガウス整数として分解不可能。
  n = norm(276 + 289i) = 2762 + 2892 = 159697
についても、(普通の意味での)素数であることを確かめられる。n は 4002 = 160000 より小さいので、ブルートフォースによって、「n は400未満のどの素数でも割り切れない」ということを確かめればいい。

18. 具体例を試すだけでも「ガウス整数の範囲でも互除法が成り立ちそう」という感触が得られるけど、具体例はあくまで具体例。「成り立つ例がある」というだけじゃ「いつでも成り立つ」という証明にはならない。そこで、前々回の「その2」では互除法の一般原理を確認、「その3」ではガウス整数にもその原理が当てはまることを確認した。

普通の整数の世界内では、足し算・引き算・掛け算はいつでもできるが、割り算ができる保証はない。例えば 17 と 2 は整数だが、17 ÷ 2 は整数にならない。

この種のいろいろな世界の中では、互除法が成り立つ世界(正式名称: ユークリッド整域)は最強。互除法が使えるなら、「最大公約数を持つ」「素因数分解ができる」といった望ましい条件は、全て自動的に満たされる(もちろん、そう言い切るためには、証明が必要だが)。そして「互除法が成り立つ」ということの本質は…
  その世界の任意の要素 a、b について(ただし b ≠ 0 とする)、
  「a を b で割ると r 余る」「余り r のサイズは、割る数 b のサイズより小さい」
…もっと正確に言えば:
  任意の a, b に対して、特定の q, r が存在して
  a = bq + r かつ norm(r) < norm(b) が成り立つ。
ここで norm() は、その世界の各要素に 0 以上の整数を対応させる関数で、余りのサイズの目安となる。ガウス整数
  z = x + yi (x, y は普通の整数)
については、
  norm(z) = x2 + y2
…と定義され、z の絶対値の2乗に等しい。z 自身と「z の共役複素数」の積にも等しい。

ユークリッドのアルゴリズムが成り立つ世界とは、「割り算ができる保証はないけど、“余り付きの割り算”なら普通にできる保証がある」という世界。四則演算が全部できる世界に近い。

だったら、最初から「四則演算が全部できる世界」(例: 有理数の世界)を考えた方がいい? まあ、そうかもしれないけど、四則演算が全部できると、例えば素数だったはずの 17 が、0 以外の任意の数で割り切れてしまう(17 ÷ 2 = 8.5 のように)。それじゃ、味気ない!

G = 565 + 13i の分解は、説明のための例で、実は本筋と無関係。本題は、ピタゴラス・トリオ。ガウス整数の方向から、ピタゴラス・トリオを眺めてみたい…。そのためには、ガウス整数の性質をある程度、はっきりさせておく必要がある。

2021-11-02 〔付記〕 159697 の素数判定

G = 565 + 13i をガウス整数の範囲で分解すると:
  G = −i(1 + i)(276 + 289i)

最後の因数 (276 + 289i) は、norm(276 + 289i) = 159697 が素数なので、これ以上分解できない。

159697 が素数であることは、コンピューターを使って試行除算すれば簡単に分かるが、手計算の場合、素数表があるとしても78回の割り算が必要(400以下の素数78個で一つずつ割ってみる)。素数表を作るところから始めると(あるいは、面倒だからと400以下の全部の奇数で割ると)約200回の割り算が必要だろう。

そこで、次のように論じる手もある: m = 159697 は、底 2 と底 3 の Miller–Rabin テストに合格する。100万以下に、そのような擬素数はないので、m は真の素数。

奇数 m に対して、底 b のミラー・ラビンを行うには、まず次のように m − 1 を 2 で割れるだけ割った指数を考える:
  e0 = m − 1 = 159696 これは2で割り切れるので(偶数なので)、2 で割ると…
  e1 = 159696/2 = 79848 これも偶数なので 2 で割ると…
  e2 = 79848/2 = 39924 これも偶数なので 2 で割ると…
  e3 = 39924/2 = 19962 これも偶数なので 2 で割ると…
  e4 = 19962/2 = 9981 偶数でないので、ここで停止

後は b の e4 乗、b の e3 乗、b の e2 乗、b の e1 乗を考えるだけ(e0 乗は考えない)。結果がどこかで ≡ −1 (mod m) になれば合格。もし ≡ 1 (mod m) になった場合、それが最初の指数乗(上の例では e4 乗)の場合に限り合格。…それ以外は、全部不合格。不合格になったら、素数ではない(フェルマーの小定理の応用)。合格したら、素数である確率が高いが、まれに例外もある。

b = 2 の場合:
  A ≡ 29981 ≡ 32867 (mod 159697)  ……… (★)
それを使って:
  B ≡ 219962 ≡ A2 ≡ 32867 × 32867 ≡ 49181 (mod 159697)
  C ≡ 239924 ≡ B2 ≡ 49181 × 49181 ≡ 159696 ≡ −1 (mod 159697) 合格

b = 3 の場合:
  I ≡ 39981 ≡ 49181 (mod 159697)  ……… (★★)
これは上記 B と同じ値なので:
  J ≡ 319962 ≡ 49181 × 49181 ≡ −1 (mod 159697) 合格

問題は、(★)や(★★)の 9981 乗の計算法。真面目に9981回、掛け算すると、とんでもない桁数になってしまう。筆算でそんな数の割り算をするくらいなら、最初の方法で普通に100回くらい割り算した方が楽。…「大きな指数の剰余」について、定石的なアルゴリズムの仕組みは次の通り。(★)の「9981乗」を例とする。

【ステップ1】 2 の「べき」…
  28 = 256, 29 = 512, 210 = 1024, 211 = 2048, 212 = 4096, 213 = 8192
…などを考えると、9981 から引ける最大のべきは 213 = 8192。
  9981 − 8192 = 1789 ここから引ける最大のべきは 210 = 1024
  1789 − 1024 = 765 ここから引ける最大のべきは 29 = 512
  765 − 512 = 253 ここから引ける最大のべきは 27 = 128
  253 − 128 = 125 ここから引ける最大のべきは 26 = 64
  125 − 64 = 61 ここから引ける最大のべきは 25 = 32
  61 − 32 = 29 ここから引ける最大のべきは 24 = 16
  29 − 16 = 13
つまり、こう書ける:
  9981 = 8192 + 1024 + 512 + 128 + 64 + 32 + 16 + 13 (☆)

【ステップ2】 次のように「べき剰余の表」を作ろう:
  216 = 65536 (←直接計算した)
  232 = 216 × 216 = 65536 × 65536 = 4294967296 ≡ 76178 (mod 159697)
  264 = 232 × 232 ≡ 76178 × 76178 = 5803087684 ≡ 18098 (mod 159697)
  同様に 2128 ≡ 180982158754 (mod 159697)
  2256 ≡ 158754290764
  2512 ≡ 907642133951
  21024 ≡ 1339512113966
  22048 ≡ 1139662 ≡ 92146
  24096 ≡ 921462 ≡ 115220
  28192 ≡ 115220236790

【ステップ3】 (☆)から逆にたどって、次のように少しずつ計算していく。
  213 = 8192 (←直接計算した)
  229 = 213 × 216 = 8192 × 65536 = 536870912 ≡ 129295 (mod 159697)
積の第1因子は直前の結果、第2因子は上で作った「べき剰余の表」を参照している。
  261 = 229 × 232 = 129295 × 76178 = 9849434510 ≡ 122035 (mod 159697)
  2125 = 261 × 264 = 122035 × 18098 = 2208589430 ≡ 139617 (mod 159697)
以下同様に:
  2253 = 2125 × 2128 = 139617 × 158754 ≡ 91194
  2765 = 2253 × 2512 = 91194 × 133951 ≡ 144267
  21789 = 2765 × 21024 = 144267 × 113966 ≡ 87984
  29981 = 21789 × 28192 = 87984 × 36790 ≡ 32867

これで(★)が得られた。

底が 3 の場合についても(☆)の分解を再利用して、同様に進めることができる。「400以下の素数をリストアップして、割り算78回」や「400以下の全奇数で割り算」より、少しは楽だろうか? 6桁の掛け算と12桁の割り算が、それぞれ20回程度。少なくとも心理的には、78回の試し割りより、楽かも…

プログラム的な実装において、ステップ1は、指数を2進表記することに当たる。「べき剰余の表」をあらかじめ作って保持するのはメモリーの無駄なので、通常、表を作ることなく、ステップ2とステップ3を同時進行的に実行する。この手法は「繰り返し2乗法」と呼ばれ、素数性の判定に限らず、用途が広い。

6桁の 159697 なら、実際問題、試行除算でも簡単に判定できるけど、これが10桁や20桁の数になると、試行除算は(少なくとも手計算では)大変。一方、ミラー・ラビンを多重に行うことで、約25桁までの数なら、容易に素数性を確定判定できる。これは比較的最近の知見であり、この方法で確定的に判定できる範囲が20桁に到達したのは2014年、25桁に到達したのは2015年らしい。
参考資料 Strong Pseudoprimes to Twelve Prime Bases
https://arxiv.org/abs/1509.00864

⁂

2021-11-03 ガウス整数から見た 3² + 4² = 5² 本当とは思えないほど美しい

19. x2 + y2 = z2 を満たす3個の自然数 (x, y, z) は、「ピタゴラス派の三つ子」(Pythagorean triples)と呼ばれる(愛称: ピタゴラス・トリオ)。
  52 + 122 = 132 (実際 25 + 144 = 169)
  82 + 152 = 172 (実際 64 + 225 = 289)
…このような数の並びには、不思議な魅力がある。
  1202 = 14400
  1192 = (120 − 1)2 = 14400 − 240 + 1 = 14161
  134 = 1692 = (170 − 1)2 = 28900 − 340 + 1 = 28561
  ゆえに 1192 + 1202 = 134 (実際 14161 + 14400 = 28561)

(x, y, z) がピタゴラス・トリオなら (2x, 2y, 2z) や (3x, 3y, 3z) などもピタゴラス・トリオだが、以下では、互いに素な(=2以上の公約数のない)トリオに話を限る。x と y の一方が奇数、他方が偶数(理由は後述)。便宜上、奇数の側を x、偶数の側を2番目の変数 y としよう。例えば、
  82 + 152 = 172 の代わりに
  152 + 82 = 172 と書くことにする。

定理 上記の条件において、どのピタゴラス・トリオも、次の形を持つ:
  (m2 − n2, 2mn, m2 + n2)
  ここで m, n は互いに素な自然数で、一方が偶数、他方が奇数。n は m より小さい。
逆に、この条件を満たすトリオは、ピタゴラス・トリオとなる。

補題1 任意の偶数 2k の平方 4k2 は、4 の倍数。一方、任意の奇数 2k + 1 の平方 4k2 + 4k + 1 = 4(k2 + k) + 1 は「4で割ると1余る数」。

この補題から、もし仮に m, n が両方奇数だとすると、m2 + n2「4で割ると1余る数」と「4で割ると1余る数」の和…つまり「4で割ると2余る数」。けれど、ピタゴラス・トリオの最後の数は平方数 z2 に対応しているのだから、同じ補題によって、z が偶数なら4で割り切れ、z が奇数なら「4で割ると1余る」。どちらのパターンになるにしても、「4で割ると2余る数」は z2 と等しくなり得ない。従って m, n は、両方奇数にはならない。両方偶数にもならない(なったとすると、トリオの3数は全部偶数になってしまい、互いに素という前提に反する)。より一般的に、m, n が2以上の公約数を持つことはない。

ピタゴラス・トリオ (x, y, z) の x と y の偶奇が異なるのも、同様の理由。x2 + y2 は(どちらがどちらかはともかく)偶数2乗と奇数2乗の和、つまり偶数と奇数の和、それは奇数。従って、z は…「どちらのパターンになるにしても」とは言ったものの…実は奇数。

定理の (m2 − n2, 2mn, m2 + n2) がピタゴラス・トリオであること:
  (m2 − n2)2 + (2mn)2 = (m2 + n2)2
…この関係については機械的計算で確認できるけど、この天下り的な式は、一体どこからやって来たのか。どうしてこういう形になるのか。この型以外のピタゴラス・トリオは存在しないのか?

ガウス整数の立場から考えてみたい。

20. x2 + y2 = z2 をガウス整数の範囲で分解して
  (x + yi)(x − yi) = z2
と書いてみる。α = x + yi, β = x − yi と置くと:
  αβ = z2

今 α と β の最大公約数を G とすると、α も β も G の倍数だから:
  α + β = 2x も G の倍数、
  α − β = 2yi も G の倍数。
つまり 2x と 2yi は、どちらも G で割り切れる。仮定により x と y は互いに素。「普通の意味で互いに素な2整数は、ガウス整数の範囲でも互いに素」という主張をひとまず受け入れるなら、上記のことは「G は 2 の約数」という意味を持つ。ガウス整数の範囲では、2 は
  12 + 12 = 1 − i2 = (1 + i)(1 − i)
と分解されるので、もし G が単数以外の 2 の約数なら、G は 1 + i または 1 − i という因数言い換えれば、約数)を含む。実際には、α も β もこのような因数を持ち得ないので(※)、当然、α と β の公約数 G も、このような因数を持たない。つまり G は、2 の約数といっても単数であり、G = 1 or −1 or i or −i。要するに α と β は、ガウス整数として互いに素

(※) 簡単に言えば、x と y は偶奇が異なるのだから α = x + yi は、例えば 3 + 4i や 10 + 7i のような数であり、1 ± i の倍数になることは無理っぽい(β についても同様)。…もう少しきちんと言うと、1 ± i はノルム2だから、1 ± i の倍数は、ノルムの値が2の倍数。ところが α のノルムも β のノルムも、x2 + y2 であり、x と y は偶奇が異なるのだから、x2 + y2 は奇数――つまり α のノルムも β のノルムも、2の倍数ではない。

一方、積 αβ は、z2 に等しいのだから平方数。従って、α と β は、それぞれ単体でも平方数(またはその単数倍)。どういうことか。例えば、z がガウス整数の範囲で、次のように 4 個の相異なる素因数を持つとしよう:
  z = PQRS
その場合、
  αβ = z2 = P2 Q2 R2 S2
について、
  α = P2Q2 = (PQ)2, β = R2S2 = (RS)2  (α と β はそれぞれ平方数)
のようなことは、あるかもしれないけど、
  α = PQ2, β = PR2 S2  (α と β は平方数でも平方数の単数倍でもない)
のように「ある一つの平方因子 P2 を α と β で分け合うこと」は、あり得ない(あり得たとすると、α と β は両方 P の倍数となり、互いに素という事実に反する)。

x と y がピタゴラス・トリオの最初の2数だとすると、x + yi はガウス整数として平方数の単数倍。つまり、何らかのガウス整数 A + Bi と単数 ε = ±1 or ±i が存在して、
  x + yi = α = ε(A + Bi)2 = ε[(A2 − B2) + 2ABi]  ……… (♪)
と書ける。

(♪)の右辺の A, B が両方偶数なら(あるいは両方奇数なら)、右辺は 2 の倍数になり、右辺に等しい α も 2 の倍数になってしまうが、それは不可能。なぜなら、既に見たように α は 1 + i の倍数ではなく、1 − i の倍数でもないので、ましてや (1 + i)(1 − i) = 2 の倍数ではない。…だから A と B は偶奇が異なる。

代わりに、次のように考えてもいい。α の共役複素数 β = x − yi は、(♪)の虚部の符号を逆にしたもの:
  もし ε = ±1 なら β = ε[(A2 − B2) − 2ABi]
  もし ε = ±i なら β = ε[−(A2 − B2) + 2ABi]
…となるが、いずれにしても A と B は偶奇が異なる。なぜなら、もし偶奇が一致すると、α と β はどちらも 2 で割り切れることになるが、それは「α, β が互いに素」という事実に反する。

ここでは x が正の奇数、y が正の偶数と仮定しているのだから、(♪)において、
  ε = 1, x = A2 − B2, y = 2AB
  または ε = −1, x = B2 − A2, y = −2AB
が題意に適する。ε = 1 なら m = |A|, n = |B| と置き、ε = −1 なら m = |B|, n = |A| と置けば、19. の定理の形になる。

<例1> 32 + 42 = 52 つまり x = 3, y = 4 のとき:
  α = 3 + 4i = (2 + i)2 従って ε = 1, A = 2, B = 1

<例2> 52 + 122 = 132 つまり x = 5, y = 12 のとき:
  α = 5 + 12i = (3 + 2i)2 従って ε = 1, A = 3, B = 2

<例3> 72 + 242 = 252 つまり x = 7, y = 24 のとき:
  α = 7 + 24i = −(1 + 2i)4 = −(−3 + 4i)2 従って ε = −1, A = −3, B = 4

21. 例3では、上の書き方では ε = −1 だが、次のように ε = 1 の形に書き換えることもできる:
  α = (−1)(−3 + 4i)2 = i2(−3 + 4i)2 = [i(−3 + 4i)]2
  = (−3i + 4i2)2 = (−4 − 3i)2 = (4 + 3i)2 なぜなら X2 と (−X)2 は等しい
  従って ε = 1, A = 4, B = 3

<例4> 332 + 562 = 652 つまり x = 33, y = 56 のとき:
  α = 33 + 56i = −(1 + 2i)2(2 + 3i)2 = −(−4 + 7i)2 従って ε = −1, A = −4, B = 7
  書き換えると α = 33 + 56i = (−7 − 4i)2 = (7 + 4i)2 従って ε = 1, A = 7, B = 4

このようにして ε = 1 に統一した場合、状況を要約すると…

ガウス整数の範囲では x2 + y2 = (x + yi)(x − yi) だが、ピタゴラス・トリオ (x, y, z) の場合、このように分解した因子の x + yi が再び平方数 (A + Bi)2 になる

これは著しい事実である(高木先生風の表現w)。

通常の整数の世界では、x2 + y2 は「平方数の和」。ガウス整数として解釈すると、それは
  (x + yi)(x − yi)
という2因子の「積」であり、しかも2因子は互いに素なので、どちらの因子も、右辺の z2 の性質――すなわち「平方数」という属性――を受け継ぐ。

もう一方の因子 x − yi については?

補題2 X, Y を任意のガウス整数とし、それらの共役複素数(虚部の符号を反転させた数: それらもガウス整数である)をそれぞれ conj(X), conj(Y) とすると:
  conj(XY) = conj(X) conj(Y)  つまり積の共役は、共役同士の積

〔証明〕 X = a + bi, Y = c + di とする。XY = (ac − bd) + (bc + ad)i なので:
  conj(XY) = (ac − bd) − (bc + ad)i   ← 虚部の符号を反転させた
これは、次の値と等しい:
  conj(X) conj(Y) = (a − bi)(c − di) = (ac − bd) + (−ad − bc)i □

この補題から、x + yi = (A + Bi)2 のとき、両辺の共役を考えれば x − yi = (A − Bi)2 となる。

というのも、X = Y = A + Bi とすると XY = (A + Bi)2 = x + yi。このとき conj(X) = conj(Y) = A − Bi で、conj(XY) = x − yi。これを補題2に当てはめた。

つまり
  x2 + y2 = z2
という2乗の足し算は、
  (x + yi)(x − yi) = (A + Bi)2(A − Bi)2 = [(A + Bi)(A − Bi)]2 = (A2 + B2)2
という2乗の掛け算と等価。例えば:
  32 + 42 = 52 ⇒ (3 + 4i)(3 − 4i) = (2 + i)2(2 − i)2 = (22 + 12)2
  52 + 122 = 132 ⇒ (5 + 12i)(5 − 12i) = (3 + 2i)2(3 − 2i)2 = (32 + 22)2

本当とは思えないほど、美しい!

注 この表現は「x が奇数、y が偶数」という便宜上の取り決めに依存している。「x が偶数、y が奇数」だとしても、変数名・足し算の順序が入れ替わるだけだが、その場合、上記 ε が ±i になってしまい、ダイレクトに「2乗の掛け算」の形にできないため、少し見通しが悪くなる。

19. の定理は天下り的で、直観的な意味が不明だったが、ガウス整数の立場から眺めると透明で、必然的。

Die gaußschen Zahlen;
Zu schön, um wahr zu sein. (ガウス整数、鳥肌もんだぜっ)

でも、証明の技術的細部がまだ甘い。ガウス整数の最大公約数は互除法から分かるとして(「ゴルゴ13」分解計画)、ガウス整数の素因数分解については、できるかどうかも未確認。19. の定理を使って小さい範囲のピタゴラス・トリオの一覧表を作り、それぞれの例について A + Bi の具体的構造を調べてみないと、上記の考察についても実感が湧いてこない。冒険は続く…

2021-11-06 ガウス整数から見た 3² + 4² = 5² (その2)

22. 互いに素な(=2以上の公約数を持たない)自然数 x, y について。ガウス整数の範囲では
  x2 + y2 = (x + yi)(x − yi)  ……… ①
と分解できる。もし第3の自然数 z があって
  x2 + y2 = z2  ……… ②
が成り立つなら、①右辺の因子 x + yi と x − yi 自身も、それぞれガウス整数の範囲では平方数となり、
  x + yi = (A + Bi)2  ……… ③
  x − yi = (A − Bi)2  ……… ④
と書ける。A, B は、普通の意味での整数(以上が前回の粗筋)。

③の右辺を展開・整理すると:
  x + yi = (A2 − B2) + 2ABi
この等式の実部・虚部を比較すると:
  x = A2 − B2  ……… ⑤
  y = 2AB  ……… ⑥

⑥から、y は2の倍数、つまり偶数。x と y は互いに素なので、x は奇数。ところで、⑤では A も B もどうせ2乗されてしまうので、A, B の符号はどうでもいい。一方、y は自然数(正の整数)なのだから、⑥によれば、A と B は両方プラスか、または両方マイナスでなければならない。わざわざマイナスを使う必要はないので、両方マイナスの場合には、符号を逆にした正の数をあらためて A, B としよう(その場合、③④右辺の丸かっこ内の符号も逆転するが、丸かっこ内はどうせ2乗されるのだから、問題なし)。

要するに、A と B は自然数で、A の方がでかい。そして A と B は互いに素(なぜなら、A と B が2以上の公約数 g を持つと、⑤⑥から x, y はどちらも g の倍数になってしまう。これは x と y が互いに素、という前提に反する)。従って A, B が両方偶数ということはないが、実は A, B が両方奇数ということもない(両方奇数だと、⑤は、x イコール「奇数の2乗、引く、奇数の2乗」イコール「奇数、引く、奇数」イコール「偶数」になってしまい、x が奇数という前提に反する)。

②を z2 = x2 + y2 と書いて、その右辺に⑤⑥を代入すると:
  z2 = (A2 − B2)2 + (2AB)2 = (A2 + B2)2
  z = A2 + B2  ……… ⑦
  前半の変形は、いつでも成り立つ等式
   (s + t)2 = s2 + 2st + t2
   (s − t)2 = s2 − 2st + t2
   (s + t)2 = (s − t)2 + 4st
  の3番目に、s = A2, t = B2 を当てはめたもの。

23. 以上の情報によって、ピタゴラス・トリオを体系的に構成できる。

まず A = 1 の場合。B は A より小さい自然数なので、条件を満たすものがない。強いて言えば B = 0 だが、そのとき⑤⑥⑦から x = A2 − B2 = 1, y = 2AB = 0, z = A2 + B2 = 1 となり、確かに
  12 + 02 = 12
が成立。けれど、これは当たり前過ぎて面白くない。やはりゼロは反則としましょう!

A = 2 の場合。B は A より小さい自然数なので、B = 1 しか可能性がない。この A, B は「互いに素で偶奇が異なる」という条件を満たすので、ちゃんとしたピタゴラス・トリオを生成する。⑤⑥⑦から:
  x = 22 − 12 = 3
  y = 2 × 2 × 1 = 4
  z = 22 + 12 = 5
  検証 32 + 42 = 52 ← 正しい(9 + 16 = 25

次に A = 3 の場合。このとき B は偶数なので B = 2 に限られる。
  x = 32 − 22 = 5
  y = 2 × 3 × 2 = 12
  z = 32 + 22 = 13
  検証 52 + 122 = 132 ← 正しい(25 + 144 = 169

今度は A = 4。このとき B は奇数なので B = 1 または B = 3。可能性が2個になった。まず B = 1 から。
  x = 42 − 12 = 15
  y = 2 × 4 × 1 = 8
  z = 42 + 12 = 17
  検証 152 + 82 = 172 ← 正しい(225 + 64 = 289

<暗算の仕方> 152 = (10 + 5)2 = 100 + 2⋅10⋅5 + 25 = 100 + 100 + 25
172 = (10 + 7)2 = 100 + 2⋅10⋅7 + 49 = 100 + 140 + 49

A = 4, B = 3 なら:
  x = 42 − 32 = 7
  y = 2 × 4 × 3 = 24
  z = 42 + 32 = 25
  検証 72 + 242 = 252 ← 正しい(49 + 576 = 625

<暗算の仕方> 242 = (20 + 4)2 = 400 + 2⋅20⋅4 + 16 = 400 + 160 + 16
252 = (20 + 5)2 = 400 + 2⋅20⋅5 + 25 = 400 + 200 + 25

一見「ピタゴラス・トリオは完全に制圧された」という感じがする。実際、この調子で A = 5 のとき B = 2 or 4、A = 6 のとき B = 1 or 5、A = 7 のとき B = 2 or 4 or 6 などと、ピタゴラス・トリオを順々に漏れなく生成できる(A = 6, B = 3 は互いに素でないので除外した)。

けど、本当に問題が解決したと言えるだろうか。これで心から納得がいくだろうか?

⁂

得られた公式は本物だけど、その導出にはギャップがある。今のところ「ガウス整数の範囲でも一意的な素因数分解ができるとすれば…」という「仮定の話」にすぎない。頂上からの景色は確かにきれいだが、本当にこの道は通行可能なのか?

面倒かもしれないけど、その道を一歩一歩、自分で歩いてみてこそ、全てのもやもやが解消され、すっきりした気分と達成感を味わえるだろう…。

⁂

(付録) 12以下の範囲の A, B から作られる31種のピタゴラス・トリオ

\\ pari
joken_o_mitasu(A,B) = { A%2 != B%2 && gcd(A,B) == 1; }
kekka_o_kaku(A,B) = { my( x=A^2-B^2, y=2*A*B, z=A^2+B^2 );
    printf( "[ %2d ] A=%2d, B=%2d ::: (%d,%d,%d)\n",
             c++, A, B, x, y, z );
}
c=0; \\ counter
for( A=1, 12, for( B=1, A-1, joken_o_mitasu(A,B) && kekka_o_kaku(A,B) ) );

出力

[  1 ] A= 2, B= 1 ::: (3,4,5)
[  2 ] A= 3, B= 2 ::: (5,12,13)
[  3 ] A= 4, B= 1 ::: (15,8,17)
[  4 ] A= 4, B= 3 ::: (7,24,25)
[  5 ] A= 5, B= 2 ::: (21,20,29)
[  6 ] A= 5, B= 4 ::: (9,40,41)
[  7 ] A= 6, B= 1 ::: (35,12,37)
[  8 ] A= 6, B= 5 ::: (11,60,61)
[  9 ] A= 7, B= 2 ::: (45,28,53)
[ 10 ] A= 7, B= 4 ::: (33,56,65)
[ 11 ] A= 7, B= 6 ::: (13,84,85)
[ 12 ] A= 8, B= 1 ::: (63,16,65)
[ 13 ] A= 8, B= 3 ::: (55,48,73)
[ 14 ] A= 8, B= 5 ::: (39,80,89)
[ 15 ] A= 8, B= 7 ::: (15,112,113)
[ 16 ] A= 9, B= 2 ::: (77,36,85)
[ 17 ] A= 9, B= 4 ::: (65,72,97)
[ 18 ] A= 9, B= 8 ::: (17,144,145)
[ 19 ] A=10, B= 1 ::: (99,20,101)
[ 20 ] A=10, B= 3 ::: (91,60,109)
[ 21 ] A=10, B= 7 ::: (51,140,149)
[ 22 ] A=10, B= 9 ::: (19,180,181)
[ 23 ] A=11, B= 2 ::: (117,44,125)
[ 24 ] A=11, B= 4 ::: (105,88,137)
[ 25 ] A=11, B= 6 ::: (85,132,157)
[ 26 ] A=11, B= 8 ::: (57,176,185)
[ 27 ] A=11, B=10 ::: (21,220,221)
[ 28 ] A=12, B= 1 ::: (143,24,145)
[ 29 ] A=12, B= 5 ::: (119,120,169)
[ 30 ] A=12, B= 7 ::: (95,168,193)
[ 31 ] A=12, B=11 ::: (23,264,265)

2021-11-07 大長編ドラえもん のび太のパラレルワールド大冒険

のび太は、割り算があまり得意ではなかった。足し算・引き算・掛け算は普通に分かるのだが…

割り算の宿題をやりたくないのび太は、もしもボックスを使って「もしも割り算がなかったら」というパラレルワールドを作る。

その結果、数学が離散的になる。「割り算」「分数」「小数」などが消滅、代わりに生徒は「Q算」と「R算」を学ばなければならない。

聞いたこともない演算に、のび太びっくり。「のび太さんたら、Q算とR算も知らないの?」パラレルワールドのしずちゃんも、びっくり。その説明によると、例えば
  17 Q 5 = 3
とは、17から5を何回まで引けるか?という計算だいう。
  17 − 5 = 12  (1回引ける)
  17 − 5 − 5 = 7  (2回引ける)
  17 − 5 − 5 − 5 = 2  (3回引ける…残った2から、5はもう引けないので答えは3)

「な~んだ、それだけのことか!」引き算は得意だったので、のび太は一安心。「早い話が、割り算の小数点以下を計算しないで、切り捨てていいのか。途中で計算やめていいだなんて、楽でいいね」「えっ、のび太さん、“割り算”って何のこと?」「いや、こっちの話。それより、R算っていうのは、何だったっけ?」…Q算で「これ以上引けなくなったとき」に残ってしまう小さな数を求める計算だという。上の例で言えば…
  17 R 5 = 2

「17割る5は3余り2ってだけじゃないか。気に入った! この世界の計算は、すごく分かりやすいぞ」

「なるほど、そういうことか」ドラえもんの説明的なせりふ。「ぼくたちの世界の A÷B は、BC = A を満たす C を見つけることだけど…。この世界では、代わりに、与えられた A と B に対して
  A = BQ + R, R < B
を満たす Q と R を見つける計算をやってるんだ!」

試しにQ算、R算の練習問題をやってみるが、とても簡単。全問正解して、クラスメートに尊敬されるのび太。

だが、離散的な世界は、のび太の予想より、はるかに奥が深いものだった。このパラレルワールドでは、小数や分数の勉強をしないでいいので、その分、指数計算やマイナスの数がどんどん導入され、それどころか「2乗するとマイナスになる数」まで小学校で学ばなければならない。さすがパラレルワールド。自然数の世界では飽き足らず、いろいろな整域が登場。入り口は剰余類かもしれないし、ガウス整数かもしれないが、誰もが当たり前のように小学校でそれを習うため、それは初歩的なこと…という認識になっている。

だから「約数」「公約数」「最大公約数」「因数分解」のような、普通の世界では簡単な概念が、非常に繊細で微妙なものになる。

割り算(この世界では誰も知らないコンセプト)をチートのように使って、にわかに超優等生になったのび太。苦手意識が克服され、得意意識が芽生えたため、いい気分になって、上記のような冒険も次々とクリアしていく。一方、パラレルワールドでは、数学の進歩にひどく偏りがあるらしく、人々は「一意分解性の破れ」をどう扱っていいのか分からず、困っていた。学校の先生も「それはまだ解明されていない、数学のなぞなのだ」とか言い出す始末。

のび太は、パラレルワールドの困っている人々を助け、数学の救世主となれるのかっ?

⁂

2021-11-08 数学が分かるコツ? 攻略作戦会議

32 + 42 = 52 とか 52 + 122 = 132 のようなピタゴラス・トリオ(ピタゴラスの定理…別名「3平方の定理」…において、平方される数が整数になる場合)は、何だか分からないけど素敵な感じがします。

ピタゴラス・トリオの特徴付け(トリオを作る公式とか)は、小学校的な方法でも簡単にできますし、単位円と二次方程式を使う方法もありますが、ガウス整数を使うアプローチは「本当とは思えないほど美しい」。しかも隠された核心・本質を突き、「より広い世界への入り口」の招待状ともなっているようです…。

その美しさを垣間見ることは、難しくありません。ユークリッドのアルゴリズム…別名「互除法」(ごじょほう)…さえ導入すれば、ほぼ全ては説明可能。

けれど、数学としてきちんと成立させるためには、どうしても避けて通れない微妙な問題が一つ残ります…。それは「ガウス整数の世界でも、普通に素因数分解ができる」という前提。より一般的に「ユークリッドのアルゴリズムが使える世界では、普通に素因数分解ができる」ことの証明。

この命題は、難しいというより微妙。ややこしい積分や三角関数のような意味での「ガリガリ計算する大変さ」はないけど、数論特有の、繊細な概念構成が必要…。群論・環論の経験がある方なら、あの「眠くなる感じ」をご存じでしょう。集合論から始まって「エレガント」に最短距離を進む公理論的アプローチ…。それが現代の代数なのだから仕方ない、という見方もあるでしょうけど。

Pete L. Clark は、こう書いてます(Number Theory: A Contemporary Introduction)。

Modern presentations of mathematics – including, alas, these notes, to a large extent – often hide this experimentation and discovery process.

実験と発見のプロセス…。教科書は「エレガント」でも、それは「数学史的には、泥沼で試行錯誤を重ねた結果」。泥沼の体験を隠しつつ、ようやく分かった結論だけを涼しい顔でプレゼンしてる!

そういう意味で、教科書というのは「いんちき」。エレガントさに惑わされてはいけない。「数学が得意な人って、頭がいいなぁ~」「自分には無理」とだまされず、自分も泥遊びをすることが鍵。眺めてないで、とりあえず何かやってみる。強引な全数検索でも何でもいいから、具体例を作って、実際に体験してみる。実験してみる。多少論理がおかしくても一通り試してみる。

「この部分が理解できない」というギャップが残っても構わない。「大体分かったが、ここのロジックが分からない。やっぱり自分には無理」と悲観せず、「よし、どこが分からないか認識できたぞ。あとはこのギャップを埋めるだけだ」と、りりしく考える。焦らない。今日は分からなくても、そのうち分かる日が来るさ…。

Frederick M. Goodman は、こう書いてます(Algebra: Abstract and Concrete)。

You must have patience, or learn patience, and you must have time. You can’t learn these things without getting frustrated, and you can’t learn them in a hurry. If you can get someone else to explain how to do the problems, you will learn something, but not patience, and not persistence, and not vision. So rely on yourself as far as possible.

⁂

「ユークリッド整域はUFD(一意分解整域)」を示す標準的論法は、「ユークリッド整域はPID、PIDはUFD」。けれど、ガウス整数だけのためにイデアルを使うのは、大げさ過ぎる。直接「ユークリッド整域はUFD」を示したい(イデアルは後で必要に迫られた時点で、導入すればいい)。この戦略を実現するためには、3段階が必要っぽい…

  1. まずは「分解不可能」(既約)と「素数」の違いをはっきりさせ、素数は分解不可能(当たり前だが)ということを示す。論理的には易しいけど、この微妙な区別を行うモチベーションがないと「眠くなる」。ワンパターンの Z[√(−5)] の例は、ちょっと天下り的だし、どうしましょ?
  2. 「ユークリッド整域では、素数と分解不可能は同じ意味」ということを確立させる。「区別しといて結局同じ意味かよ。訳の分からんお役所仕事みたいだな」…と思わせないためには、遠回りでも「一意分解でない整域」を先に出すのが必然か…。このステップを省ければ話が早いが、互除法は準備してあるから、この命題自体はあと一歩…。やるっきゃない!
  3. 本題の「ユークリッド整域はUFD」だが、PIDのレイヤーを間に挟むのを回避するため、イデアルを集合としてベタに書き、イデアルの概念を使わずに「どうにかする」。どうやって? 「ユークリッド整域⇒PID⇒UFD」なんだから、「ユークリッド整域⇒UFD」は論理的に保証されている。論理的に保証されてるんだから、やれば何とかなるでしょ?

一方、教科書的な方法は、ほとんどあらゆる講義ノートに記されているでしょうが、適当に検索してたまたまヒットした中では、次が明快でいい感じかも。
James McKernan「数学18.703」(MIT 2013年春)
https://math.mit.edu/~mckernan/Teaching/12-13/Spring/18.703/lectures.html
Lecture 16 から Lecture 20

どうせ可換環とかイデアルとか使うんだから、教科書通りに早めに導入したっていいじゃん…という立場もあるけど、まぁ、遊び…。遊びなんだから、自分にとって一番気持ちいのいい道を気ままに歩きたい。泥んこの野原で体験してみてこそ「これを整理して、蒸留すると、教科書の記述になる」と納得がいくでしょうし、「教科書の記述はあくまでフォーマルなプレゼン。具体的には、こういうことなんだ」みたいな実感もつかめるでしょう。

「初等的な問題のはずなのに、イメージがつかめない」という場合、大抵、教科書(との相性)が悪い。「自分なら、もっと分かりやすく説明・証明できる」と考え(少なくとも、自分自身にとって分かりやすいという意味で)、それを実行してみる。かなりの高確率で「ほらね、教科書の側にギャップがあった。誤植があった。説明が不明瞭だった」となるのでは…。でも、そこで高ぶらず「教科書が分かりにくいおかげで、勉強になった。きっとこの著者は読者を信じて、わざとギャップを残し、行間を広くしたのだろう。ありがとう」とほほ笑みましょう…。笑う門には福来る。

とはいえ、数学者って、本質的にものぐさ(特に、事柄の説明に関しては)。証明を「明らか」の一言で終わらせたり、「読者の練習問題とする」を乱発したりするのは、正直、やめてほしいよねw

「PはQである。実際…」みたいな堅苦しい教科書調も改め、フレンドリーに「PはQだよ。だってさぁ…」とか書いたらいいのに(笑)

2021-11-13 バシェ/ベズの定理

24. 次の定理は、一見無味乾燥に思えるが、実はめちゃくちゃ役立つ。例えば、mod p での逆数計算に使えるし、「素数とは何か?」という本質を考えるとき、重要な鍵となる。

定理(Bachet–Bézout) 任意の2整数 a, b について、それらの最大公約数を g とするとき、
  ax + by = g
は、整数解 x, y を持つ。

<例> a = 123 と b = 45 の最大公約数は 3 なので、123x + 45y = 3 は解を持つ。…ユークリッドの方法(互除法=ごじょほう)で最大公約数を求めると、副産物として、この事実は自然に分かる:
  ① 123 を 45 で割ると 33 余る
  ② 45 を 33 で割ると 12 余る
  ③ 3312 で割ると 9 余る
  ④ 129 で割ると 3 余る
  93 で割ると、割り切れる
  最後の余り 3 が、最大公約数。

①は 123 = 45q + 33 という意味だが(q は 123 を 45 で割った整数商、具体的には 2)、ちょっと変形すると
  ①′ 33 = 123 − 45q = 123 × 1 + 45 × (−2)
つまり「a = 123 と b = 45 を使って、余り 33 を aX + bY の形で書ける」。

同様に ② から:
  45 = 33 × 1 + 12
  12 = 45 − 33 × 1 = 45 + 33 × (−1)
これは「余り 12 を b + 33 × 整数 の形で書ける」という意味だが、①′ から、33 は aX + bY の形で書けるので、次のように 12 も同じ形で書ける:
  ②′ 12 = 45 + [123 × 1 + 45 × (−2)] × (−1) = 123 × (−1) + 45 × 3

さらに ③ から、余り 9 も 123X + 45Y の形で書ける:
  33 = 12 × 2 + 9
  9 = 33 − 12 × 2  ここで①′ と ②′ を使うと:
  ③′ 9 = [123 × 1 + 45 × (−2)] − [123 × (−1) + 45 × 3] × 2 = 123 × 3 + 45 × (−8)

全く同様にして、④ の余り 3 も、123X + 45Y の形で書ける:
  12 = 9 × 1 + 3
  3 = 12 − 9 × 1  ここで②′ と ③′ を使うと:
  3 = [123 × (−1) + 45 × 3] − [123 × 3 + 45 × (−8)] × 1 = 123 × (−4) + 45 × 11

つまり 123x + 45y = 3 の一つの解は x = −4, y = 11。

25. 上記は単なる一つの具体例だが、同様の手順で、ax + by = g の解 x, y は、いつでも単純計算で求まる(順々に機械的に、上の式を下の式に代入しているだけ)。のみならず、互除法が使える限り、全く同様の議論が成り立つので、この定理は、整数の世界に限らず、任意の「互除法が使える世界」(正式名称: ユークリッド整域)に拡張される

ただし a または b が 0 の場合、個別的な注意が必要になりそうなので、面倒を避けるため、今は「どちらも 0 でない」としておく。

特に、任意のユークリッド整域 W の任意の2元 a, b について、もしそれらが互いに素なら…言い換えれば g = gcd(a, b) = 1 ならば…上の定理は、こうなる:
  「ax + by = 1 を満たす x, y ∈ W が存在する」

17世紀フランスの数学者バシェ、18世紀フランスの数学者ベズ。上記の定理を導いた彼ら自身、そこに秘められた深い意味に、気付く由もなかった。折しもベズがその著書を出版したのは、ガウスが1歳の誕生日を迎えた頃。この赤ん坊がやがて青年となり、数論の世界に革命を巻き起こす…。

⁂

2021-11-14 「余白が狭過ぎる」事件 犯人バシェ Bachet

画像1(390 KiB)「フェルマーの最終定理」は超有名。フェルマーは、ディオファントス(3世紀ギリシャの数学者)の著作を熟読、余白にあれこれ書き込みをしたという。

画像は、その「余白が狭過ぎる」本。1621年の初版(フェルマーが持っていたのと同じ?)のスキャンをフランスのサイトで見つけた。
https://gallica.bnf.fr/ark:/12148/bpt6k57276g.pdf

フェルマーが愛読したのは、古代の写本などではなく、ラテン語対訳の新しい出版物だった。翻訳したのは、フランスの数学者C. G. バシェ(Claude-Gaspard Bachet)。「バシェ/ベズの定理」のバシェに他ならない(この定理の名前はあまり知られていないが、定理の内容はよく知られている)。バシェが素数の本質に触れる研究をしたのも、偶然ではなさそうだ。

それにしても「1000年以上前の教科書から、一生懸命、数学の知識を得る」という当時の状況は、想像を絶する。「魔女」を火あぶりにしたり、天文学者を自宅監禁していたヨーロッパのキリスト教会は、学問の面では極めて罪深い。いまだに地球史や進化論に抵抗する人々もいるし、大企業や政府による監視・検閲を正当化する動きもあるけれど、学問の自由を不当に制限すると、いろいろなことが停滞してしまう。

さて、フェルマーが「余白が狭過ぎる」と書き込んだという問題のページ(画像2)。意外と余白は狭くない

↓ていうか、これ以上、余白があったら、余白が広過ぎではw

画像2(280 KiB)けど、フェルマーがメモしたかったのは、このくらいのスペースでは書き込めないような、複雑な内容だったのだろう。「そういうときには本の余白でなく、自分のメモ用紙に書けばいい」という常識がないのが、天才数学者の天才たるゆえんかw

フェルマーのアイデアは、直接には実を結ばなかった。しかし「最高に素晴らしい証明法を思い付いたが、それを書くにはこの余白は狭過ぎる」という謎めいたその走り書きは、フェルマーの最終定理と呼ばれ、何世紀にもわたって、数学の発展に多大な影響を及ぼした。

ピタゴラス・トリオで遊んじゃえっ」シリーズでは、一番簡単な「最終定理の n=4 の場合」をフェルマー風に証明している。同じ内容を「ガウス整数の問題として証明する方法」もあって、今ではそっちの方が有名かも…。

バシェが翻訳したこの本では、非平方数を平方数の和で表すことも説明されている。フェルマーのクリスマス定理(4k+1型の素数は、2平方数の和で表される)の出発点かもしれない。

晩年のバシェ(1635年) [JPG画像] ←「余白が狭過ぎる」本の著者w
パブリック・ドメインの資料
 https://commons.wikimedia.org/wiki/Category:Claude_Gaspar_Bachet_de_M%C3%A9ziriac
参考文献 https://fr.wikipedia.org/wiki/Claude-Gaspard_Bachet_de_M%C3%A9ziriac

2021-11-15 天国でけんか中の数学者たち シリア学者の憂鬱

フェルマー「ワイルズ君、よくやった!」
オイラー&ガウス&その他大勢「よく言うよ…」
フェルマー「む、そ、そのぉ…。あ、あんたの本の余白が狭過ぎるから、数学史が混乱したんだからねっ」
バシェ「だから余白じゃなくて、ちゃんと自分のノートに書けばいいし…」
ディオファントス「どうでもいいが、貴君らは1000年以上前の我が輩の著書で数学の勉強かね。1000年間、数学の進歩が止まっているとは情けないではないか」
マーダバ「まさに。中世ヨーロッパは、少なからずお粗末と言わねばなるまい」
アブール・ワファー「まあヨーロッパは、イスラム世界から必死に三角関数を学んだわけだがね…」
アル・クワーリズミー「そもそもアルゴリズムという言葉自体、私の名前が語源なわけだが…」
バル・エブラヤ「まあ、そのイスラム世界は、われわれシリア世界から学んだわけだが…」
ケーララ学派&ペルシャ「あんた誰?」
バル・エブラヤ「シリアのダビンチ、このバル・エブラヤを知らぬとは不勉強な連中だ。よし、ウィキペディアの記事にリンクを張ってやる。おれさまの偉大さを…あれ? ウィキペディア日本語版におれの記事がないぞ」
インド&イスラム「ハッハッハッ、あんたは特筆に値しない存在ってことだな」
バル・エブラヤ「ちょ、ちょっと待て。そんわけない。シリア語じゃなくて英語風表記かな。『バル・ヘブラエウス』検索…。あれ、やっぱりおれの記事がない? まじ?」
インド&イスラム「あんたは、どうでもいい端役!」
バル・エブラヤ「そんなばかな…古典ギリシャとイスラム黄金期の架け橋となったのはシリアなのに…。これがホントの『笑える話』か…」

フォボナッチ「このわたくしの存在も、お忘れなく! フィボナッチ、ニーサンゴーハチ、フォボナッチに清き一票を!」
インド&イスラム&シリア「足し算してるだけのあんたは、さらにどーでもいーだろ!」

フェルマー「まあまあ、けんかはやめよう。われわれは同じ趣味の同志ではないか。ページの余白の落書きはさておき、小定理はいいでしょ?」
ユークリッド「ときに、先生方の一番お好きな数は何ですか」
ガウス「最も美しい数、それはやはり17であろう」
マーダバ「インドとしては1729を推さねばなるまい」
メルセンヌ「149だな、うん。M149の分解は、心が躍る!」
フィボナッチ「やはり数の基本は (1+√5)/2 でしょう!」
アイゼンシュタイン「それを言うなら (−1+√−3)/2 だ!」
ユークリッド「皆さん 4k+1 派のようですね」
フェルマー「本当だ…」
オイラー「不思議なようだが、本当なのだ…」

⁂

2021-11-17 直観的に分かる「第一補充法則」 かえって疑問が増えるけどw

26. 数学自体が難しいというより、なぜこんなことをやるの?というパースペクティブが捉えにくいかも…。教科書的に硬く考えず、適当に散歩してみたい。4で割って1余る素数は、バニラの香りがする。

フェルマーの小定理の重大性は、明らかだろう。身近な例として、私たちが安全にメールをやり取りするためのPGP(正確に言えばRSA暗号)だって、鍵を作るとき、フェルマーの小定理の考え方を使ってる。

フェルマーの小定理(簡易版) 3 以上の任意の素数 p が与えられたとき、2 の p−1 乗は、p の倍数より 1 大きい。

<例1> 素数 7 が与えられた。27−1 = 26 = 64 は、7 の倍数より 1 大きい。実際 63 = 7 × 9 は 7 の倍数だから、64 = 7の倍数 + 1。

フェルマーの小定理(続き) 2 という数を p と互いに素な任意の自然数に置き換えても、同じことが成り立つ。

<例2> 例1の 2 を 3 に置き換える。37−1 = 36 = 729 も、7 の倍数より 1 大きい。

<例3> 例1の 2 を 5 に置き換える。57−1 = 56 = 15625 も、7 の倍数より 1 大きい。

フェルマーの小定理(フォーマル・バージョン) 任意の奇素数 p について、bp−1 ≡ 1 (mod p)。ここで b は p と互いに素な任意の自然数。(言葉で言うと: b の p−1 乗を p で割ると 1 余る。

≡ 1 (mod p) という記号は、「p の倍数より 1 大きい」言い換えれば「p で割ると 1 余る」という意味。正式には「p を法として 1 と合同」「コングルエント・トゥ 1、モジュロ p」と読まれるのだが、めんどくさいので「イコール1、モッドp」でいいでしょ。意味が分かれば、記号の読み方なんてどーでもいーじゃん?

何やら数学教師&優等生諸君が怒ってるようだが、無視、無視w

27. フェルマーの小定理は、p−1 乗すれば ≡ 1 になるという主張。…それは「p−1 乗しなければ ≡ 1 にならない」という意味ではない。例えば、
  【ア】 26 = 64 ≡ 1 (mod 7)
は上で確かめたけど、別に6乗しなくたって、3乗の時点で
  【イ】 23 = 8 ≡ 1 (mod 7)
が成り立つ。

けれど p−1 乗される数 b は選べるわけで、中には p−1 乗して初めて ≡ 1 (mod p) になるような b も必ずある。そのような b を原始根(げんしこん)という。小定理の証明、原始根の存在については、そのうちゆっくり研究するとして、とりあえず【ア】をこう書くことができる:
  26 = (23)2 ≡ 1 (mod 7)
23 を X と置くと:
  【ウ】 X2 ≡ 1 つまり X ≡ 1 or −1 (mod 7)

本当はもう少し繊細に扱う必要があるけど、常識で考えればそうなる(2乗して 1 になる数は、±1 のどっちかでしょ?)。【イ】では X ≡ 1 となった。一方、べき乗される数 b が原始根なら「途中」で 1 になることはないので、必然的に他方の選択肢 X ≡ −1 となる。例えば:
  【エ】 36 = 729 ≡ 1 (mod 7)
は上で確かめたけど、6乗の「半分」の3乗の時点では:
  【オ】 33 = 27 ≡ −1 (mod 7)
…ここで ≡ −1 (mod 7) は「7 の倍数マイナス 1」という意味(28 は 7 の倍数。27 はそれマイナス 1)。33 を X と置くと【ウ】と同様だが、今度は 1 or −1 の部分で、マイナス側が選択された!

観察 フェルマーの小定理から bp−1 ≡ 1 (mod p) だが、p−1 乗の「半分」…つまり b の (p−1)/2 乗…を計算すると ≡ 1 または ≡ −1 (mod p) になる。特に b が原始根なら:
  b(p−1)/2 ≡ −1

ところで、p が 7 のような 4k+3型の素数(愛称: チョコレート素数)の場合、「そのまた半分」を考えることはできない。だって、p = 4k+3 なら p−1 の半分 (p−1)/2 = (4k+2)/2 = 2k+1 は奇数。「そのまた半分」が無理な理由は、「奇数は、整数の範囲では半分にできないから」。当たり前。

28. 一方、p が 4k+1型の素数(愛称: バニラ素数)なら、「p−1 の半分」乗…つまり (p−1)/2 乗…を考えられるのはもちろん、「そのまた半分」乗…つまり (p−1)/4 乗…を考えることもできる。だってさぁ p = 4k+1 [例: p = 13] なら (p−1)/2 = (4k)/2 = 2k は偶数なんだから[例: (13−1)/2 = 6]、その数はもう一度2で割り切れるでしょ。例:
  【カ】 2(13−1) = 212 = 4096 ≡ 1 (mod 13)
  【キ】 2(13−1)/2 = 26 = 64 ≡ −1 (mod 13)
  【ク】 2(13−1)/4 = 23 = 8 ≡ 8 (mod 13)

【ク】は、2乗すると ≡ −1 になる数。事実 82 = 64 ≡ −1。原始根を2乗・3乗・4乗…すると、p−1 乗して初めて 1 になるのだから、(p−1)/2 乗や (p−1)/4 乗では、まだ ≡ 1 にならない。軽く整理すると:
  【ケ】 p が 4k+1型の素数(バニラ)なら x2 ≡ −1 (mod p) を満たす x が存在する(例えば、原始根 b を使って、x ≡ b(p−1)/4 を計算すればいい)。
  【コ】 p が 4k+3型の素数(チョコレート)なら x2 ≡ −1 (mod p) を満たす x は存在しない(b として何を選ぼうが、そもそも (p−1)/4 乗という計算ができない)。

「x2 ≡ −1 (mod p) が解を持つこと・持たないこと」を、難しい言葉でそれぞれ「−1 は法 p の平方剰余(じょうよ)・平方非剰余(ひじょうよ)」という。「−1 が平方剰余であること」は、次のように書かれることがある(ルジャンドルの記号):
  【サ】 (−1 | p) = 1  ……【ケ】の場合。右辺の +1 は「Yes, 平方剰余」という意味
−1 が平方非剰余であることは
  【シ】 (−1 | p) = −1  ……【コ】の場合。右辺の −1 は「No, 平方剰余じゃない」という意味
と書かれる。どちらになるかは p がバニラ(4k+1型)か、チョコ(4k+3型)かによって決まる。【サ】【シ】を一つの式にまとめると:
  【ス】 (−1 | p) = (−1)(p−1)/2

【ス】は「平方剰余の相互法則の第一補充法則」(なげえ名前だな)と呼ばれ、直観的な意味が分かりにくいことで有名(?)だが、p が 4k+1型なら (4k)/2 = 2k で偶数だから【ケ】【サ】になり【ス】右辺の指数も、それに見合って、−1 の偶数乗は 1。一方、p が 4k+3型なら (4k+2)/2 = 2k+1 で奇数だから【コ】【シ】になり、【ス】右辺の指数も、それに見合って、−1 の奇数乗は 1。【ス】の直接的な意味はさておき、上のように考えると、第一補充法則は意外と単純かも…?

29. それがどうガウス整数と結び付くの?

素数 p は、2個の平方数の和の形で書けることもある。p = 13 なら 13 = 4 + 9 = 22 + 32 のように…。一方、p = 11 も素数だけど、どう頑張っても、11 を 2個の平方数の和で書くことはできない。

一般に p = A2 + B2 と書けたと仮定すると(A, B は自然数)、当然 A2 + B2 は p で割り切れる(商は 1、余り 0)。割り切れるも何も、両者は等しいのだから、「5 は 5 で割り切れる」みたいな当たり前の話。A2 + B2 を p で割ると 0 余るのだから:
  A2 + B2 ≡ 0 (mod p)
  A2 ≡ −B2 (mod p)
両辺に B2 の逆数を掛けると:
  A2 / B2 ≡ −B2 / B2 つまり…
  【セ】 (A / B)2 ≡ −1 (mod p)
【セ】は、とある数 (A/B) を平方したら ≡ −1 (mod p) になった…という意味。そのような「とある数」が存在するか?という問題は、
  x2 ≡ −1 (mod p) を満たす x が存在するかしないか?
…つまり、mod p において −1 が平方剰余か非剰余か?という問題。既に見たように、その答えは「p は 4k+1型か、それとも 4k+3型か?」によって決まる。4k+3型なら、第一補充法則により【セ】は絶対に成り立たない。どう頑張っても、p = 11を2個の平方数の和では書けないのは、11 が 4k+3型素数(チョコレート)だから。p = 13 ならOKなのは、13 が 4K+1型素数(バニラ)だから。

注意深い読者はここで疑問を抱くかもしれない。「ちょっと待て、A と B は自然数だろ。自然数の世界で 1/B なんて反則じゃん。例えば B = 3 なら 1/3 は自然数じゃないし」…実は、A, B は確かに自然数だが、それ以降の式変形は普通の等式 = でなく、合同の記号 ≡ になってる。この演算が行われる世界では、自然数や整数の世界と違って普通に割り算ができ、必ず B の逆数 1/B が存在する(例えば B ≡ 3 (mod 13) なら 1/B ≡ 9。実際、3 × 9 = 27 ≡ 1 (mod 13) なので 9 は 3 の逆数)。ただし「法 p が素数」ということが前提。この点については、機会があれば、もっときちんと考えてみたい。ここでは具体例の確認だけ…
  A = 2, B = 3 は A2 + B2 = 13 ≡ 0 (mod 13) を成立させる。
  このとき 1/B ≡ 9 なので(上述)、A/B ≡ A × (1/B) ≡ 2 × 9 ≡ 18 ≡ 5 (mod 13)
  この数は実際に【セ】を満たす: (A/B)2 ≡ 52 ≡ 25 ≡ −1 (mod 13)
  つまり −1 は法 13 の平方剰余!

雑な議論だが、大筋において「4k+3型の素数は、絶対に2個の平方数の和の形で書けない!」という結論が得られた。逆に「4k+1型素数なら、2個の平方数の和の形で書ける可能性がある」ことが示唆されるが、上の議論だけでは「必ず書ける!」という確信までは得られない。

第一補充法則によれば p がバニラ素数の場合、x2 ≡ −1 (mod p) を満たす x が存在する。ちょっと変形すると:
  x2 + 1 ≡ 0 (mod p)
つまり x2 + 1 は p で割り切れる。この左辺は、ガウス整数の範囲では…
  x2 + 1 = x2 − (−1) = x2 − i2 = (x + i)(x − i)
…と分解されるので、x2 + 1 が p で割り切れるのなら、それと等しい (x + i)(x − i) も、当然 p で割り切れる。

ところで、一般の整域(例えばガウス整数)における素数の定義っていうのは、意外と複雑。「任意の積 ab が p で割り切れるとき、必ず a が p で割り切れるか、または b が p で割り切れる」…素数とは、そういう性質を持つ p のこと(詳細は 36. 以降)。上記の場合、(x + i)(x − i) は p で割り切れるものの、ガウス整数 x + i もガウス整数 x − i も、ガウス整数の範囲において p では割り切れない(無理やり割っても、結果の x/p + i/p などはガウス整数にならない)。ということは、ガウス整数の範囲では、バニラ素数 p は、もはや素数ではない。

もしガウス整数の範囲でも、ちゃんと素因数分解ができるとするなら(重大な「もし」である!)、バニラ素数 p はもはや素数でない以上、さらに分解され、例えば p = αβ となるはず。ここで α = s + ti は、とあるガウス整数(s, t は通常の整数)、β もまた同様。実は α = s + ti なら β は共役の s − ti となり(その理由はノルムと関係ある)、ガウス整数の範囲での分解…
  p = (s + ti)(s − ti)
…が成立。右辺を展開すると:
  p = s2 + t2
つまり普通の意味での素数 p は、それが 4k+1型なら、必ず2平方数の和で表される!

「ゴルゴ13」分解計画 9. も参照。

以上の考察には、あちこちにギャップがある。まず、最も大切なピースが一つ抜けている: そもそも素数の定義とは…? 「1 と自分自身」以外では割り切れない数、という古典的定義では駄目なの?

これは見かけ以上に深い問題だけど、表面的な話として、任意のガウス整数は i で割り切れる。「1 と自分自身」以外では割り切れない数、という定義だと、全てのガウス整数は(「1 と自分自身」以外の i で割り切れるのだから)素数でない…ガウス整数の世界には素数がないので素因数分解もできない…という結論になってしまい、それだけでも非常に具合が悪い。「じゃあ素数とは何なのか」「どういう根拠で、何をどう定義すればいいのか」…考えるモチベーション、素朴な好奇心がちょっとは湧いてくる。

ガウス整数などの少し広い観点から眺めるとき、いつしか一つの予感が芽生える。古典数論の雑多な話題(フェルマーの小定理、クリスマス定理、平方剰余、補充法則など)は、どれも同じ一つの本質から生じてくるのではないか…。「数の不思議」の根底にある真相が分かり、全てをすっきり透明に見通すことができれば、それは素敵なことだろう。

とびきり楽しい冒険しよう!

⁂

2021-11-23 ガウス整数から見た 3² + 4² = 5² (その3)

30. ガウス整数の範囲では x2 + y2 = (x + yi)(x − yi) だが、ピタゴラス・トリオ (x, y, z) の場合、このように分解した因子の x + yi が再び平方数 (A + Bi)2 になる。他方の因子 x − yi も同様の平方数 (A − Bi)2 になる(21.参照)。理由が分かれば「当たり前」かもしれないが、
  32 + 42 = 52 ⇒ (3 + 4i)(3 − 4i) = (2 + i)2(2 − i)2 = (22 + 12)2
  52 + 122 = 132 ⇒ (5 + 12i)(5 − 12i) = (3 + 2i)2(3 − 2i)2 = (32 + 22)2
といった構造は、本当とは思えないほど美しい。素直に感動!

もっとも x + yi の形…例えば 3 + 4i…を (A + Bi)2 の形…例えば (2 + i)2…に変換する魔法は、まだ修得していない。要するに「ガウス整数の世界の素因数分解」だが、その研究は後のお楽しみ!

呪文でホラ変身よ> 3 + 4i パリエルレムリン・スイートミント、ガウス素数になぁれ~ = (2 + i)2

逆方向の変換法は、既に分かっている。例えば (2 + i)2 つまり A = 2, B = 1 を x + yi の形にするには、2乗の部分を展開するだけ。一般に、こうなる(「その222.):
  x = A2 − B2
  y = 2AB
  z = A2 + B2
分解されているものを掛け合わせるのは簡単だが、掛け合わされているものを分解するのは難しい…。「自分は数学が得意だから、そんなの全然難しくないよ」と考える人もいるかもしれないが、「計算量的に本当に難しい」というのが多くの専門家の予想であり、実際この予想が、日常、インターネット上で使われるRSA系の暗号システムの基礎となっている。

とはいえ最近…大ざっぱに2010年くらいから…「難しいといっても、原理的にはやればできるし」「パスワードとかクラックされたら、セキュリティー的にやばいし」というムードが強まって、「RSAでも桁数をさらにでかくしよう」「RSA系自体が不安だから、楕円曲線暗号に移行しよう」という流れになっている。楕円なら安全? それもまた、誰にも分からない未解決問題。数論の世界には、未知がいっぱい。教科書に書いてあることを覚えればいい、なんていう、甘い話じゃない。ある意味「ロマン」だが、難しくて途方に暮れてしまう。

31. ピタゴラス・トリオについては、上記の A, B の性質がよく分かっているので、次の例のように、いくらでも機械的に生成できる(「その2」付録)。

[  1 ] A= 2, B= 1 ::: (3,4,5)
[  2 ] A= 3, B= 2 ::: (5,12,13)
[  3 ] A= 4, B= 1 ::: (15,8,17)
[  4 ] A= 4, B= 3 ::: (7,24,25)
[  5 ] A= 5, B= 2 ::: (21,20,29)
[  6 ] A= 5, B= 4 ::: (9,40,41)
[  7 ] A= 6, B= 1 ::: (35,12,37)
[  8 ] A= 6, B= 5 ::: (11,60,61)
[  9 ] A= 7, B= 2 ::: (45,28,53)
[ 10 ] A= 7, B= 4 ::: (33,56,65)

これをじっと眺めると、トリオの最後の数 z に素数が多いことが目に付く: 5, 13, 17, 29 など…。これらの素数は、どれも「4で割ると1余る素数」(愛称: バニラ素数)のようだ。それは実は当たり前。だってさぁ、
  z = A2 + B2
って、2個の平方数の和じゃん? しかも、AとBって、一方が偶数、他方が奇数(22.参照)。偶数の2乗は、4の倍数(★)。奇数の2乗は、4の倍数プラス1(☆)。それらの和(★プラス☆)も、4の倍数プラス1。だから z は、素数であっても素数でなくても、必ず「4で割ると1余る数」。

(★) どんな偶数も、2の倍数なので 2n の形を持つ(n は整数: 例えば、偶数6は 2×3)。その2乗は: (2n)2 = 4n2。これは「4 の n2倍」なので、4の倍数。

(☆) どんな奇数も、2の倍数より1大きいので 2n+1 の形を持つ(n は整数: 例えば、奇数7は 2×3+1)。その2乗は: (2n+1)2 = 4n2 + 4n + 1 = 4(n2 + n) + 1 = 4の倍数 + 1。

具体例を眺めると、逆にどのバニラ素数も、必ずピタゴラスの z となるように思える(この予想は実は正しい)。けれど今は、別の部分に注目したい。

z が全部素数になるなら「ありがちな展開」かもしれないけど、なんか 5 の倍数が交じってるよ? 上の例では 25 と 65。何だ、この連中? そっちの方が気になる。

暫定的に「ピタゴラストリオの z は、バニラ素数または5の倍数になる」という予想が浮かぶ。ところが、上記の「付録」をよーく見ると、この予想は正しくない:

[ 29 ] A=12, B= 5 ::: (119,120,169)

この z = 169 は 132 であり、素数でも5の倍数でもない。予想に合わない「反例」ってやつ。素早く予想を修正して「素数でない z は、5の倍数または平方数」と言いたい気もするが、本当だろうか?

話がちょっと戻るが、まだ導入してない x + yi の素因数分解の技術。やり方はともかく、結果としては…
  [1] 3 + 4i = (2 + i)2
  [2] 5 + 12i = (3 + 2i)2
  [3] 15 + 8i = (4 + i)2
  [4] 7 + 24i = −(1 + 2i)4
  [5] 21 + 20i = (5 + 2i)2
  [6] 9 + 40i = (5 + 4i)2
…だいたいは、前述の通り、そのまんま「何かの2乗」の形になってる。4番だけ、何やら妙な形。4乗なので、これも「何かの2乗」の形に書き直すことができ(20. & 21.参照)、上記 30. の主張に間違いはないのだが…。「ピタゴラストリオの式の左辺を(ガウス整数として)分解した因子」という同じ性質のものなのに、なぜ一つだけ他と違う形なのだろう?

「素数でない z は、どういう数か?」という疑問。そしてこの、釈然としない現象。

実は、この二つのもやもやは関連していて、全てをすっきり透明に見通せる観点が存在している。…それは分かってしまえば簡単なことで、客観的には当たり前のことなので、いちいち教科書には記されてないだろうけど、主観的には意外と面白い。どんな小さな命題だって、自力で独立に発見した事柄は、キラキラ心に残るだろう。

24.では「バシェ/ベズの定理」を導入して、懸案の「ガウス整数の一意分解」を攻略する伏線を張った。教科書的には「一意分解ができること」を証明してから、具体例を挙げるのが正しいだろうけど、「一意分解」という抽象的性質を考える前に、「分解の具体例」を体験して感覚をつかむ方が、たぶん分かりやすい…。記事にまとめるとき、余計な脱線を削除して、説明が抜けてるところを補い、整理したい。

⁂

2021-11-24 ガウス整数 13i の因数分解 実例研究その1

当面の目標は「ガウス整数の世界でも一意的な素因数分解ができる」という命題だけど、実際の証明の前に実例をいくらかいじって、感覚をつかんでおきたい。ユークリッド整域なので「既約」と「素数」の違いを隠したまま話を進めることもでき、その方がお手軽だが…。「その二つは異なる概念」というのが、問題の核心だろう。ある時点で、思い切りカメラを引いて「世界を外側から眺めること」が必要になる。まぁ流れに任せて適当に…。

32. 純虚数のガウス整数 13i を分解できるだろうか?

13 はバニラ素数なので、2平方数の和。42 = 16 は大き過ぎるから、12 = 1, 22 = 4, 32 = 9 の範囲で和を考える。簡単な試行錯誤の結果(総当たりでも数パターンしかない):
  13 = 22 + 32 = (2 + 3i)(2 − 3i)
  つまり 13i = (2 + 3i)(2 − 3i)i = (2 + 3i)(2i + 3)  (*)

出てきた因子の A = 2 + 3i などは、もうこれ以上分解できないのだろうか?

ここでクリティカルな役割を果たすのが「ノルム」(15.参照)。0でないガウス整数 A が、2個のガウス整数の積 PQ に分解されたとしよう。つまり
  A = PQ
が成り立ったとしよう。上の式の両辺のノルムを考えると:
  norm(A) = norm(PQ) = norm(P) norm(Q)
A = 2 + 3i の場合、norm(A) = 13 は普通の意味での素数なので、これ以上意味のある分解はできない。強いて言えば norm(P), norm(Q) の一方が13、他方が1で 13 = 13 × 1 という分解が考えられるが、ノルム1の数は ±1, ±i に限られ、これらは真の約数ではない(普通の素因数分解で、因子 1 が無視されるのと同じ)。要するに、ノルムが素数なら、もうそれ以上、分解できない

この場合、2 と 3 の順序を入れ替えて次のように書いても、最終的な結論は同じ:
  13 = 32 + 22 = (3 + 2i)(3 − 2i)
  つまり 13i = (3 + 2i)(3 − 2i)i = (3 + 2i)(3i + 2)  (*)と同じ

⁂

2021-11-25 ガウス整数 1 + 13i の因数分解 実例研究その2

33. いきなり α = 1 + 13i を分解しろと言われても、どこから手を付けていいのか分からない感じだが…。ガウス整数が分解されるときには、対応するノルムも、普通の整数の範囲で分解されるのだった。とりあえずノルムを調べてみよう:
  norm(α) = norm(1 + 13i) = 12 + 132 = 170 = 2 × 85

85 はさらに 5 で割れるが、今は 2 の方に集中する。状況を再確認:
  α = βγ なら norm(α) = norm(β) norm(γ)
  ここでは α = 1 + 13i で norm(α) = 170, norm(β) = 2, norm(γ) = 85。

要するに、ノルムが 2 のガウス整数 β を見つければ、α = βγ のような分解が成り立つ可能性がある。具体的に α/β が割り切れれば、α/β = γ と置いて α = βγ となる。注意点として
  α = βγ なら norm(α) = norm(β) norm(γ)
というのは確かだが、逆が成り立つ保証はない。つまり、
  norm(α) = norm(β) norm(γ) だからといって α = βγ とは限らない。
言い換えると α/β が割り切れる保証はない。保証はなくても可能性はあるので、試すだけ試してみたい。

問題 norm(β) = 2 を満たすガウス整数 β は何か?

先に感覚的なアプローチ、後からきっちりしたアプローチを…。感覚的には、「普通の整数をガウス整数の範囲で分解したいなら、2平方数の和で書けばいい」:
  2 = 12 + 12 = 12 − i2 = (1 + i)(1 − i)
従って β = 1 + i または β = 1 − i という可能性がある。

試しに α = 1 + 13i を第一候補 β = 1 + i で割ってみると(割り算の仕方は13.参照):
  α / β = (1 × 1 + 13 × 1) / 2 + [(13 × 1 − 1 × 1) / 2]i  【ア】
  = 14 / 2 + (12 / 2)i = 7 + 6i

イェーイ、割り切れたっ! 【ア】実部の分子は「実実・虚虚の和」、【ア】虚部の分子は「内内マイナス外外」、【ア】の分母は β のノルム(16.参照)。やり方を無理に丸暗記しなくても、13.のように普通に計算すれば同じ結果が得られる。とりあえず…

α = 1 + 13i = (1 + i)(7 + 6i)  【イ】

…ここまでは分解できた。石橋をたたく心構えで【イ】の右辺を展開してみる:
  (7 + 6i) + (7 + 6i)i = (7 + 6i) + (7i − 6) = 1 + 13i
うん、ちゃんと【イ】の左辺と等しい。

34. 【イ】右辺の第1因数 1 + i は、そのノルムが2(普通の意味での素数)なので、これ以上、分解できない。第2因数 7 + 6i については、そのノルムが 49 + 36 = 85 = 5 × 17 なので、ノルム 5 のガウス整数で割り切れる可能性がある。ノルム 5 のガウス整数(…名前がないと不便なので、ここでは、ノルム 5 のガウス整数を f と呼ぶことにする)を作るため、5 を2平方数の和として表現する:
  5 = 22 + 12 = 22 − i2 = (2 + i)(2 − i)
f = 2 + i または f = 2 − i は、ノルム5を持つ。

試しに f = 2 + i で割ってみる:
  (7 + 6i) / (2 + i) = (14 + 6) / 5 + [(12 − 7) / 5]i = 4 + i
割り切れた! 商のノルムは17(普通の意味での素数)なので、これ以上の分解はできず、これにて分解完了:
  1 + 13i = (1 + i)(7 + 6i) = (1 + i)(2 + i)(4 + i)

他方の選択肢 f = 2 − i を試すと何が起きるのか。
  (7 + 6i) / (2 − i) = (14 − 6) / 5 + [(12 + 7) / 5]i = 8/5 + (19/5)i
こっちだと、割り切れない。つまり、こっちは正しい因数ではない。「ノルム5」というのは大きな手掛かりだが、因数をピンポイントで確定させるほどの「決定的な情報」でもない。最終的には、地道に「試し割り」するしかなさそうだ。

35. 話を少し戻して、33.問題(β の導出)をもう少しきっちり考えてみたい。β = x + yi とすると(x, y は普通の整数)、
  norm(β) = norm(x + yi) = x2 + y2
…が 2 に等しいというのが条件なので:
  x2 + y2 = 2  【ウ】

x2 と y2 は、どちらも 0 以上の整数なので、【ウ】が成り立つとすれば、一方が 2 で他方が 0 になるか、または、両方とも 1 になる必要がある。「一方が 2」というパターンは無理(x2 = 2 のようなものは、整数の範囲で解けない)。従って、正解は x2 = y2 = 1 つまり x = ±1, y = ±1(符号の選択は自由):
  β = 1 ± i または −1 ± i  【エ】
選択肢がいっぱいあって扱いにくそうだが、複素平面上において、これらは全部「座標軸の2本の対角線」の上にあり、原点からの距離が一定。言い換えると、ベクトル (1, 1) を90°刻みで回転させたものに他ならない(回転方向は反時計回り)。(1, 1) はもちろん 1 + i に対応する点。さて、あるベクトルの180°の回転(つまり、原点から伸びる正反対の矢印)が、もともとのベクトルの −1 倍に対応することは、明らかだろう。90°の回転とは「2回繰り返すと180°の回転(つまり −1 倍)に対応する操作」なので、i 倍に当たる(i 倍したものをもう一度 i 倍すれば、最初の −1 倍になる)。

【エ】の4個の選択肢は、β = 1 + i を基準にすると (i)β, (i2)β = (−1)β, (i3)β = (−i)β に当たり、どの二つも互いに単数倍なので、通常の因数分解の観点からは、区別する必要ない。特に、
  2 = (1 + i) × (1 − i) の第2因子 (1 − i) について
  (1 − i) = −i(1 + i)
が成り立つので:
  2 = (1 + i) × [−i(1 + i)] = −i(1 + i)2
普通の意味での素数が、ガウス整数の範囲でさらに分解されるのは、よくあること。けれど 2 という数は、ガウス整数の世界で、何とも興味深い形で分解される…。一種の「平方数」、正確に言えば「平方数の単数倍」。イメージ的には、1 + i は偏角45°、絶対値 √2 のベクトルなので、自乗すると、結果は偏角90°、絶対値 2:
  2i = (1 + i)2
90° の回転を打ち消して実数に戻すため、−i を掛け算すると:
  2 = (1 + i)2 × (−i)

最後に、ノルム5の因子 f についても同様に考えると、【ウ】に当たるものは
  x2 + y2 = 5
…上記 β と同様に考えると、x2, y2 の一方が 4、他方が 1 になる必要があり、【エ】に当たるものは:
  f = 2 ± i または −2 ± i または 1 ± 2i または −1 ± 2i
ガウス整数の世界には単数が4種類しかないので、これら8パターンが全部「互いに単数倍」というのは不可能。第1グループとして、f = 2 + i とその単数倍(自分自身=1倍を含む)計4種は、本質的に同じ因子。第2グループとして、f = 2 − i とその単数倍・計4種は、本質的に同じ因子だが、第1グループとは異なる。実際、34. で見たように、一方では割り切れても、他方では割り切れないことがある。

β の例は特別で、虚部の符号を変えた相棒(正式名称: 共役)が互いに単数倍(正式名称: 同伴)になっていた。一般には f の例のように、虚部の符号を変えた相棒は「同伴」ではなく、友達以上・恋人未満…。「ノルムが同じ・絶対値も同じ・実部も同じで虚部の符号だけが正反対」という特別な関係ではあるけれど、「おれに割れる数なら、おまえにも割れる。おまえに割れる数なら、おれにも割れる」というほどの、一心同体の関係ではない。

⁂

(付録) 追加の実例

ガウス整数の分解について、大ざっぱな感覚がつかめたら、この付録を飛ばして 36. に進んでください。「もうちょっと練習してみたい・遊んでみたい」方は、どうぞ…。

☆ α = 2 + 13i を分解。norm(α) = 4 + 169 = 173。このノルムは分解不可能。なぜなら、実際に試すと 2, 3, 5, 7, 11 のどれでも割り切れず、製造方法からして 13 でも割り切れない(13 で割ると 4余る)。17 で割り切れないこともすぐ分かるが、そもそも 17 が最小の素因数になるためには 172 = 289 以上であることが必要。結論として、このノルムは素数。だから α も分解不可能。

☆ α = 3 + 13i を分解。norm(α) = 9 + 169 = 178 = 2 × 89。ノルム 2 のガウス素数 β = 1 + i で割れる可能性が高い。実際に割ってみると α/β の実部は (3 × 1 + 13 × 1)/2 = 8、虚部は (13 × 1 − 3 × 1)/2 = 5。結論として α = (1 + i)(8 + 5i)。…8 + 5i は、ノルムが素数89なので、それ以上、分解不可能。

☆ α = 4 + 13i を分解。norm(α) = 16 + 169 = 185 = 5 × 37。ノルム 5 のガウス素数 f = 2 ± i で割れる可能性が高い。2 + i で割ってみると、商の実部は (4 × 2 + 13 × 1)/5 = 21/5。割り切れない。2 − i で割ってみると、商の実部は (4 × 2 − 13 × 1)/5 = −5/5 = −1、虚部は (13 × 2 − 4 × (−1))/5 = 30/5 = 6 なので、α = (2 − i)(−1 + 6i)。…この第2因子は、ノルムが素数37なので、これ以上、分解不可能。

不可欠な処理ではないが、そうしたければ、全部の因子を第1象限の数(偏角90°未満)の単数倍として表現できる。1回 i を掛けるごとに90°回転することを念頭に、第2・第3・第4象限にある因子については、それぞれ i3 = −i, i2 = −1, i1 = i を掛ければ、第1象限の数になる。この計算を正当化するためには、それぞれ単数 i1, i2, i3 をくくり出す必要がある。上記の例では:
  第4象限の 2 − ii 倍すると 2i + 1 なので (2 − i) = i3(1 + 2i)
  第2象限の −1 + 6i は −i 倍すると i + 6 なので (−1 + 6i) = i1(6 + i)
  だから α = (2 − i)(−1 + 6i) = i3(1 + 2i)i1(6 + i) = (1 + 2i)(6 + i) と書き換え可能。

☆ α = 5 + 13i を分解。norm(α) = 25 + 169 = 194 = 2 × 97。ノルム 2 のガウス素数 β = 1 + i で割れる可能性が高い。実際に割ってみると α/β の実部は (5 × 1 + 13 × 1)/2 = 9、虚部は (13 × 1 − 5 × 1)/2 = 4。結論として α = (1 + i)(9 + 4i)。…9 + 4i は、ノルムが素数97なので、それ以上、分解不可能。

ところで、次の3命題は同値:

  1. ガウス整数 α = x + yi は、偶数のノルムを持つ。
  2. α の実部と虚部は、偶奇が一致する。
  3. α は 1 + i で割り切れる。

例えば 565 + 13i のような数を見たら(565 と 13 は両方奇数、つまり偶奇が一致するので)、瞬時に 1 + i で割り切れると判定できる。

証明 偶数の2乗は偶数、奇数の2乗は奇数なので、整数の偶奇に関しては、その数自身を考えても、その数の2乗を考えても、同じこと。今、x2, y2 の両方が偶数であるか、または両方が奇数なら、norm(α) = x2 + y2 は(偶数同士の和、または奇数同士の和なので)偶数。それ以外の場合(つまり x2, y2 の一方が偶数で他方が奇数なら)、norm(α) = x2 + y2 は(偶数と奇数の和なので)偶数にならない。だから、最初の2命題は同値。さて、α が 1 + i で割り切れるということは、
  (x + yi) / (1 + i) = (x + y)/2 + [(y − x)/2]i
の分数が割り切れるということであり、つまり x + y と y − x がどちらも偶数ということ。場合分けして考えると、それは x と y の偶奇が一致することと同じ意味。だから、2番目の命題と3番目の命題も同値。□

⁂


<メールアドレス>