最大公約数と最小公倍数の積の性質の2通りの証明

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

正の整数 a,ba,b に対して,それらの最大公約数を gg,最小公倍数を ll とおくと ab=glab=gl

つまり,「最大公約数と最小公倍数の積」が「もとの二つの数の積」に等しい。

覚える必要はありませんが,シンプルで美しい定理です。2通りの証明を解説します。

具体例

証明の前に実験してみましょう。まずは数が小さい例です。

a=6,b=9a=6,b=9 のとき,

より,最大公約数は g=3g=3,最小公倍数は l=18l=18 です。

実際,ab=54=glab=54=gl となっています!

もう少し数が大きい場合の例です!

a=72,b=182a=72,b=182 のとき,

a=23×32a=2^3\times 3^2

b=2×7×13b=2 \times 7\times 13

より,最大公約数は g=2g=2,最小公倍数は l=23×32×7×13=6552l=2^3\times 3^2\times 7\times 13=6552 です。

実際,ab=13104=glab=13104=gl となっています。

素因数分解を用いた証明

では,ab=glab=gl の証明を2通り紹介します。

まずは,具体例で実験をしていると思いつきやすい証明です。記号がいろいろ登場して難しそうですが,考え方は難しくありません。

なお,max(ei,fi)\max(e_i,f_i)eie_ifif_i のうち大きい方,min(ei,fi)\min(e_i,f_i) は小さい方を表します。

証明

aabb の少なくともどちらか一方を割り切る素数を p1,p2,,pkp_1,p_2,\cdots ,p_k とおく。このとき,aabb を素因数分解すると,

a=p1e1p2e2pkeka=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}

b=p1f1p2f2pkfkb=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}

となる(ただし,ei,fie_i,f_i00 以上の整数であり,素因数分解に登場しない素数の部分の指数は 00 となる)。

このとき,

  • 最大公約数 gg を素因数分解したときの pip_i の指数は min(ei,fi)\min(e_i,f_i)
  • 最小公倍数 ll を素因数分解したときの pip_i の指数は max(ei,fi)\max(e_i,f_i)

となる(※)。

よって,glgl を素因数分解したときの pip_i の指数は min(ei,fi)+max(ei,fi)=ei+fi\min(e_i,f_i)+\max(e_i,f_i)=e_i+f_i

となり,abab を素因数分解したときの pip_i の指数と等しい。

g,lg,l には当然 pip_i 以外の素因数は登場しないので)ab=glab=gl が示された。

min(ei,fi)+max(ei,fi)=ei+fi\min(e_i,f_i)+\max(e_i,f_i)=e_i+f_i が成立するのが証明の肝です。

※部分について難しい方は,以下の「補題」をご参照ください。

最小公倍数と最大公約数の性質

補題

正の整数 a,ba,b に対して,

  • 素因数分解して「各部分の大きい方」をかけ算したものが最小公倍数
  • 素因数分解して「各部分の小さい方」をかけ算したものが最大公約数

a=12,b=18a=12,b=18 の最小公倍数と最大公約数を計算してみよう。

素因数分解すると

  • a=22×3a=2^2\times 3
  • b=2×32b=2\times 3^2

ここで,

  • 「素因数2」について大きいのは 222^2,「素因数3」について大きいのは 323^2 なので,最小公倍数は 22×32=362^2\times 3^2=36
  • 「素因数2」について小さいのは 212^1,「素因数3」について小さいのは 313^1 なので,最大公約数は 21×31=62^1\times 3^1=6
補題の証明

最小公倍数について考える。

aa は素因数 pp でちょうど AA 回割れ,bb は素因数 pp でちょうど BB 回割れるとする。

  • aabb の公倍数は pAp^A の倍数かつ pBp^B の倍数なので,pAp^ApBp^B の大きい方 pmax(A,B)p^{\mathrm{max}(A,B)} の倍数である。
  • 一方「最小」公倍数ならそれよりも多い回数 pp で割れるとおかしい。

つまり,aabb の最小公倍数は,pp でちょうど「AABB の大きい方」回だけ割れる。他の素因数も同様。

最大公約数も同様。

最大公約数と最小公倍数の定義を考えた証明

次は,ab=glab=gl について,もう一つ証明方法を解説します!

証明

ggaabb の最大公約数なので,互いに素な整数 a,ba',b' を使って

a=ga,b=gba=ga',b=gb' と書ける。

このとき 「補題2:aabb の最小公倍数は l=gabl=ga'b'である」

より,gl=g(gab)=gagb=abgl=g(ga'b')=ga'gb'=ab となり証明完了。

補題2の証明:
最小公倍数は a=gaa=ga' の倍数なので,整数 nn を用いて l=ngal=nga' と書ける。これが b=gbb=gb' の倍数となるのは「nana'bb' の倍数となる」のは条件。ところが,aa'bb' は互いに素なので,さきほどの条件は「nnbb' の倍数となるとき」と言い換えられる。よって,最小公倍数は n=bn=b' のときに対応して,l=gabl=ga'b' となる。

私は1つ目の証明の方が好きです!

Tag:数学Aの教科書に載っている公式の解説一覧