最大公約数

$a\neq0$ としてよい。$d\mid a$ なら $a=dk$ で $k\neq0$ なので $|d|\le|d||k|=|a|$ であり、$a$ の約数は $-|a|$ 以上 $|a|$ 以下の有限個である。$1$ はすべての整数を割り切るので、公約数全体は $1$ を含む空でない有限集合であり、最大元がただ 1 つある。それは $1$ 以上である。$d\mid a$ と $d\mid-a$ は同値なので公約数全体は $a,b$ の符号によらず、順序を入れ替えても変わらない。$0$ はすべての $d$ で $0=d\cdot0$ と割り切られるので、$a$ と $0$ の公約数は $a$ の約数そのものであり、その最大は $|a|$ である。$1$ の約数は $\pm1$ だけなので $\gcd(a,1)=1$ である。$\square$

$a=b=0$ なら $d=0$ であり、公約数全体も $0$ の約数全体もすべての整数である。以下 $a,b$ の少なくとも一方は $0$ でないとする。Bézoutの等式 の記事の定理「Bézoutの等式」の 1 により $d=ax+by$ となる整数 $x,y$ がある。$c$ が $a,b$ の公約数なら $c$ は $ax+by=d$ を割り切る。逆に $d$ の約数は、$d\mid a$、$d\mid b$ により $a,b$ の公約数である。
一意性を示す。$0$ 以上の整数 $d'$ も同じ性質をもつとすると、$d'$ は公約数なので $d'\mid d$、$d$ は公約数なので $d\mid d'$ である。$d=0$ なら $d\mid d'$ から $d'=0$ である。$d>0$ なら $d'\neq0$ であり、互いに割り切ることから $|d|\le|d'|\le|d|$、$d,d'\ge0$ なので $d=d'$ である。$\square$

1. $e\mid a$、$e\mid b$ なら $e\mid a-qb$ であり、逆に $e\mid a-qb$、$e\mid b$ なら $e\mid(a-qb)+qb=a$ である。公約数全体が一致するので、thm-gcd-divisibility の一意性（公約数全体を約数全体とする $0$ 以上の整数は 1 つ）により最大公約数も一致する。
2. $m=0$ または $a=b=0$ なら両辺とも $0$ である。そうでないとき $d:=\gcd(a,b)$、$e:=\gcd(ma,mb)$ とおく。$|m|d$ は $ma$ と $mb$ を割り切るので、thm-gcd-divisibility により $|m|d\mid e$ である。一方 Bézoutの等式 により $d=ax+by$ と書け、$md=(ma)x+(mb)y$ なので $e\mid md$ である。$e$ と $|m|d$ は互いに割り切り合う正の整数なので等しい。
3. 2 を $m=d$、$(a/d,b/d)$ に使うと $d=\gcd(a,b)=d\cdot\gcd(a/d,b/d)$ であり、$d>0$ なので $\gcd(a/d,b/d)=1$ である。
4. thm-gcd-divisibility により、「$e\mid a$ かつ $e\mid b$」は「$e\mid\gcd(a,b)$」と同値である。したがって $a,b,c$ の公約数全体と、$\gcd(a,b)$ と $c$ の公約数全体は一致し、最大公約数も一致する（すべてが $0$ の場合は両辺とも $0$ と約束する）。$\square$

1. $\delta_p\le\alpha_p$ がすべての $p$ で成り立てば、$k:=\prod_pp^{\alpha_p-\delta_p}$ は正の整数で $a=dk$ である。逆に $a=dk$（$k$ は正の整数）とし、$k=\prod_pp^{\kappa_p}$ と書くと、$dk=\prod_pp^{\delta_p+\kappa_p}$ は $a$ の素因数分解でもあるので、分解の一意性から $\alpha_p=\delta_p+\kappa_p\ge\delta_p$ である。
2. $g:=\prod_pp^{\min(\alpha_p,\beta_p)}$ とおく。1 により $g$ は $a$ と $b$ を割り切る。$d$ が $a,b$ の正の公約数なら、1 により $\delta_p\le\alpha_p$ かつ $\delta_p\le\beta_p$、すなわち $\delta_p\le\min(\alpha_p,\beta_p)$ なので、再び 1 により $d\mid g$、特に $d\le g$ である。よって $g$ は正の公約数のうち最大であり $g=\gcd(a,b)$ である。
   同様に $L:=\prod_pp^{\max(\alpha_p,\beta_p)}$ とおくと、1 により $a\mid L$、$b\mid L$ である。$M=\prod_pp^{\mu_p}$ が $a,b$ の正の公倍数なら、1 により $\alpha_p\le\mu_p$ かつ $\beta_p\le\mu_p$ なので $\max(\alpha_p,\beta_p)\le\mu_p$、再び 1 により $L\mid M$、特に $L\le M$ である。よって $L=\operatorname{lcm}(a,b)$ である。
3. 2 の証明で、正の公倍数 $M$ は $L$ で割り切れることを示した。負の公倍数 $M$ については $-M$ に適用し、$0$ は $L$ の倍数である。逆に $L$ の倍数は $a,b$ の公倍数である。$\square$

$a=0$ または $b=0$ なら、約束により $\operatorname{lcm}(a,b)=0$ で両辺とも $0$ である。$a,b\neq0$ のとき、$\gcd$ と $\operatorname{lcm}$ は符号によらないので $a,b>0$ としてよい。thm-gcd-factorization の 2 と、実数 $x,y$ について $\min(x,y)+\max(x,y)=x+y$ であることから
$$ \gcd(a,b)\operatorname{lcm}(a,b)=\prod_pp^{\min(\alpha_p,\beta_p)+\max(\alpha_p,\beta_p)}=\prod_pp^{\alpha_p+\beta_p}=ab $$
である。$\square$

$a,b,c>0$ としてよい。素数 $p$ ごとに指数を比べると、$a,b,c$ の $p$ の指数を $x,y,z$ として
$$ \max(x,y,z)+\min(x,y)+\min(y,z)+\min(z,x)=x+y+z+\min(x,y,z) $$
を示せばよい。両辺は $x,y,z$ の入れ替えで変わらないので $x\le y\le z$ としてよく、このとき左辺は $z+x+y+x$、右辺は $x+y+z+x$ で等しい。$\square$

存在：$r=a/b$、$b>0$ と書く（$b<0$ なら分子と分母に $-1$ を掛ける）。$b\neq0$ なので $d=\gcd(a,b)\ge1$ であり、$p=a/d$、$q=b/d\ge1$ は整数で $p/q=a/b$、prop-gcd-rules の 3 により $\gcd(p,q)=1$ である。
一意性：$p/q=p'/q'$ で $q,q'\ge1$、$\gcd(p,q)=\gcd(p',q')=1$ とすると $pq'=p'q$ である。$q$ は $pq'$ を割り切り、$p$ と互いに素なので $q\mid q'$ である（互いに素 の記事の命題「互いに素な因子の消去」）。同様に $q'\mid q$ であり、どちらも正なので $q=q'$、したがって $p=p'$ である。$\square$