第1章: 整数の性質
約数・倍数と整除性
このページの目標
整数の基本的な性質を理解し、約数・倍数・整除性の概念を定義する。最大公約数・最小公倍数の求め方とそれらの関係を学ぶ。
1. 整数とは
整数（integer）とは、$\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$ のことである。
整数全体の集合を $\mathbb{Z}$ で表す。
数の分類
- 自然数 $\mathbb{N}$：$1, 2, 3, \ldots$（正の整数）
- 整数 $\mathbb{Z}$：$\ldots, -2, -1, 0, 1, 2, \ldots$
- 有理数 $\mathbb{Q}$：分数で表せる数（$\frac{p}{q}$, $p, q \in \mathbb{Z}$, $q \neq 0$）
包含関係：$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}$
2. 整除性（割り切れる関係）
整数 $a, b$ に対し、ある整数 $k$ が存在して $b = ka$ となるとき、
「$a$ は $b$ を割り切る」または「$b$ は $a$ で割り切れる」といい、
$$a \mid b$$と書く。このとき $a$ を $b$ の約数、$b$ を $a$ の倍数という。
- $3 \mid 12$ ✓（$12 = 3 \times 4$）
- $5 \mid 15$ ✓（$15 = 5 \times 3$）
- $4 \nmid 10$ ✗（$10$ は $4$ で割り切れない）
3. 整除の基本性質
整数 $a, b, c$ について以下が成り立つ：
- 反射律：$a \mid a$（任意の整数は自分自身を割り切る）
- 推移律：$a \mid b$ かつ $b \mid c$ ならば $a \mid c$
- 線形結合：$a \mid b$ かつ $a \mid c$ ならば $a \mid (bx + cy)$（任意の整数 $x, y$）
（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$。
$$bx + cy = kax + lay = a(kx + ly)$$$kx + ly$ は整数なので $a \mid (bx + cy)$。
4. 約数と倍数
正整数 $n$ の正の約数とは、$n$ を割り切る正整数のことである。
$12 = 1 \times 12 = 2 \times 6 = 3 \times 4$
したがって、12 の正の約数は $1, 2, 3, 4, 6, 12$ の6個。
5. 最大公約数（GCD）
2つ以上の正整数に共通する約数を公約数という。
公約数のうち最大のものを最大公約数（Greatest Common Divisor）といい、
$$\gcd(a, b) \text{ または } (a, b)$$と書く。
12の約数：$1, 2, 3, 4, 6, 12$
18の約数：$1, 2, 3, 6, 9, 18$
公約数：$1, 2, 3, 6$
最大公約数：$\gcd(12, 18) = 6$
3つ以上の最大公約数
3つ以上の整数の最大公約数は、2つずつ順に求めればよい：
$$\gcd(a, b, c) = \gcd(\gcd(a, b),\, c)$$これは任意個に一般化できる：
$$\gcd(a_1, a_2, \ldots, a_n) = \gcd(\gcd(a_1, \ldots, a_{n-1}),\, a_n)$$早期終了による高速化
途中で $\gcd = 1$ になったら、それ以降は計算不要である。任意の整数 $c$ に対して $\gcd(1, c) = 1$ だからである。
逐次計算：
- $\gcd(48, 60) = 12$
- $\gcd(12, 36) = 12$
よって $\gcd(48, 60, 36) = 12$。
$\gcd(7, 12, 100, 999)$ を求める。
- $\gcd(7, 12) = 1$ → ここで終了！
$\gcd = 1$ になった時点で、残りの $100, 999$ を調べるまでもなく答えは $1$。
6. 最小公倍数（LCM）
2つ以上の正整数に共通する倍数を公倍数という。
公倍数のうち最小の正のものを最小公倍数（Least Common Multiple）といい、
$$\mathrm{lcm}(a, b) \text{ または } [a, b]$$と書く。
正整数 $a, b$ について
$$\gcd(a, b) \times \mathrm{lcm}(a, b) = ab$$$d = \gcd(a, b)$ とおくと、$a = da'$, $b = db'$（$\gcd(a', b') = 1$）と書ける。
このとき $\mathrm{lcm}(a, b) = da'b'$ である（$a'$ と $b'$ は互いに素なので）。
したがって
$$\gcd(a, b) \times \mathrm{lcm}(a, b) = d \times da'b' = d^2a'b' = (da')(db') = ab$$$\mathrm{lcm}(12, 18) = \dfrac{12 \times 18}{6} = \dfrac{216}{6} = 36$
検算：$12, 24, 36, \ldots$ と $18, 36, \ldots$ の最小公倍数は確かに36 ✓
3つ以上の最小公倍数
GCD と同様に、LCM も2つずつ順に求めればよい：
$$\mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b),\, c)$$- $\mathrm{lcm}(4, 6) = 12$
- $\mathrm{lcm}(12, 10) = 60$
よって $\mathrm{lcm}(4, 6, 10) = 60$。
落とし穴：GCD × LCM = abc は3つ以上では成立しない
2つの場合は $\gcd(a, b) \times \mathrm{lcm}(a, b) = ab$ が成り立つが、3つ以上ではこの関係は成り立たない。
反例：$a = 2,\, b = 3,\, c = 6$ のとき
- $\gcd(2, 3, 6) \times \mathrm{lcm}(2, 3, 6) = 1 \times 6 = 6$
- $abc = 2 \times 3 \times 6 = 36$
$6 \neq 36$ なので不成立。したがって3つ以上の LCM を求めるときに
$\mathrm{lcm}(a, b, c) = \dfrac{abc}{\gcd(a, b, c)}$ としてはいけない。
正しくは逐次計算（$\mathrm{lcm}(\mathrm{lcm}(a,b),\, c)$）を使うこと。
7. 例題
$\gcd(48, 60)$ と $\mathrm{lcm}(48, 60)$ を求めよ。
解答
48の約数：$1, 2, 3, 4, 6, 8, 12, 16, 24, 48$
60の約数：$1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$
公約数：$1, 2, 3, 4, 6, 12$
$\gcd(48, 60) = 12$
$\mathrm{lcm}(48, 60) = \dfrac{48 \times 60}{12} = 240$
$a \mid b$ かつ $a \mid c$ のとき、$a \mid (2b - 3c)$ を証明せよ。
解答
$a \mid b$ より $b = ka$、$a \mid c$ より $c = la$（$k, l$ は整数）。
$$2b - 3c = 2ka - 3la = a(2k - 3l)$$$2k - 3l$ は整数なので $a \mid (2b - 3c)$。
まとめ
この章のポイント
- 整数 $\mathbb{Z}$：自然数を負の方向に拡張した数の集合
- 整除性：$a \mid b$ ⟺ ある整数 $k$ で $b = ka$
- 最大公約数：公約数の中で最大のもの
- 最小公倍数：公倍数の中で最小の正のもの
- GCDとLCMの関係：$\gcd(a,b) \times \mathrm{lcm}(a,b) = ab$