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

共通約数をもつ数字の線形結合
c|b,b|aならばc|a

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

たとえば共通の約数を 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$ について
$\qquad\qquad b\,|\,a_1,\:b\,|\,a_2$　ならば　$b\,|\,c_1a_1+c_2a_2$

[証明] $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)$ について
$\qquad\qquad b\,|\,a_i$　ならば　$b\,|\,\displaystyle\sum_{i=1}^n c_ia_i$

定理A3 と定理A4 を数学記号を用いて簡略して書いてみます。
整数全体の集合は $\mathbb{Z}$ と表すことが慣例になっています。そしてこの集合から１つの整数 $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 \Longrightarrow 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】$a\:|\:m,\:b\:|\:m,\: l=\{a,\:b\}\quad\Longrightarrow\quad 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$ であることと同値である。

[証明]$\{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 整数の公約数で割り切れる。

[証明] 定理 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$ は互いに素である。

[証明] $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 整数の最大公約数と最小公倍数の積に等しい。

[証明] $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$ で割り切れる。

[証明] 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)\]が成り立ちます。

[証明] 当たり前のことですが、
\[(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\]

[証明] $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\}\]

[証明] $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\]

[証明] 定理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\]
と計算できます。

【次の記事】≫ ユークリッドの互除法の原理