最大公約数と最小公倍数の話

最大公約数と最小公倍数についてのお話です。

次を読んで当たり前と思うでしょうか。

正の整数との最大公約数をとし，，となるように，を定める（，は互いに素な正の整数）。このとき，との最小公倍数はと表せる。

素因数分解をイメージして，共通する素因数を集めたものがで，残っている素因数には共通するものがなく，公倍数にするために足りない数を補うために残っている素因数，すなわち，をかければよい。・・・ですが，こういうフワフワした話は伝わる人と伝わらない人がいます。私はフワフワした話が好きで度々するのですが，経験上伝わらないことの方が多いです。そういうときは，実際に数字を使って見せると納得してもらえることが多いです。

授業で説明する場合は数字を使って納得してもらいますが，ここでは問題を解く訓練としてあえて証明をしてみます。最小公倍数とは，公倍数のうちで最小のものをいうのでした。は，の倍数になっているので，との公倍数になっています。最小であるかどうかが問題です。背理法で示してみます。

証明　が最小の公倍数でないと仮定すると，真の最小公倍数が存在し，最小公倍数以外の公倍数は最小公倍数の倍数だからとおける（は2以上の整数）。はとの公倍数だから

，

とおける（は正の整数）。を代入して整理すると

，

，

よって，はいずれもの倍数であるが，これは，が互いに素であることに反する。よって，は最小公倍数である。

別の証明

最小公倍数がであることを忘れて，初めから最小公倍数を求める方針が次の証明です。

証明　との公倍数とすると，公倍数はとの倍数だからとおける（は正の整数）。よりの右辺はの倍数だから左辺もの倍数であるが，とは互いに素だからがの倍数である。よって（は正の整数）とおける。これをに代入してが最小となるのはのとき。よって最小公倍数は。

最大公約数と最小公倍数の関係

，の最大公約数，最小公倍数について，が成り立ちます。

証明　の両辺にをかけて。，だから。

，の値によらずが成り立つのはちょっと不思議に感じるかもしれません。本当はこっちの話がきっかけでしたが，構成上こんな風になりました。