3 整数の最大公約数と最小公倍数

3 整数の最大公約数

 たとえば 16, 24, 28 の 3 整数について、16 と 24 の最大公約数は
 
\[(16,\:24)=8\]
であり、8 と 28 の最大公約数は
 
\[(8,\:28)=4\]
となって、これが 3 整数の最大公約数 となっていることは、それぞれの数を素因数分解してみれば、ほぼ自明のことだといえます:
 
\[(2^3,\:2^3\cdot 3,\:2^2\cdot 7)=4\]
 ただし本講座ではまだ素因数分解を定義していないので、これはちょっと反則ですね。後述の一般定理はもちろん素因数分解なしで証明します。ようするに 3 整数の間には
 
\[(16,\:24,\:30)=((16,\:24),\:30)=4\]
が成り立っています。これを一般的に書いたのが定理 A13 です。

[定理 A13] 任意の 3 整数 $a,\:b,\:c$ について
\[(a,\:b,\:c)=((a,\:b),\:c)\]が成り立ちます。

[定理 A13 の証明] 当たり前のことですが、
 
\[(a,\:b,\:c)\:|\:a\:,\quad (a,\:b,\:c)\:|\:b\]
が成り立ちます。すなわち $(a,\:b,\:c)$ は $a,\:b$ の公約数ですから、これはもちろん $a,\:b,\:c$ の最大公約数で割り切れます。
 
\[(a,\:b,\:c)\:|\:(a,\:b)\]
 さらに
 
\[(a,\:b,\:c)\:|\:c\]
も成り立っているので、$(a,\:b,\:c)$ は $(a,\:b)$ と $c$ の公約数です。これも $a,\:b,\:c$ の最大公約数で割り切れます。
 
\[(a,\:b,\:c)\:|\:((a,\:b),\:c)\tag{1}\]
 また、次のような関係が成り立つことも明らかです:
 
\[\begin{align*}((a,\:b),\:c)\:|\:(a,\:b)\:|\:a\\[6pt]
((a,\:b),\:c)\:|\:(a,\:b)\:|\:b\\[6pt]
((a,\:b),\:c)\:|\:c\end{align*}\]
 すなわち $(a,\:b,\:c)$ は $((a,\:b),\:c)$ で割り切れます。
 
\[((a,\:b),\:c)\:|\:(a,\:b,\:c)\tag{2}\]
 (1) と (2) より、
 
\[(a,\:b,\:c)=((a,\:b),\:c)\]
が成り立つことが示されました。(証明終)

 この定理から直ちに次の定理 A14 が導き出されます。

[定理 A14] 整数 $a,\:b,\:c$ のいずれか 2 つが互いに素であるならば
\[(a,\:b,\:c)=1\]が成り立ちます。

[定理 A14 の証明] $a,\:b,\:c$ は互いに交換できるので、$(a,\:b)=1$ である場合のみを考えます。定理 A13 から
 
\[(a,\:b,\:c)=((a,\:b),\:c)=(1,\:c)=1\]
となり、定理 A14 が証明されました。(証明終)

 この定理は 3 数のうちいずれか 2 つが互いに素 であれば使えます(もちろん 3 数全てが互いに素であっても成り立つことは言うまでもありません)。たとえば 5, 7, 10 という組を考えると、5 と 7, 7 と 10 は互いに素ですが、5 と 10 は互いに素ではありません。しかし定理 A14 より(わざわざ定理を持ち出さなくても、ひと目でわかりますが)、3 数の最大公約数は 1 です。
 

平方剰余の相互法則―ガウスの全証明

中古価格
¥3,225から
(2017/9/1 13:23時点)

3 整数の最小公倍数

 3 つの整数 4, 6, 10 の最小公倍数は
 
\[\{4,\:6,\:10\}=\{\{4,\:6\}\:10\}=\{12,\:10\}=60\]
と計算することができます。これもほぼ自明のことだと思われるかもしれませんが、以下で証明しておきます。

[定理 A15] 任意の 3 整数 $a,\:b,\:c$ について
\[\{a,\:b,\:c\}=\{\{a,\:b\},\:c\}\]が成り立ちます。

[定理 A15 の証明] $a\:|\:\{a,\:b,\:c\},\:b\:|\:\{a,\:b,\:c\}$ なので、$\{a,\:b,\:c\}$ は $a$ と $b$ の公倍数であり、$a$ と $b$ の最小公倍数で割り切れます。
 
\[\{a,\:b\}\:|\:\{a,\:b,\:c\}\]
 さらに $c\:|\:\{a,\:b,\:c\}$ ですから、$\{a,\:b,\:c\}$ は $\{a,\:b\}$ と $c$ の公倍数であり、$\{a,\:b\}$ と $c$ の最小公倍数で割り切れます。
 
\[\{\{a,\:b\},\:c\}\:|\:\{a,\:b,\:c\}\tag{3}\]
 また、次の関係が成り立つことは明らかです。
 
\[\begin{align*}a\:|\:\{a,\:b\}\:|\:\{\{a,\:b\},\:c\}\\[6pt]
b\:|\:\{a,\:b\}\:|\:\{\{a,\:b\},\:c\}\\[6pt]
c\:|\:\{\{a,\:b\},\:c\}\end{align*}\]
 すなわち
 
\[\{a,\:b,\:c\}\:|\:\{\{a,\:b\},\:c\}\tag{4}\]
が成立します。(3), (4) より
 
\[\{a,\:b,\:c\}=\{\{a,\:b\},\:c\}\]
となることが示されました。(証明終)

 定理 A15 から次の定理 A16 が導き出されます。

[定理 A16] 整数 $a,\:b,\:c$ のどの 2 数をとっても互いに素であるならば
\[\{a,\:b,\:c\}=1\]が成り立ちます。

[定理 A16 の証明] 定理 A15 を用いると
 
\[\{a,\:b,\:c\}=\{\{a,\:b\},\:c\}=\{ab,\:c\}=abc\]
となります。(証明終)

 定理 A14 と対をなす定理ですが、こちらは どの 2 数をとっても互いに素 でなくてはなりません。たとえば 2, 3, 5 という数の組を考えると、2 と 3, 3 と 5, 2 と 5 はどれも互いに素の関係にあるので、その最小公倍数は
 
\[\{2,\:3,\:5\}=30\]
と計算できます。 ≫ 小さくない数と大きくない数 ≫ 初等整数論入門講座

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

コメントをどうぞ

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

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください