文献あり

初等整数論講義 - §2 - 最大公約数, 最小公倍数

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

まず、用語を整理しておきます。

$a$ が $b$ で割り切れるとき、「 $a$ は $b$ の倍数」、あるいは、「 $b$ は $a$ の約数」といいます。
$n$ が $a, b, c, \dots$ で割り切れるとき、「 $n$ は $a, b, c, \dots$ の公倍数」といいます。
$a, b, c, \dots$ が $n$ で割り切れるとき、「 $n$ は $a, b, c, \dots$ の公約数」といいます。
公約数の中で最大のものを最大公約数、正の公倍数の中で最小のものを最小公倍数といいます。

二つ以上の整数の公倍数は最小公倍数の倍数である

$l$ を $a, b, c, \dots$ の最小公倍数、 $m$ を $a, b, c, \dots$ の任意の公倍数とする。
$m = q l + r, 0 \leq r < l$
と表すと、 $r = m - q l$ である。 $m$ も $q l$ も $a$ の倍数なので $r$ は $a$ の倍数。これを $b, c, \dots$ にも適用して、 $r$ が $a, b, c, \dots$ の公倍数であることがわかる。ここで、 $0 \leq r < l$ だったので、 $r = 0$ 。よって、 $m = q l$ であり、公倍数は最小公倍数の倍数であることが分かる。

二つ以上の整数の公約数は最大公約数の約数である

$m$ を $a, b, c, \dots$ の最大公約数、 $d$ を $a, b, c, \dots$ の任意の公約数とする。
背理法で証明する。つまり、 $m$ が $d$ で割り切れないとする。これは $m = d q + r$ と書ける（ $1 \leq r < | d |$ ）。
$a = m a^{'} = d a^{″}$
$b = m b^{'} = d b^{″}$
$\dots$
とおく。ここで、 $a^{'}, b^{'}, c^{'}, \dots$ のすべてが $\pm 1$ でない $d$ のある約数（これを $α$ と書くことにする）で割り切れるとすれば、 $| m α |$ の方が $m$ よりも大きい公約数になるので矛盾。よって $m = d q + r$ は $d$ の倍数。ゆえに、 $r$ は $d$ の倍数であるが、 $1 \leq r < d$ であることに矛盾。
よって背理法より、 $d$ は $m$ の約数である。

$a, b$ の最小公倍数を $l$ 、最大公約数を $m$ とすれば、
$a b = l m$
が成り立つ（ $a > 0, b > 0$ とする）

定理1より、 $a b$ は $l$ の倍数なので $a b = d l$ とかける。
$l$ は $a, b$ の公倍数なので、 $l = a x = b y$ とかける。 $a b = d l$ に代入して、 $b = d x, a = d y$ である。よって $d$ は $a, b$ の公約数である。
よって定理2より $m = d e$ とかける。ここで、 $m$ は $a$ と $b$ の公約数なので、 $b = d x, a = d y$ より、 $e$ は $x$ と $y$ の公約数である。よって、 $x = e x^{'}, y = e y^{'}$ として $l = a x = b y$ に代入すると、 $l = e a x^{'} = e b y^{'}$ 。もしも $e > 1$ なら、 $l / e < l$ が $a, b$ の公倍数になるが、これは矛盾。よって $e = 1$ 。ゆえに $a b = l m$ が成り立つ。

$a, b, c, \dots$ の最大公約数を $(a, b, c, \dots)$ という記号で書き表すことにします。

$(a, b) = 1$ のとき、 $a, b$ を互いに素と言います。

$a, b$ が互いに素で、かつ $b c$ が $a$ の倍数ならば、 $c$ は $a$ の倍数である。

定理3を使うと、 $(a, b) = 1$ より、 $a, b$ の最小公倍数は $a b$ である。
今、 $b c$ は $a$ の倍数なので $b c$ は $a, b$ の公倍数。よって $b c$ は $a b$ の倍数。ゆえに $b c / a b = c / a$ は整数で、 $c$ が $a$ で割り切れることが分かった。