共通の約数 b をもつ数の線形結合も b を約数にもちます

共通の約数 b をもつ数字の線形結合

 たとえば共通の約数 2 をもつ 6 と 12 を考えます。
 数論の記号を使うと 2|6 , 2|12 です。これを足し合わせると
 
\[6+12=2(3+6)=2\cdot 9\]
と書けるので、18 もまた 2 を約数にもちます。今度は 6 と 12 にそれぞれ適当な整数を掛けて加えてみます(これを 線形結合 とよびます)。たとえば係数として 11 と 5 を選ぶと
 
\[11\cdot 6+5\cdot 12=2(11\cdot 3+5\cdot 6)=2\cdot 63\]
と書けるので、126 もやはり 2 を約数にもちます。以上のことを一般化すると次の定理が成り立ちます。

[定理 A3] 整数 $a_1,\:a_2,\:b,,\:c_1,\:c_2$ について

$b\,|\,a_1,\:b\,|\,a_2$ ならば $b\,|\,c_1a_1+c_2a_2$

が成り立ちます。

[定理 A3 の証明] $a_1=bq_1,\:a_2=bq_2$ と表すと、
 
\[c_1a_1+c_2a_2=b\,(c_1q_1+c_2q_2)\]
となるので、$b$ を約数にもつことが示されました。

 定理 A3 は次のように拡張できます。

[定理 A4] 整数 $a_i,\:b,\:c_i\: (i=1,\:2,\:\cdots\:n)$ について

$b\,|\,a_i$ ならば $b\,|\,\displaystyle\sum_{i=1}^n c_ia_i$

が成り立ちます。

 定理 A3 と A4 を数学記号を用いて簡略して書いてみます。
 整数全体の集合は $\mathbb{Z}$ と表すことが慣例になっています。そしてこの集合から1つの整数 $a$ を選ぶこと、つまり任意の整数 $a$ であることを $a\in\mathbb{Z}$ のように書きます。正確には「 $a$ は $\mathbb{Z}$ の元である」ことを意味しています。また「 P ならば Q 」、すなわち「 P は Q であるための十分条件」であることを $P\Longrightarrow Q$ という記号で表します。このような記号を用いると定理 A3 と A4 は次のように書くことができます。

[定理 A3] $a_1,\:a_2,\:b,,\:c_1,\:c_2\in\mathbb{Z}$
\[b|a_1,\quad b\,|\,a_2\quad\Longrightarrow\quad b\,|\,c_1a_1+c_2a_2\]
[定理 A4] $a_i,\:b,\:c_i\in\mathbb{Z}\quad (i=1,\:2,\:\cdots\:n)$
\[b\,|\,a_i\quad\Longrightarrow\quad b\,|\,\sum_{i=1}^n c_ia_i\]

 このように記号だけ並べてしまうと、慣れないうちは難しく感じるかもしれませんが、そもそも記号は物事を楽に考えるために(つまりなるべく脳を休ませるために)使うのであって、いったん慣れてしまえば、こちらのほうがずっと楽に思えてくるのです。当サイトでは両方のスタイルを併記するようにします。
 

c|b , b|a ならば c|a

 たとえば 3 を約数にもつ 9 と、9 を約数にもつ 27 について、27 が 3 を約数にもつことはほぼ自明のことですが、これを定理として書くと次のようになります。

[定理 A5] 整数 $a,b,c$ について

$c\,|\,b,\:b\,|\,a$ ならば $c\,|\,a$

が成り立ちます。

 最小公倍数の定義と使用する記号についてまとめておきます。

 ある正整数 $M$ が正整数 $a$ と $b$ を約数にもつとき、すなわち $a\:|\:M$ かつ $b\:|\:M$ であるとき、$M$ を $a$ と $b$ の公倍数 (Common Multiple) といいます。その中で最小の $M$ を最小公倍数 (LCM ; Least Common Multiple) とよび、$\{a,\:b\}$ という記号で表します。

 たとえば 8 と 12 の公倍数は
 
\[24,\:48,\:72,\:96,\:\cdots\]
であり、この中の最小のものは 24 なので、
 
\[\mathrm{LCM}=\{8,\:12\}=24\]
のように表します。

 たとえば、8 と 12 の公倍数 24, 48, 72, 96 ... はいずれも最小公倍数 24 で割り切れます。これは最小公倍数に関する最も基本的な性質であり、一般的に書くと次のようになります。

[定理 A6] 2 つの正整数 $a,\:b$ の公倍数は、その 2 整数の最小公倍数 $\{a,\:b\}$ で割り切れます。

 記号を使って書くと次のようになります。

[定理 A6]   $a\:|\:m,\:b\:|\:m,\: l=\{a,\:b\}\quad\Longrightarrow\quad l\:|\:m$

[定理 A6 の証明] 証明に用いる定理 A3 を再掲しておきます。

[定理 A3] 整数 $a_1,\:a_2,\:b,\:c_1,\:c_2$ について、

$b\:|\:a_1,\:b\:|\:a_2\quad\Longrightarrow\quad b\:|\:c_1a_1+c_2a_2$

が成り立ちます。

 除算アルゴリズム によって
 
\[m=lq+r\quad (0\leq r\lt l)\]
となるような整数 $q,\:r$ が唯一組定まります。すなわち
 
