最大公約数・最小公倍数とユークリッドの互除法

$a$ から $b$ の倍数を引いても、$b$ との公約数が増えたり減ったりすることはない:$a$ と $b$ の両方を割り切る数は残り $r=a-bq$ も割り切らねばならず、逆もまた成り立つ。

ステップ1（公約数の集合の一致）。$d$ を $a$ と $b$ の両方を割り切る任意の整数とし、整数 $x,y$ によって $a=dx$、$b=dy$ と書く。すると $r=a-bq=dx-dyq=d(x-yq)$ より $d\mid r$ となり、$d$ は $b$ と $r$ の両方を割り切る。逆に $d$ が $b$ と $r$ の両方を割り切り、$b=dy$、$r=dz$ と書けるなら、$a=bq+r=dyq+dz=d(yq+z)$ より $d\mid a$ となり、$d$ は $a$ と $b$ の両方を割り切る。

ステップ2（最大公約数の一致）。組 $(a,b)$ と $(b,r)$ はまったく同じ公約数の集合を持つので、その最大元も一致する:$\gcd(a,b)=\gcd(b,r)$。

ステップ3（有限回での停止）。各除法ステップの余りは $0\le r<b$ を満たすので、二つ目の数の列 $b > r_1 > r_2 > \cdots \ge 0$ は非負整数の狭義単調減少列である。このような列は高々 $b$ ステップで $0$ に達する;$\gcd(r_{k-1},r_k)=\gcd(r_k,0)=r_k$ の段階で、最後のゼロでない余り $r_k$ が $\gcd(a,b)$ となる。

各素数 $p$ について、$\gcd(a,b)$ は $a,b$ における $p$ の指数の小さい方を取り、$\operatorname{lcm}(a,b)$ は大きい方を取る;二つの数の小さい方と大きい方を足せば、常に元の二つの数の和になる。

ステップ1. すべての素数 $p$ にわたって $a$ と $b$ の素因数分解を $a=\prod_p p^{e_p}$、$b=\prod_p p^{f_p}$ と書く（$e_p,f_p\ge0$ で、ゼロでない指数は有限個のみ）。

ステップ2. 正の整数 $d=\prod_p p^{c_p}$ が $a$ と $b$ の両方を割り切るのは、すべての $p$ で $c_p\le e_p$ かつ $c_p\le f_p$ のとき、かつそのときに限るので、最大の約数は $c_p=\min(e_p,f_p)$ を選ぶ:$\gcd(a,b)=\prod_p p^{\min(e_p,f_p)}$。公倍数に対する双対の議論により、両方以上の最小の指数を選んで $\operatorname{lcm}(a,b)=\prod_p p^{\max(e_p,f_p)}$ を得る。

ステップ3. 任意の二つの実数に対して $\min(e_p,f_p)+\max(e_p,f_p)=e_p+f_p$ が成り立つ。したがって二つの積を素数ごとに掛け合わせると、$\gcd(a,b)\cdot\operatorname{lcm}(a,b)=\prod_p p^{\min(e_p,f_p)+\max(e_p,f_p)}=\prod_p p^{e_p+f_p}=\left(\prod_p p^{e_p}\right)\left(\prod_p p^{f_p}\right)=ab$ となる。