ユークリッドの互除法の正しさ

大きな整数の最大公約数は、約数をすべて列挙しなくても求められます。ユークリッドの互除法は「割った余りに置き換えても共通の約数は変わらない」という事実に基づきます。答えが正しい理由と、必ず終了する理由を分けて示します。

成立する条件

ここでは正整数を扱い、最大公約数を正に取ります。一般の整数は絶対値に置き換えられます。

$\gcd(b,0)=b$（$b>0$）とします。$\gcd(0,0)$ はこの手順の対象に含めません。

証明

1. $d$ が $a,b$ の共通の正の約数だとします。$a,b$ が $d$ の倍数なら、その整数係数の差 $a-bq=r$ も $d$ の倍数です。したがって $d$ は $b,r$ の共通の約数です。
2. 逆に、$d$ が $b,r$ の共通の正の約数なら、$a=bq+r$ も $d$ の倍数です。よって $d$ は $a,b$ の共通の約数です。
3. 以上の両方向により、二組の共通の正の約数は完全に一致します。したがって、その中で最大のものも等しく、$\gcd(a,b)=\gcd(b,r)$ が得られます。
4. 余りが非零なら、次に $b$ を $r$ で割ります。現れる非零の余りは正整数で、$b>r>\cdots$ と真に減少します。正整数の真の減少列が無限には続かないので、有限回で余りが $0$ になります。
5. 最後に得られた組を $(d,0)$ とすると、その最大公約数は $d$ です。各段階で最大公約数が変わらないことを既に示したため、この $d$ が最初の二整数の最大公約数です。

使ってみる

$252$ と $105$ では、$$252=105\cdot2+42,\quad105=42\cdot2+21,\quad42=21\cdot2+0.$$ 最後の非零の余りは $21$ なので、$\gcd(252,105)=21$ です。

式を逆向きにたどると $21=105-2(252-2\cdot105)=5\cdot105-2\cdot252$。最大公約数を元の整数の整数係数の和で表す拡張互除法にもつながります。

注意点

最後の「余り $0$」を答えにしないでください。答えはその一つ前の非零の余りです。公約数が保存される理由だけでは終了の証明にはならず、余りが小さくなることも必要です。最初の余りが0の場合は、元の小さい方の数 $b$ が答えになります。

関連項目