最大公約数と最小公倍数を掛けるとなぜ元の 2 数の積になるのか

$60$ と $72$ の最大公約数は $12$ 、最小公倍数は $360$ です。掛けると $4320$ になり、これは $60 \times 72$ とぴたり同じ。

偶然ではありません。素因数の指数を並べて眺めると、なぜそうなるかがそのまま見えます。

指数を並べて見る

$60 = 2^{2} \times 3 \times 5$ 、 $72 = 2^{3} \times 3^{2}$ です。 $72$ には $5$ が入っていないので、指数は $0$ と数えます。

最大公約数は、素因数ごとに指数の小さいほうをとって作ります。最小公倍数は大きいほうをとる^[1]。

$g cd (a, b) = p \prod p^{m i n (a_{p}, b_{p})}, lcm (a, b) = p \prod p^{m a x (a_{p}, b_{p})}$

$5$ の段を見ると、 $60$ に 1 個あって $72$ にはない。低いほうは $0$ なので、最大公約数に $5$ は入りません。

積が 2 数の積になる理由

素因数 1 つぶんで考えます。 $60$ の指数を $a$ 、 $72$ の指数を $b$ とすると、最大公約数の指数は $min (a, b)$ 、最小公倍数の指数は $max (a, b)$ 。

小さいほうと大きいほうを足せば、もとの 2 つを足したものに戻ります。

$min (a, b) + max (a, b) = a + b$

どの素因数でも指数の合計が保たれるので、掛け算に直すと次の等式になります^[1,2]。

$g cd (a, b) \times lcm (a, b) = ab$

例：24 と 36 で確かめる

$24 = 2^{3} \times 3$ 、 $36 = 2^{2} \times 3^{2}$ です。最大公約数は $2^{2} \times 3 = 12$ 、最小公倍数は $2^{3} \times 3^{2} = 72$ 。

$12 \times 72 = 864 = 24 \times 36$

一方が分かればもう一方が出ます。 $lcm = ab \div g cd$ という形で使うのがふつう。

例：3 つ以上では成り立たない

$2$ 、 $3$ 、 $4$ で試します。最大公約数は $1$ 、最小公倍数は $12$ で、掛けると $12$ 。

3 数の積は $24$ なので、一致しません。指数の振り分けが 2 つのときだけの話だからです。

$2$ 、 $2$ 、 $2$ ではもっとはっきりします。最大公約数も最小公倍数も $2$ で積は $4$ 、3 数の積は $8$ 。

この等式が使えるのはちょうど 2 数のときだけです。

3 数では $min$ と $max$ を足しても、真ん中の値が余る。指数の合計が保たれない。

互いに素という条件

共通の素因数がまったくないとき、2 数は互いに素といいます^[3]。最大公約数が $1$ になる状態です。

このとき $min$ はすべて $0$ なので、最小公倍数は 2 数の積そのもの。 $lcm (a, b) = ab$ になります。

$8$ と $15$ が例です。 $8 = 2^{3}$ 、 $15 = 3 \times 5$ で素因数が重ならず、最小公倍数は $120$ 。

互いに素

最大公約数が $1$ 。最小公倍数はそのまま積になる

共通の素因数がある

最大公約数が $2$ 以上。最小公倍数は積より小さくなる

最大公約数でくくる

$g = g cd (a, b)$ とし、 $a = g a^{'}$ 、 $b = g b^{'}$ と書きます。この $a^{'}$ と $b^{'}$ は必ず互いに素です^[3]。

共通の因数が残っていれば、それも $g$ に入っていたはず。 $g$ が最大だという条件から、残りかすは出ません。

このとき最小公倍数は $g a^{'} b^{'}$ になります。整数問題では、この形に置くところから始めるのが定石。

最大公約数を $g$ と置く

$a = g a^{'}$ 、 $b = g b^{'}$ と書く

$a^{'}$ と $b^{'}$ が互いに素という条件を使う

例：最大公約数 6、最小公倍数 72 の 2 数

$a = 6 a^{'}$ 、 $b = 6 b^{'}$ とすると、最小公倍数は $6 a^{'} b^{'} = 72$ なので $a^{'} b^{'} = 12$ 。

$a^{'}$ と $b^{'}$ は互いに素なので、 $12$ を共通因数なしに分ける必要があります。 $(1, 12)$ と $(3, 4)$ の 2 通り。

