最大公約数と最小公倍数を掛けるとなぜ元の 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]。

$$\gcd (a,b)=\prod _p{p}^{\min (a_p,b_p)},\mathrm{lcm}(a,b)=\prod _p{p}^{\max (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]。

$$\gcd (a,b)\times \mathrm{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$$

一方が分かればもう一方が出ます。$\mathrm{lcm}=ab÷\gcd$ という形で使うのがふつう。

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

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

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

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

互いに素という条件

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

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

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

最大公約数でくくる

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

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

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

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

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

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

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

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

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

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

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

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

$\mathrm{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\le x\le 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 つ。

$\mathrm{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$$

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

検算

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

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

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

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

出典