共通約数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 を約数にもちます。以上のことを一般化すると次の定理が成り立ちます。

[証明] $a_1=b{q}_1,a_2=b{q}_2$ と表すと、
$$c_1{a}_1+c_2{a}_2=b(c_1{q}_1+c_2{q}_2)$$
となるので、$b$ を約数にもつことが示されました。

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

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

このように記号だけ並べてしまうと、慣れないうちは難しく感じるかもしれませんが、そもそも記号は物事を楽に考えるために（なるべく脳を休ませるために）使うのであって、いったん慣れてしまえば、こちらのほうがずっと楽に思えてきます。
　　

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

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

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

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

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

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

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

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

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

[証明] 定理 A7 より、最小公倍数 $l=(d,g)$ が $g$ に等しいを示せばよいことになります。
$$d|a,g|a$$
なので $a$ は $d$ と $g$ の公倍数です。公倍数は最小公倍数で割り切れるので、
$$l|a$$
が成り立ちます。同様に
$$l|b$$
も成り立ちます。つまり $l$ は $a,b$ の公約数となっています。公約数は最大公約数以下ですから
$$l\le g$$
です。一方で $g|l$ より
$$g\le 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,15=3g$$
と表せます。このとき 2 と 3 は互いに素な関係にあります：
$$(2,3)=1$$
このことを一般的に書くと次のような定理になります。

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

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

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

[証明] $a,b$ を最大公約数 $g$ を用いて
$$a=a_{1}g,b=b_{1}g$$
とおくと、定理A9 より $a_1$ と $b_1$ は互いに素です：
$$(a_1,b_1)=1$$
ここで $m=g{a}_1{b}_1$ とおくと、
$$\begin{array}{}\text{(1)}& \begin{array}{r}m=(g{a}_1)b_1=b_{1}a\\ m=a_1(g{b}_1)=a_{1}b\end{array}\end{array}$$
のように書くことができるので、$m$ は $a$ と $b$ の公倍数であることがわかります。公倍数は最小公倍数で割り切れるので、
$$l|m$$
となります。そこで
$$\begin{array}{}\text{(2)}& m=kl\end{array}$$
とおくと (1) より
$$\begin{array}{}\text{(3)}& kl=b_{1}a,kl=a_{1}b\end{array}$$
また $l$ は $a$ と $b$ の最小公倍数なので
$$l=a_{2}a,l=b_{2}b$$
と表せます。これを (3) に代入すると
$$(a_{2}a)k=b_{1}a,(b_{2}b)k=a_{1}b$$
すなわち
$$a_{2}k=b_1,b_{2}k=a_1$$
よって $k$ は $a_1,b_1$ の公約数ですが、$(a_1,b_1)=1$ なので $k=1$ となり、
$$a_2=b_1,b_2=a_1$$
すなわち (2) より $m=kl=l$ なので、
$$g{a}_1{b}_1=l$$
両辺に $g$ をかけると
$$(g{a}_1)(g{b}_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$$
当たり前といえば当たり前のことですが、これも定理として載せておきます。

[証明] 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 です。

[証明] 当たり前のことですが、
$$(a,b,c)|a,(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$ の最大公約数で割り切れます。
$$\begin{array}{}\text{(1)}& (a,b,c)|((a,b),c)\end{array}$$
また、次のような関係が成り立つことも明らかです：
$$\begin{array}{r}((a,b),c)|(a,b)|a\\ ((a,b),c)|(a,b)|b\\ ((a,b),c)|c\end{array}$$
すなわち $(a,b,c)$ は $((a,b),c)$ で割り切れます。
$$\begin{array}{}\text{(2)}& ((a,b),c)|(a,b,c)\end{array}$$
(1) と (2) より、
$$(a,b,c)=((a,b),c)$$
が成り立つことが示されました。（証明終）

この定理から直ちに次の定理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$$
と計算することができます。これもほぼ自明のことだと思われるかもしれませんが、以下で証明しておきます。

[証明] $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$ の最小公倍数で割り切れます。
$$\begin{array}{}\text{(3)}& \{\{a,b\},c\}|\{a,b,c\}\end{array}$$
また、次の関係が成り立つことは明らかです。
$$\begin{array}{r}a|\{a,b\}|\{\{a,b\},c\}\\ b|\{a,b\}|\{\{a,b\},c\}\\ c|\{\{a,b\},c\}\end{array}$$
すなわち
$$\begin{array}{}\text{(4)}& \{a,b,c\}|\{\{a,b\},c\}\end{array}$$
が成立します。(3), (4) より
$$\{a,b,c\}=\{\{a,b\},c\}$$
となることが示されました。（証明終）

定理A15 から次の定理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$$
と計算できます。