\[r=m-lq\]
 $a\:|\:m$ かつ $b\:|\:m$ , $a\:|\:l$ かつ $b\:|\:l$ なので、定理 A3 より $a\:|\:r$ かつ $b\:|\:r$ です。
 すなわち $r$ も $a,\:b$ の公倍数となります。しかし $0\leq r\lt l$ のような $r$ が存在してしまうと $l$ が最小であることに反します。ゆえに $r=0$ となり、
 
\[l\:|\:m\] 
であることが示されました。(証明終)

 最大公約数の定義と記号、いくつかの定理をまとめておきます。

 ある正整数 $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\]
と表します。
 

[定理 A7] 正整数 $d$ が $g$ の約数であることは、$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 です。
 言われてみれば当たり前のことなのですが、この同値関係を使うだけで証明が上手くいく場合があるのです。
 

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

 [定理 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 のいずれでも割り切れます。
 

最大公約数と互いに素である数

 たとえば 10 と 15 の最大公約数 $g$ は
 
\[g=(10,\:15)=5\]
ですが、10 と 15 はそれぞれ $g$ を用いて
 
\[10=2g,\quad 15=3g\]
と表せます。このとき 2 と 3 は互いに素な関係にあります:
 
\[(2,\:3)=1\]
 このことを一般的に書くと次のような定理になります。

[定理 A9] 2 つの正整数 $a,\:b$ の最大公約数を $g$ とし、
\[a=a_1g,\quad b=b_1g\]とおくと、$a_1$ と $b_1$ は互いに素です。

 [定理 A9 の証明] $a_1,\:b_1$ に公約数 $g_1$ が存在すると仮定すると
 
\[a_1=g_1r,\quad b=g_1s\]
のように表すことができます。すなわち
 
\[a_1=(g_1g)r,\quad b=(g_1g)s\]
となります。つまり $g_1g$ が $a,\:b$ の公約数であるということですが、これは明らかに $g$ が最大公約数であることに矛盾します。よって $a_1$ と $b_1$ は互いに素です。(証明終)
 

2 整数の積は GCD と LCM の積に等しい

 10 と 15 の最大公約数 $g$ , 最小公倍数 $l$ はそれぞれ、
 
\[g=(10,\:15)=5,\quad l=\{10,\;15\}=30\]
となります。このとき最大公約数と最小公倍数の積 $gl$ は 10 と 15 の積 150 に等しくなっています。これを一般的に書くと次のようになります。

[定理 A10] 2 つの正整数の積は、その 2 整数の最大公約数と最小公倍数の積に等しい。

 [定理 A10 の証明] $a,\:b$ を最大公約数 $g$ を用いて
 
\[a=a_1g,\:\:b=b_1g\]
とおくと、定理 A9 より $a_1$ と $b_1$ は互いに素です:
 
\[(a_1,\:b_1)=1\]
 ここで $m=ga_1b_1$ とおくと、
 
\[\begin{align*}m=(ga_1)b_1=b_1a\\[6pt]
m=a_1(gb_1)=a_1b\end{align*}\tag{1}\]
のように書くことができるので、$m$ は $a$ と $b$ の公倍数であることがわかります。公倍数は最小公倍数で割り切れるので、
 
\[l\:|\:m\]
となります。そこで
 
\[m=kl\tag{2}\]
とおくと (1) より
 
\[kl=b_1a,\quad kl=a_1b\tag{3}\]
 また $l$ は $a$ と $b$ の最小公倍数なので
 
\[l=a_2a,\quad l=b_2b\]
と表せます。これを (3) に代入すると
 
\[(a_2a)k=b_1a,\quad (b_2b)k=a_1b\]
 すなわち
 
\[a_2k=b_1,\quad b_2k=a_1\]
 よって $k$ は $a_1,\:b_1$ の公約数ですが、$(a_1,\:b_1)=1$ なので $k=1$ となり、
 
\[a_2=b_1,\quad b_2=a_1\]
 すなわち (2) より $m=kl=l$ なので、
 
\[ga_1b_1=l\]
 両辺に $g$ をかけると
 
\[(ga_1)(gb_1)=gl\]
 すなわち
 
\[ab=gl\]
であることが示されました。(証明終)
 

a, b が素であり、bc が a で割り切れるなら、c は a で割り切れる

 3 と 5 は互いに素の関係にあります。
 
\[(3,\:5)=1\]
 ここで 3 で割り切れるように 5 に適当な数をかけます。
 たとえば 6 をかけてみると
 
\[3\:|\:5\times 6\]
 すると 5 は 3 で割れないのですから、 6 が 3 で割り切れることがわかります。
 
\[3\:|\:6\]
 当たり前といえば当たり前のことですが、これも定理として載せておきます。

[定理 A11] 2 つの整数 $a,\:b$ が互いに素であり、$bc$ が $a$ で割り切れるなら、$c$ は $a$ で割り切れます。

 [定理 A11 の証明] 2 整数の積は最大公約数と最小公倍数の積に等しいので、
 
\[(a,\:b)\{a,\:b\}=ab\]
が成り立ちます。$a,\:b$ は互いに素なので、
 
\[\{a,\:b\}=ab\]
 $a\:|\:bc,\:\:b\:|\:bc$ より $bc$ は $a$ と $b$ の公倍数なので
 
\[\{a,\:b\}\:|\:bc\]
 したがって $ab\:|\:bc$ すなわち $a\:|\:c$ が示されました。(証明終)
 

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 整数の最小公倍数

 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\]
と計算できます。


 

コメントをどうぞ

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