第1章: 整数の性質

（1の証明）

$a = 1 \cdot a$ より $a \mid a$。

（※ $a = 0$ の場合：$0 = k \cdot 0$ は任意の整数 $k$ で成立するので、定義に従えば $0 \mid 0$ は真である。ただし教科書によっては $0 \mid 0$ を定義しない、または別扱いとするものもある。初学者はまず $a \neq 0$ の場合を主に考えればよい。）

（2の証明）

$a \mid b$ より $b = ka$（ある整数 $k$）。

$b \mid c$ より $c = lb$（ある整数 $l$）。

したがって $c = lb = l(ka) = (lk)a$。

$lk$ は整数なので $a \mid c$。

（3の証明）

$a \mid b$ より $b = ka$、$a \mid c$ より $c = la$。

$kx + ly$ は整数なので $a \mid (bx + cy)$。

証明

$d = \gcd(a, b, c)$、$g = \gcd(a, b)$、$d' = \gcd(g, c)$ とおく。$d = d'$ を示す。

($d \mid d'$ の証明)

$d = \gcd(a, b, c)$ であるから $d \mid a$ かつ $d \mid b$ である。 $d$ は $a$ と $b$ の公約数なので、最大公約数 $g = \gcd(a, b)$ の定義から $d \mid g$。 また $d \mid c$ でもある。よって $d$ は $g$ と $c$ の公約数であり、$d' = \gcd(g, c)$ の定義から $d \mid d'$。

($d' \mid d$ の証明)

$d' = \gcd(g, c)$ であるから $d' \mid g$ かつ $d' \mid c$ である。 $g = \gcd(a, b)$ であるから $g \mid a$ かつ $g \mid b$。 $d' \mid g$ と合わせて $d' \mid a$ かつ $d' \mid b$。また $d' \mid c$ でもある。 よって $d'$ は $a, b, c$ の公約数であり、$d = \gcd(a, b, c)$ の定義から $d' \mid d$。

$d \mid d'$ かつ $d' \mid d$ であり、$d, d' > 0$ なので $d = d'$。 $\blacksquare$

$d = \gcd(a, b)$ とおくと、$a = da'$, $b = db'$（$\gcd(a', b') = 1$）と書ける。

$da'b'$ は $a = da'$ の倍数（$da'b' = a \cdot b'$）かつ $b = db'$ の倍数（$da'b' = b \cdot a'$）なので公倍数である。 $a'$ と $b'$ は互いに素なので、$a$ と $b$ の任意の公倍数は $da'b'$ の倍数となり、$\mathrm{lcm}(a, b) = da'b'$ が従う。

したがって

証明

$L = \mathrm{lcm}(a, b, c)$、$m = \mathrm{lcm}(a, b)$、$L' = \mathrm{lcm}(m, c)$ とおく。$L = L'$ を示す。

($L' \mid L$ の証明)

$L$ は $a, b, c$ の公倍数なので $a \mid L$ かつ $b \mid L$ である。 $m = \mathrm{lcm}(a, b)$ は $a, b$ の公倍数の中で最小であるから $m \mid L$。 また $c \mid L$ でもある。よって $L$ は $m$ と $c$ の公倍数であり、$L' = \mathrm{lcm}(m, c)$ の定義から $L' \mid L$。

($L \mid L'$ の証明)

$m = \mathrm{lcm}(a, b)$ であるから $a \mid m$ かつ $b \mid m$ である。 $m \mid L'$ なので $a \mid L'$ かつ $b \mid L'$。また $c \mid L'$ でもある。 よって $L'$ は $a, b, c$ の公倍数であり、$L = \mathrm{lcm}(a, b, c)$ の定義から $L \mid L'$。

$L' \mid L$ かつ $L \mid L'$ であり、$L, L' > 0$ なので $L = L'$。 $\blacksquare$