アルゴリズム論特論（塩田）第2回 (2) 最大公約数と最小公倍数
最大公約数・最小公倍数の定義
まずは $0$ についての注意から。
Rem.1
- $0$ は全ての整数の倍数 ( $a \times 0 = 0$ ゆえ )
- 任意の整数は $0$ の約数
$0$ との整除関係は日頃あまり意識しませんが、このように考えます。次は記号の定義
Def.2 (1) $a$, $b$ の共通の約数のうち最大の数を最大公約数と言い、$\gcd(a,b)$ と表す。
(2) $a$, $b$ の共通の倍数のうち、正で最小の数を最小公倍数と言い、$\mbox{lcm}(a,b)$ と表す。
ただし
- $\gcd(a, b)$ は必ず 0 以上に定めます。
- 片方が 0 のときは $\gcd(a, 0)=|\,a\,|$ となります。( Rem.1 より $|\,a\,|$ も $0$ の約数ゆえ。)
- 両方が 0 のときは $\gcd(0, 0)=0$ と定めます。
( Rem.1 から任意の整数が $0$ の約数なので、$\infty$ となりそうに思いますが、こう約束すると後述の Th.6 が例外なく成立します。)
- $\mbox{lcm}$ も両方が 0 のときは $\mbox{lcm}(0, 0)=0$ と定めます。
また、それぞれ何の略かと言うと
- gcd = greatest common divisor
- lcm = least common multiple
です。
Ex. $\gcd(-12, -21)=3$, $\gcd(0, -5) = 5$.
最大公約数・最小公倍数の整除関係
最大公約数・最小公倍数は、公約数や公倍数の中の
大小関係で定義しますが、次のように、
他の公約数・公倍数との間に
整除関係を持つのが面白いところです。
Th.3 $a$, $b$ の任意の公倍数は $\mbox{lcm}(a,b)$ の倍数。
証明 $x$ を $a$, $b$ の任意の公倍数、$c=\mbox{lcm}(a,b)$ とします。
$x$ を $c$ で割って
$x = cq+r \qquad ( 0 \leqq r \lt c)$
とすると、
$r = x -cq$
であり、$x$ も $c$ も $a$, $b$ の公倍数ですから、$r$ も $a$, $b$ の公倍数となります。
もし $r \gt 0$ なら $c$ が最小の公倍数であることに反しますから $r=0$.
よって $x=cq$ は $c$ の倍数になります。(証明終)
Th.4 $a$, $b$ の任意の公約数は $\gcd(a,b)$ の約数。
証明 $x$ を $a$, $b$ の任意の公約数とし、
$d=\gcd(a,b)$, $y=\mbox{lcm}(x,d)$
とします。
- $x$ も $d$ も $a$, $b$ の公約数
- $\Rightarrow$ $a$ も $b$ も $x$, $d$ の公倍数
- $\Rightarrow$ $a$ も $b$ も $y$ の倍数 ( Th.3 より )
- $\Rightarrow$ $y$ は $a$, $b$ の公約数
- $\Rightarrow$ $y \leqq d$
他方、$y=\mbox{lcm}(x,d)$ は $d$ の倍数ですから $y \geqq d$ です。
$y \leqq d$ かつ $y \geqq d$ から $y=d$ となり、
すると $d=\mbox{lcm}(x,d)$ が成り立つので $x$ は $d$ の約数となります。
(証明終)