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

方針

解答

⓪ 発想 — どう考え始めるか。 最大公約数が $12$ という情報を、まず使いやすい形に翻訳する。

$2$ 数を $12a$、$12b$($a$、$b$ は互いに素)と置くのが定跡だ。すると和の条件が $a+b=15$ という小さな式に縮む。

あとは「和が $15$ で互いに素な組」の有限リストを吟味するだけになる。

大きな数の問題を、互いに素な小さい数の世界へ写す。この流れを自力で通せるかが問われる。

最大公約数が $12$ なので、$2$ 数は $12a$、$12b$ とおける($a$、$b$ は互いに素)。和の条件より

$$12(a+b)=180\text{よって}a+b=15$$

$a\le b$、$a+b=15$、$a$ と $b$ は互いに素、という組を探す。

$a+b=15$ の組:$(1,14),(2,13),(3,12),(4,11),(5,10),(6,9),(7,8)$。このうち互いに素でないものを除く — $(3,12)$ は $\gcd =3$、$(5,10)$ は $\gcd =5$、$(6,9)$ は $\gcd =3$ なので除外。残るのは

$$(1,14),(2,13),(4,11),(7,8)$$

それぞれ $12$ 倍して

$$(12,168),(24,156),(48,132),(84,96)$$

(和が一定のときは、互いに素かどうかの選別が必要。最大公約数がちょうど $12$ になるのは、$a$、$b$ が互いに素なときだけだ。)

発展 — 一歩先へ。 和と最大公約数から $2$ 数を復元できるのは、$\gcd (a,b)=\gcd (a,a+b)$ という性質のおかげだ。

和 $a+b$ を固定すると、互いに素という条件は「$a$ が和と互いに素」という条件に化ける。だから候補が一気に絞れる。

最大公約数や最小公倍数と、和や積を組み合わせて $2$ 数を求める問題は、この「互いに素な組へ分解する」翻訳がいつでも出発点になる。

別解

別解 — 「和と互いに素」に読みかえる(得意な人向けの視点)。 $12a$、$12b$ と置き、$a+b=15$、$a\le b$ とするところまで本解と同じ。ここから互いに素の判定を速める。

$\gcd (a,b)$ は $\gcd (a,a+b)=\gcd (a,15)$ に等しい(片方から和を引いても最大公約数は変わらない)。つまり $a$ と $b$ が互いに素であることは、$a$ が $15$ と互いに素であることと同じ意味になる。

$15=3\times 5$ だから、$a$ が $3$ でも $5$ でも割り切れなければよい。$a\le b$ より $a$ は $1$ から $7$ の範囲。

• $a=3,5,6$ は $3$ か $5$ の倍数なので除く。
• 残る $a=1,2,4,7$ が条件を満たす。

対応する組 $(1,14),(2,13),(4,11),(7,8)$ を $12$ 倍して

$$(12,168),(24,156),(48,132),(84,96).$$

一つずつ最大公約数を確かめなくても、$a$ と $15$ の関係だけで選別できた。本解と同じ答えに至る。