余りのある割り算

前のステージで、既約元がどれも素元（p が ab を割り切れば a か b を割り切る数）なら、素因数分解はただ1通りになると分かった。今日はいよいよ、整数の素数が素元であることを証明する。そして同じ方法がガウス整数の世界でも使えることを確かめる。そうすれば、1つ目の謎を解く道具がそろうんだ。おまけに、第1章で存在だけ確かめた mod p の逆数を、実際に計算する方法も手に入る。道具は割り算だ。17 を 5 で割ると、どうなるかな？

そう。どんな整数 a と正の整数 b でも、b の倍数のうち a を超えない最大のものを qb とすれば、a＝qb＋r で余り r は 0 以上 b 未満になる。これが余りのある割り算だ。これをくり返すのがユークリッドの互除法だよ。84 と 30 で、大きいほうを小さいほうで割り、次は割った数を余りで割り…と、余りが 0 になるまで続けてごらん。

そう。最後の 0 でない余りは、いつでも2つの数の最大公約数になる。その理由を確かめよう。84 と 30 の公約数と、30 と 24 の公約数を比べてごらん。24＝84−30×2 だね。

そう。割り算を1回するたびに数の組は変わるけれど、公約数の集まりは変わらない。最後はどうなるかな？

互除法には、長方形を使った見方もある。横 84・縦 30 の長方形から、1辺 30 の正方形をできるだけ切り取ると、残りは横 24・縦 30 の長方形だ。そこから1辺 24 の正方形を切り取り…とくり返すと、最後の正方形の1辺が最大公約数になる。

そう。互除法には、もう1つ大事な使い道がある。最後の余り 6 を、途中の式を下からたどって、84 と 30 だけで書いてごらん。

そう。上からたどっても分かる。最初の余り 24 は 84−30×2 で、「84×整数＋30×整数」の形だ。次の余りは「ひとつ前の割る数−商×ひとつ前の余り」だから、どうなるかな？

よく見抜いたね。さあ、p を素数、a を p で割り切れない整数としよう。何が言えるかな？

そう。第1章では、mod p の掛け算表の各行に 1 が1回ずつ出ることから逆元があることを確かめたけれど、互除法を使うと、どんなに大きな p でも逆元を計算できる。RSA 暗号の秘密鍵 d も、e×d≡1 (mod φ(n)) をみたす数だったから、同じ計算で求まる。たとえば φ(n)＝20、e＝3 なら？

その通り。では本題に戻ろう。ax＋py＝1 の両辺に b を掛けてごらん。そして、p が ab を割り切るとしよう。

その通り。この証明で本当に使った道具は何だったかな？

そう。だから、ガウス整数でも余りのある割り算ができれば、同じ証明が通る。複素数には大小がないから、「小さい」はノルムで測ろう。z を w で割って z＝qw＋r、N(r)＜N(w) にできればいい。まず z÷w を計算する。分母の w＝3＋2i に 3−2i を掛けると、(3＋2i)(3−2i)＝9＋4＝13 で実数になる。z＝10＋7i として、z÷w を求めてごらん。

そこで、z÷w にいちばん近いガウス整数を商 q に選ぶ。q＝3 だね。余り r＝z−qw を計算してごらん。

それを確かめよう。z÷w は平面のどこかの点で、ガウス整数の点は1辺 1 の正方形の角に並んでいる。z÷w にいちばん近い角を q に選ぶと、z÷w と q の距離はどこまで大きくなりうるかな？

よく確かめたね。ガウス整数でも余りのある割り算ができるから、互除法が使える。割るたびに余りのノルムが小さくなるから、必ず止まる。そして、整数のときと同じ理由で、最後の 0 でない余り d は2つの数の公約数で、しかも「z×（ガウス整数）＋w×（ガウス整数）」の形に書ける。では、π をガウス整数の既約元、a を π で割り切れないガウス整数としよう。π と a で互除法をすると、最後の余り d について何が言えるかな？

その通り。だからガウス整数の素因数分解も、順番と単数の違いを除いてただ1通りになる。整数の一意性も、ガウス整数の一意性も、「余りのある割り算ができる」という1つの性質から出てきたんだ。次のステージでは、この一意性を使って、いよいよ1つ目の謎、2つの平方数の和の謎を解こう。