2 整数の最大公約数は、その 2 整数の公約数で割り切れます

最大公約数の定義

 最大公約数の定義と記号についてまとめておきます。

 ある正整数 $m$ が正整数 $a$ と $b$ の共通の約数になっているとき、すなわち $m\:|\:a$ かつ $m\:|\:b$ であるとき、$m$ を $a$ と $b$ の公約数 (Common Divisor) といいます。その中で最大の $m$ を最大公約数 (GCD ; Gread Common Divisor) とよび、$(a,\:b)$ という記号で表します。

 たとえば 12 と 30 の公約数は
 
\[1,\:2,\:3,\:6\]
であり、この中の最大のものは 6 なので、
 
\[\mathrm{GCD}=(12,\:30)=6\]
と表します。
 

整数 d が g の約数 ⇔ d と g の最小公倍数が g

 今回の記事タイトルにある定理を証明する前に、次の定理 A7 を証明しておきます。

[定理 A7] 正整数 $d$ が $g$ の約数であることは、$d$ と $g$ の最小公倍数が $g$ であることと同値です。

 記号を使って書き直すと、

[定理 A7] $d\:|\:g\quad\Longleftrightarrow\quad \{d,\:g\}=g$

 [定理 A7 の証明]
 $\{d,\:g\}=g\:\:\Rightarrow\:\: d\:|\:g$ は最小公倍数の定義から明らかです。
 $d\:|\:g\:\:\Rightarrow\:\: \{d,\:g\}=g$ を示します。$d\:|\:g$ なので $g=kd$ と書けて、
 
\[\{d,\:g\}=\{d,\:kd\}=kd=g\]
 すなわち $d$ と $g$ の最小公倍数が $g$ であることが示されました。(証明終)

 たとえば 8 は 2 を約数にもちますが、2 と 8 の最小公倍数は 8 です。
 言われてみれば当たり前のことなのですが、この同値関係を使うだけで証明が上手くいく場合があるのです。
 

大学入試問題で語る数論の世界―素数、完全数からゼータ関数まで (ブルーバックス)

中古価格
¥298から
(2017/9/1 13:26時点)

2 整数の最大公約数は、その 2 整数の公約数で割り切れます

 今回証明したいのは以下の定理 A8 です。

[定理 A8] 2 つの正整数 $a,\:b$ の最大公約数 $(a,\:b)$ は、その 2 整数の公約数で割り切れます。

 記号を使って簡略化すると

[定理 A8] $d\:|\:a,\:\:d\:|\:b,\:\:g=(a,\:b)\quad\Longrightarrow\quad d\:|\:g$

 [定理 A8 の証明]
 定理 A7 より、最小公倍数 $l=(d,\:g)$ が $g$ に等しいを示せばよいことになります。
 
\[d\:|\:a,\:\:g\:|\:a\]
なので $a$ は $d$ と $g$ の公倍数です。公倍数は最小公倍数で割り切れるので、
 
\[l\:|\:a\]
が成り立ちます。同様に
 
\[l\:|\:b\]
も成り立ちます。つまり $l$ は $a,\:b$ の公約数となっています。公約数は最大公約数以下ですから
 
\[l\leq g\]
です。一方で $g\:|\:l$ より
 
\[g\leq l\]
も成り立っています。つまり
 
\[l=g\]
であり、$d$ と $g$ の最小公倍数が
 
\[l=\{d,\:g\}=g\]
であること、すなわち
 
\[d\:|\:g\]
であることが示されました。(証明終)

 以上の事実は具体的な数字で確認すると、ほとんど自明のことです。
 たとえば 12 と 30 の公約数を並べると
 
\[1,\:2,\:3,\:6\]
となりますが、最大公約数 6 は 1, 2, 3 のいずれでも割り切れます。

 ≫ 2 整数の積は GCD と LCM の積に等しくなります
 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。