ユークリッドの互除法の正当性の証明

証明する内容

$a$、$b$を正の整数とし、$a$を$b$で割ったときの商を$q$、余りを$r$とします。つまり、

$a = bq+r, \qquad 0\leq r

が成り立っているとします。このとき、次の等式が成り立ちます。

$\gcd(a,b) = \gcd(b,r)$

ここで$\gcd(x,y)$は、$x$と$y$の最大公約数(公約数のうち最も大きいもの)を表します。

これが、ユークリッドの互除法が正しく最大公約数を計算できることの根拠になっている事実です。直感的には、「$a$と$b$の最大公約数を求める問題は、より小さい数の組である$b$と$r$(=$a$を$b$で割った余り)の最大公約数を求める問題に置き換えても答えが変わらない」ということを意味しています。これを繰り返し使うことで、どんどん小さい数の組に置き換えながら、最終的に余りが$0$になったところで最大公約数が求まります。

証明

準備:割り算に関する2つの補助的な事実

まず、この先の証明で何度も使う、割り算に関する基本的な事実を2つ確認しておきます。ある整数$d$が整数$m$を「割り切る」(記号で$d\mid m$と書きます)とは、ある整数$k$を使って$m=dk$と表せることをいいます。

補助事実A:$d\mid x$ かつ $d\mid y$ ならば、$d\mid(x+y)$ かつ $d\mid(x-y)$ が成り立つ。

これを確認します。$d\mid x$ より、ある整数$s$を使って$x=ds$と書けます。$d\mid y$ より、ある整数$t$を使って$y=dt$と書けます。このとき、

$x+y = ds+dt = d(s+t)$

$s+t$は整数どうしの和なので整数です。したがって、$x+y$は$d$に整数をかけた形で表せるので、$d\mid(x+y)$が成り立ちます。同様に、

$x-y = ds-dt = d(s-t)$

$s-t$も整数なので、$d\mid(x-y)$も成り立ちます。

補助事実B:$d\mid x$ ならば、どんな整数$k$に対しても $d\mid(xk)$ が成り立つ。

これを確認します。$d\mid x$ より、ある整数$s$を使って$x=ds$と書けます。このとき、

$xk = (ds)k = d(sk)$

$sk$は整数どうしの積なので整数です。したがって、$xk$は$d$に整数をかけた形で表せるので、$d\mid(xk)$が成り立ちます。

ステップ1:$a$と$b$の公約数は、すべて$b$と$r$の公約数でもある

$d$を、$a$と$b$の公約数(つまり$d\mid a$かつ$d\mid b$を満たす正の整数)とします。このとき、$d\mid b$と補助事実Bより($k=q$として)、

$d\mid (bq)$

が成り立ちます。また、$d\mid a$と$d\mid(bq)$の両方が成り立っているので、補助事実Aより、

$d\mid \bigl(a-bq\bigr)$

が成り立ちます。ここで、$a=bq+r$ という関係式から、$a-bq=r$ です。したがって、

$d\mid r$

が成り立ちます。もともと$d\mid b$でもあったので、$d$は$b$と$r$の両方を割り切る、つまり$d$は$b$と$r$の公約数です。

以上より、「$a$と$b$の公約数」は、すべて「$b$と$r$の公約数」でもあることが示されました。

ステップ2:$b$と$r$の公約数は、すべて$a$と$b$の公約数でもある

今度は逆に、$d$を、$b$と$r$の公約数(つまり$d\mid b$かつ$d\mid r$を満たす正の整数)とします。このとき、$d\mid b$と補助事実Bより($k=q$として)、

$d\mid(bq)$

が成り立ちます。また、$d\mid(bq)$と$d\mid r$の両方が成り立っているので、補助事実Aより、

$d\mid\bigl(bq+r\bigr)$

が成り立ちます。ここで、$a=bq+r$ という関係式から、

$d\mid a$

が成り立ちます。もともと$d\mid b$でもあったので、$d$は$a$と$b$の両方を割り切る、つまり$d$は$a$と$b$の公約数です。

以上より、「$b$と$r$の公約数」は、すべて「$a$と$b$の公約数」でもあることが示されました。

ステップ3:2つの公約数の集合が完全に一致する

ステップ1では「$a,b$の公約数」の集合が「$b,r$の公約数」の集合に含まれることを示し、ステップ2ではその逆の含まれ方を示しました。両方向の含まれ方が成り立つということは、この2つの集合が完全に同じ集合であるということです。つまり、

$\{a\text{と}b\text{の公約数全体}\} = \{b\text{と}r\text{の公約数全体}\}$

が成り立ちます。

2つの集合が完全に一致しているならば、その中で最も大きい数(最大値)も当然一致します。「$a$と$b$の公約数全体」の中で最も大きいものは、定義より$\gcd(a,b)$であり、「$b$と$r$の公約数全体」の中で最も大きいものは、定義より$\gcd(b,r)$です。2つの集合が同じである以上、その最大値である$\gcd(a,b)$と$\gcd(b,r)$も等しくなります。

$\gcd(a,b) = \gcd(b,r)$

これで証明が完成しました。

検算

具体例で確かめます。$a=48$、$b=18$とします。$48$を$18$で割ると、商は$2$、余りは$48-18\times2=48-36=12$なので、$q=2$、$r=12$です。

$48$の正の約数は $1,2,3,4,6,8,12,16,24,48$、$18$の正の約数は $1,2,3,6,9,18$ なので、共通する約数は $1,2,3,6$ であり、$\gcd(48,18)=6$です。

一方、$18$の正の約数は $1,2,3,6,9,18$、$12$の正の約数は $1,2,3,4,6,12$ なので、共通する約数は $1,2,3,6$ であり、$\gcd(18,12)=6$です。

確かに $\gcd(48,18)=\gcd(18,12)=6$ となっており、証明した等式と一致しています。

この証明のポイント

「2つの数の組が等しいこと」を直接示すのが難しいとき、その代わりに「それぞれの数の組に対応する集合(ここでは公約数全体の集合)が完全に一致すること」を、2方向の包含関係(片方の集合の要素はもう片方の集合にも必ず属し、逆も成り立つ)に分けて示す、という証明の型は、整数の性質に関するさまざまな証明で応用できる考え方です。