ユークリッドの互除法

方針

解答

⓪ 発想 — どう考え始めるか。 $319$ と $377$ の最大公約数。素因数分解しようとしても、手が止まるはずだ($319$ を割り切る素数がすぐには見えない)。

こういうときのための道具がユークリッドの互除法である。手順は機械的だ。

大きいほうを小さいほうで割り、余りを出す。次は「割る数」と「余り」で同じことを繰り返す。余りが $0$ になったら、そのときの割る数が答え。

$$377÷319=1\cdots \text{余り }58$$

$$319÷58=5\cdots \text{余り }29$$

$$58÷29=2\cdots \text{余り }0$$

余りが $0$ になった。そのとき割っていた数 $29$ が最大公約数。

最後の余り($0$)ではなく、その手前の「割る数」が答え。 ここを取り違えないこと。

互除法は『割って余りを出す』をくり返すだけだ。$377$ を $319$ で割ることから始める。

$$377=1\times 319+58$$

$$319=5\times 58+29$$

$$58=2\times 29+0$$

余りが $0$ になった。そのときの割る数 $29$ が最大公約数だ。

$$\gcd (319,377)=29$$

(なぜこれで求まるのか。『$377$ と $319$ の公約数』は『$319$ と余り $58$ の公約数』とぴったり同じ — 余りを取っても公約数は変わらない。だから数をどんどん小さくしていって、最後に残る数が最大公約数になる。素因数分解しにくい大きな数でも使えるのが強みだ。)

発展 — 一歩先へ。 互除法には、逆に読むという使い方がある。計算の跡を逆走すると、次の形の式が作れるのだ。

$$319x+377y=29(\text{整数 }x,y)$$

実際、互除法の式を下から順に代入していくと

$$29=319-58\times 5=319-(377-319)\times 5=319\times 6-377\times 5$$

$x=6$、$y=-5$ が見つかった。 確かめると $319\times 6-377\times 5=1914-1885=29$ ✓。

一般に、次の定理が成り立つ。

$$ax+by=\gcd (a,b)\text{を満たす整数 }x,y\text{ が必ず存在する}$$

これは強力だ。 特に $a$ と $b$ が互いに素($\gcd =1$)なら

$$ax+by=1$$

を満たす整数が存在する。これが $1$ 次不定方程式が解ける理由であり(次の問題で使う)、暗号理論で「逆元を求める」操作の正体でもある。

互除法は、gcd を求めるだけの道具ではない。 割り算の跡を逆にたどることで、方程式の解までもたらしてくれる。

$2300$ 年前のアルゴリズムが、なぜ今も現役なのか — 速いだけでなく、副産物として深い情報を吐き出すからだ。数学の道具は、しばしば作った人の意図を超えて働く。

別解

互除法が本当に正しいのか、素因数分解で答え合わせをしよう。そして互除法を図形として見ると、この $2300$ 年前のアルゴリズムの美しさが分かる。

答え合わせ: 素因数分解でも求めてみる。

$$319=11\times 29,377=13\times 29$$

共通の素因数は $29$ だけ($11$ と $13$ は互いに素)。

$$\gcd (319,377)=29✓$$

互除法の答えと一致した。

しかし、この分解を見つけるのは大変だったはずだ。$319$ を $2,3,5,7$ で割っても割り切れず、$11$ でようやく割れる。$377$ も $13$ まで試す必要がある。互除法なら、割り算 $3$ 回で終わった。

互除法を、図形で見る。

$377\times 319$ の長方形を、正方形のタイルで敷き詰めることを考えよう。できるだけ大きな正方形で、余りなく敷き詰めたい。

手順1: いちばん大きく取れるのは $319\times 319$ の正方形。$1$ 個切り取ると、$58\times 319$ の長方形が残る。

$$377=319\times 1+58$$

手順2: 残った長方形から、$58\times 58$ の正方形を切り取る。$5$ 個取れて、$29\times 58$ が残る。

$$319=58\times 5+29$$

手順3: $29\times 29$ の正方形がちょうど $2$ 個で、余りなく埋まった。

$$58=29\times 2+0$$

最後にぴったり埋まった正方形の $1$ 辺が $29$。これが最大公約数である。

互除法とは「長方形を、できるだけ大きな正方形で敷き詰める手続き」だったのだ。ユークリッドが『原論』でこれを幾何の言葉で書いたのは、偶然ではない。$2$ つの数の共通の"ものさし"を探す — それが最大公約数の意味である。

互除法の速さ。 この方法は、驚くほど速い。$2$ 数がどんなに大きくても、割り算の回数は桁数の $5$ 倍程度にしかならない(フィボナッチ数列を使って証明できる)。

$300$ 桁の数どうしでも、$1500$ 回程度の割り算で gcd が出る — 一瞬だ。一方、同じ数を素因数分解しようとすれば、宇宙の年齢でも足りない。

「割り算を繰り返す」という原始的な操作が、素因数分解という難問を迂回して、答えにたどり着く。 アルゴリズムの勝利である。