$(2, 6)$ は両方が $2$ で割れるので不可。したがって $(a, b)$ は $(6, 72)$ か $(18, 24)$ 、および順序を入れかえたものです。

例：和が 84 で最大公約数が 12 の 2 数

$a = 12 a^{'}$ 、 $b = 12 b^{'}$ と置くと $12 (a^{'} + b^{'}) = 84$ なので $a^{'} + b^{'} = 7$ 。

和が $7$ になる正の整数の組は $(1, 6)$ 、 $(2, 5)$ 、 $(3, 4)$ 。どれも互いに素なので、すべて条件をみたします。

$(a, b) = (12, 72)$ 、 $(24, 60)$ 、 $(36, 48)$ の 3 組。和を確かめると、どれも $84$ です。

例：最小公倍数から相手を決める

$lcm (n, 24) = 360$ をみたす正の整数 $n$ を全部求めます。 $24 = 2^{3} \times 3$ 、 $360 = 2^{3} \times 3^{2} \times 5$ 。

素因数ごとに $max$ の条件を書き下すのが早い。 $n$ に $2$ 、 $3$ 、 $5$ 以外の素因数は入れられません。

$2$ の指数は $max (x, 3) = 3$ から $0 \leq x \leq 3$ の 4 通り。 $3$ の指数は $max (y, 1) = 2$ から $y = 2$ に決まります。

$5$ の指数は $max (z, 0) = 1$ なので $z = 1$ 。よって $n = 2^{x} \times 3^{2} \times 5$ で、 $45$ 、 $90$ 、 $180$ 、 $360$ の 4 つ。

$lcm (45, 24)$ を確かめると $360$ 。ほかの 3 つも同じ値になります。

例：どちらに掛けても自然数になる分数

$\frac{35}{6}$ と $\frac{21}{10}$ のどちらに掛けても自然数になる分数のうち、最小の正のものを求めます。

求める分数を $\frac{q}{p}$ （既約）とすると、分子 $q$ は $6$ と $10$ の公倍数、分母 $p$ は $35$ と $21$ の公約数でなければなりません。

最小にしたいので、 $q$ は最小公倍数 $30$ 、 $p$ は最大公約数 $7$ 。答えは $\frac{30}{7}$ です。

$\frac{35}{6} \times \frac{30}{7} = 25, \frac{21}{10} \times \frac{30}{7} = 9$

分子は最小公倍数、分母は最大公約数。この対応を覚えておくと、同じ形の問題は数行で終わります。

検算

答えが出たら $g cd \times lcm = ab$ に戻して確かめます。 $(18, 24)$ なら $g cd = 6$ 、 $lcm = 72$ 。

$6 \times 72 = 432$ で、 $18 \times 24 = 432$ 。一致したので、最大公約数と最小公倍数の組み合わせに矛盾はありません。

逆に、この積が合わない答えは必ずどこかが誤りです。書き出す前の足切りに使えます。

$g cd (a, b) = 8$ 、 $lcm (a, b) = 96$ をみたす正の整数の組 $(a, b)$ は何組ありますか。順序が違うものは別の組と数えます。

2 組
4 組
6 組

__RESULT__

$a = 8 a^{'}$ 、 $b = 8 b^{'}$ と置くと $8 a^{'} b^{'} = 96$ から $a^{'} b^{'} = 12$ 。互いに素な組は $(1, 12)$ 、 $(3, 4)$ とその入れかえで 4 組です。 $(2, 6)$ は互いに素でないので数えません。

素因数ごとの指数に落として $min$ と $max$ を見る。この見方に慣れると、公式を覚え直さなくても組み立て直せます。

出典

Least common multiple - Wikipedia

Kleinstes gemeinsames Vielfaches - Wikipedia

Coprime integers - Wikipedia

$60 = 2^2 \times 3 \times 5$、$72 = 2^3 \times 3^2$ と並べると、最大公約数は指数の低いほう、最小公倍数は高いほうを集めた数になる。低いほうと高いほうを足せばもとの 2 つに戻るので、掛け算に直すと $\gcd \times \mathrm{lcm} = ab$ です。3 数で崩れる理由も同じところ。$a = ga'$ と置く定石、最大公約数 6 で最小公倍数 72 の 2 数、$\mathrm{lcm}(n, 24) = 360$ をみたす $n$ が 4 つ出る話、分子が最小公倍数で分母が最大公約数になる分数の問題まで扱いました。