04-02最大公約数と最小公倍数(難易度2)

自然数$a、b$の最大公約数が$28$、最小公倍数$840$となる$(a、b)$の組を全て求めよ
ただし、$a>b$とする

最小公倍数を最大公約数で割ると、何が残るのか考えてみよう

最大公約数が$28$のため$p、q(p>q)$を互いに素の整数として以下のように表すことができる。
$a=28p$
$b=28q$
また、最大公約数が$840$のため
 $28pq=840$
 $pq=30=2\cdot3\cdot5$
$p$と$q$は互いに素のため、$p$と$q$は以下の組み合わせになる
 $(1、2\cdot3\cdot5)、(2、3\cdot5)、(3、2\cdot5)、(5、2\cdot3)$
$p>q$より
 $(p、q)=(30,1)、(15、2)、(10、3)、(6、5)$

つまり
 $(a、b)=(840,28)、(420、48)、(280、84)、(168、140)$


それぞれの数を最大公約数で割ると、その商は互いに素になります。
商が互いに素にならないのであれば、そこに公約数があり、最大公約数ではなくなるからです。
この性質に気づくことができていたら解けると思います。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする