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

方針

解答

⓪ 発想 — どう考え始めるか。 最大公約数が $6$ という情報は、2数の「形」を教えてくれる。2数は $6a$、$6b$($a$、$b$ は互いに素)と書ける。

すると最小公倍数は $6ab$。これが $180$ だから $ab=30$。

あとは、積が $30$ になる互いに素な組 $(a,b)$ を探すだけだ。「互いに素」の条件を忘れずに、順序を決めて($a\le b$)数えれば重複しない。

最大公約数が $6$ なので、$2$ 数は $6a$、$6b$ とおける。ここで $a$ と $b$ は互いに素($1$ 以外の共通約数を持たない)。もし共通約数があれば、最大公約数が $6$ より大きくなってしまうからだ。

このとき、最小公倍数は $6ab$ になる。条件より

$$6ab=180\text{よって}ab=30$$

$a\le b$、$a$ と $b$ は互いに素、$ab=30$ を満たす組を探す。$30$ を $2$ つの積に分けると $(1,30),(2,15),(3,10),(5,6)$ で、どれも互いに素だ。それぞれを $6$ 倍して

$$(6,180),(12,90),(18,60),(30,36)$$

(注意:$a$ と $b$ が互いに素であることが必要。$ab=30$ でも共通因数があれば最大公約数が $6$ からずれる。今回の $4$ 組はすべて互いに素なので、これで尽くされている。)

発展 — 一歩先へ。 積の保存則 $\gcd \times \mathrm{lcm}=mn$ は、素因数の指数で見ると「min + max = 足し算」という当たり前の事実になる。各素数の指数について、gcd は小さい方、lcm は大きい方を取るからだ。

ただしこの保存則は2数限定で、3数では崩れる。指数の min と max だけでは真ん中の情報が消えるからだ。便利な公式ほど、適用範囲の境界を知っておく価値がある。

別解

検算の道具として、「積の保存則」を持っておくと強い。

2つの自然数について、いつでも

$$(\text{最大公約数})\times (\text{最小公倍数})=(\text{2数の積})$$

が成り立つ。今回なら2数の積は必ず $6\times 180=1080$ になるはずだ。

答えの4組を検分すると、$6\times 180=1080$、$12\times 90=1080$、$18\times 60=1080$、$30\times 36=1080$。すべて合格で、安心して提出できる。

この保存則が成り立つ理由も、$6a\times 6b=6\times 6ab=(\text{gcd})\times (\text{lcm})$ と、本解の形からすぐ出る。逆に、積 $1080$ を先に出して「積が1080で最大公約数が6の組」を探す攻め方もできる。