最大公約数と最小公倍数から2数を求める

方針

解答

⓪ 発想 — どう考え始めるか。 最大公約数が $12$ なら、$a=12a^{\prime }$、$b=12b^{\prime }$($a^{\prime },b^{\prime }$ は互いに素)と書ける。この形にするのが第一歩。

最小公倍数は、互いに素な $a^{\prime },b^{\prime }$ を使うと $\mathrm{lcm}=12a^{\prime }{b}^{\prime }$。これが $720$ だから $a^{\prime }{b}^{\prime }=60$。

あとは「互いに素で積が $60$ の組 $(a^{\prime },b^{\prime })$」($a^{\prime }\le b^{\prime }$)を挙げる。$60=2^2\cdot 3\cdot 5$ の素因数を $2$ グループに分けて互いに素にすると $(1,60),(3,20),(4,15),(5,12)$ の $4$ 組。それぞれ $12$ 倍する。

① 商の積を求める。 $a=12a^{\prime },b=12b^{\prime }$($a^{\prime },b^{\prime }$ 互いに素、$a^{\prime }\le b^{\prime }$)とおく。最小公倍数は $12a^{\prime }{b}^{\prime }=720$ だから

$$a^{\prime }{b}^{\prime }=60$$

② 互いに素な組を挙げる。 積が $60$ で互いに素な $(a^{\prime },b^{\prime })$($a^{\prime }\le b^{\prime }$):

• $(1,60)$、$(3,20)$、$(4,15)$、$(5,12)$

($(2,30)$ は $\gcd =2$、$(6,10)$ は $\gcd =2$ で互いに素でないから除く。)

③ $12$ 倍して戻す。

$$(a,b)=(12,720),(36,240),(48,180),(60,144)$$

まとめ:最大公約数の情報は「$a=g{a}^{\prime },b=g{b}^{\prime }$、$a^{\prime },b^{\prime }$ 互いに素」に翻訳。最小公倍数は $g{a}^{\prime }{b}^{\prime }$ なので商の積が決まり、あとは互いに素な因数分解を数える。$\gcd$ が消える組($(2,30)$ 等)を除くのがポイント。

発展 — 一歩先へ。 $\gcd (a,b)\times \mathrm{lcm}(a,b)=ab$ は、素因数ごとに「指数の $\min +\max =$ 両方の和」から出る基本公式。$a=12a^{\prime },b=12b^{\prime }$($a^{\prime },b^{\prime }$ 互いに素)と分けると、互いに素な数の積が最小公倍数になる。$\gcd$ と $\mathrm{lcm}$ を与えて $2$ 数を復元する問題は、この分解がすべての鍵だ。

別解

別解 — 積 $ab=\gcd \times \mathrm{lcm}$ を使って絞る(得意な人向けの視点)。 $2$ 数の「最大公約数 $\times$ 最小公倍数 $=$ $2$ 数の積」という公式を使う。

$$ab=\gcd (a,b)\times \mathrm{lcm}(a,b)=12\times 720=8640.$$

さらに $a=12a^{\prime }$、$b=12b^{\prime }$ とすると $ab=144a^{\prime }{b}^{\prime }=8640$ より $a^{\prime }{b}^{\prime }=60$。互いに素($\gcd (a^{\prime },b^{\prime })=1$)で積 $60$ の組を探す。

$60=2^2\cdot 3\cdot 5$ の素因数を、$2$ つのグループに「まるごと」振り分ける(互いに素にするには、同じ素数を両方に分けられない)。素因数のかたまり $\{4\},\{3\},\{5\}$ を $2$ グループに分ける方法で

$$(a^{\prime },b^{\prime })=(1,60),(3,20),(4,15),(5,12).$$

($a^{\prime }\le b^{\prime }$。$4$ 組。)$12$ 倍して $(12,720),(36,240),(48,180),(60,144)$。

$\mathrm{lcm}=12a^{\prime }{b}^{\prime }$ を使う本解と同じだが、$ab=\gcd \times \mathrm{lcm}$ を使うと積 $8640$ から一気に $a^{\prime }{b}^{\prime }=60$ が出る。素因数を「かたまりで」振り分けるのが、互いに素にする条件の本質だ。