【分解する物語（９）】最大公約数

自然数の素因数分解が一意的であることを証明しよう。前回の考察から、一意分解条件を示すには次の２つの条件：
　（Ⅱ）約鎖条件
　（Ⅲ）素元条件
を満足することを確認すればよい。ここではこの２つを確認しよう。

ただし（Ⅲ）素元条件については、「最大公約数の２つの定義について、両者は同値である」ということを認めた上で証明する。この２つの定義の同値性の証明はここでは与えず、先に素元性を導こう。

１．約鎖条件の確認

任意の自然数ａを持ってきて、ａ＝ａ(0)の約元の列を作る：
　･･･｜ａ(n)｜･･･｜ａ(1)｜ａ(0)

このとき、自然数の減少列となる：
　ａ(0)≧ａ(1)≧･･･≧ａ(n)≧･･･

自然数だからこの減少列はすべて０より大きいから、ある番号Ｎが存在して、すべてのｎ≧Ｎについて
　ａ(n)＝ａ(n+1)
となる。よって、特に
　ａ(n)～ａ(n+1)
である。

これで約鎖条件が確認された。

２．素元条件の確認

自然数の乗法に関する世界における既約元とは素数のことであった。つまり、素数が素元であることを示せばよい。つまり、
　ｐが素数のとき、
　　ｐ｜ａｂ　⇒　ｐ｜ａ　または　ｐ｜ｂ
を示せばよい。

一見、素数に関するこの性質は疑う余地がないかもしれないが、素因数分解の一意性がまだ証明されていないのに、その証明に素因数分解の一意性を使うことはできない。ここでは素数の定義と何か初等的な原理を使って導かなくてはならない。

ではこのことは一体何が原理になって機能するのだろう。

３．最大公約数の定義

その鍵は、最大公約数の考察にある。

最大公約数とは何だったか思い出そう。

まずａとｂを２つの自然数とする。ａとｂの約数で共通する自然数を、ａとｂの公約数と呼んだ。

整除関係”｜”の記号を使って書けば、ａ，ｂの公約数は
　ｄ’｜ａ　かつ　ｄ’｜ｂ
を満たす自然数ｄ’をいう。

どんな自然数でも１は必ず約数としてもつから、公約数はひとつもないことはない。そして、公約数は有限個しかない。

そして、自然数ａ，ｂの公約数の中で、大小関係（≦）において最大であるものを最大公約数と呼んだ。これを定式化すると、次の定義１になる。

【定義１】
　任意の２つの自然数ａ，ｂについて、次の２条件を満たす自然数ｄをａとｂの最大公約数という：
　　（１）ｄ｜ａ　かつ　ｄ｜ｂ
　　（２）ｄ’｜ａ　かつ　ｄ’｜ｂ　⇒　ｄ’≦ｄ

条件（１）は公約数の条件で、条件（２）は公約数の中での最大値という条件をいっている。

例えば、ａ＝１２とｂ＝８の場合、
　１２の約数：１，２，３，４，６，１２
　８の約数：１，２，４，８
であるから、この２数の公約数ｄ’は
　ｄ’＝１，２，４
であり、最大公約数ｄはこの公約数のうち最大の自然数であるから
　ｄ＝４
である。

さてこの定義は馴染みのあるわかりやすいのであるが、次のような同値な定義もある：

【定義２】
　任意の２つの自然数ａ，ｂについて、次の２条件を満たす自然数ｄをａとｂの最大公約数という：
　（１）ｄ｜ａ　かつ　ｄ｜ｂ
　（２）ｄ’｜ａ　かつ　ｄ’｜ｂ　⇒　ｄ’｜ｄ

条件（１）は公約数の条件であるのは定義１と同じである。

条件（２）は条件（１）を満たすもの（公約数）の集合における整除関係”｜”（これは順序関係であった）に関する最大性を意味する。

自然数の場合はこの定義２と、もとの定義１が一致する。

例えば、上と同じａ＝１２とｂ＝８の例では、公約数が
　１，２，４
であったが、確かに最大公約数４はどの公約数も約数に持つ。
　１｜４，２｜４，４｜４

一般の場合でも両定義は同値である。しかしその証明は後にしよう。今はこれを認めた上で、定義２を使って議論を進めよう。

さて、ａ，ｂの最大公約数（greatest common divisor）を
　（ａ，ｂ）
と書く。あるいは、もっと丁寧には
　ｇｃｄ（ａ，ｂ）
と書くこともある。

なお、最大公約数は２つの自然数の組でなくても同様に定義される。３つ以上の場合、次のようになる：

３つ以上の有限個の自然数ａ，ｂ，ｃ，･･･について次の２条件を満たす自然数ｄをａ，ｂ，ｃ，･･･の最大公約数という：
（１）ｄ｜ａ　かつ　ｄ｜ｂ　かつ　ｄ｜ｃ　かつ　･･･
（２）ｄ’｜ａ　かつ　ｄ’｜ｂ　かつ　ｄ’｜ｃ　かつ　･･･　⇒　ｄ’｜ｄ

やはり、このｄを
　（ａ，ｂ，ｃ，･･･）
と書く。あるいは、もっと丁寧には
　ｇｃｄ（ａ，ｂ，ｃ，･･･）
と書くこともある。

４．最大公約数の存在性

任意の２つの自然数の公約数は有限個であるから、通常の大小関係に関する公約数の最大値が存在する。それが定義１による最大公約数であるから、最大公約数が常に存在することがわかる。

そして２つの自然数の最大公約数の存在性から、３つ以上の自然数の最大公約数の存在も、次節の性質２によって２つずつを組にして帰納的に証明される。

５．最大公約数の諸性質

ここではのちの証明で使えるように、先に最大公約数の性質を３つ見ておこう。

【性質１】
有限個の自然数ａ，ｂ，ｃ，･･･の最大公約数は、それらの元の並び順は関係ない。例えば、
　（ａ，ｂ，ｃ，･･･）＝（ａ，ｃ，ｂ）＝（ｂ，ｃ，ａ，･･･）＝･･･
等が成り立つ。

これは定義より明らかである。

【性質２】
　（ａ，ｂ，ｃ，･･･）＝（（ａ，ｂ），ｃ，･･･）

【証明】
左辺の値をｄ，右辺の値をｅとおこう。ｄ＝ｅをいうのに、
　ｄ｜ｅ　かつ　ｅ｜ｄ
（すなわちｅとｄは互いに同伴である）を示せばよい。

まずｄの公約数性だから
　ｄ｜ａ，ｄ｜ｂ，ｄ｜ｃ，･･･
である。そして最大公約数（ａ，ｂ）の最大性によって
　ｄ｜（ａ，ｂ），ｄ｜ｃ，･･･
とわかる。よって右辺の最大公約数の最大性によって
　ｄ｜ｅ
である。

次に、ｅの公約数性から
　ｅ｜（ａ，ｂ），ｅ｜ｃ，･･･
である。特に
　ｅ｜ａ，ｅ｜ｂ，ｅ｜ｃ，･･･
であるから左辺の最大公約数の定義によって
　ｅ｜ｄ
である。

左辺ｄと右辺ｅの両者は互いに割り合うから同伴である。自然数の同伴とは等号に他ならない。よって、
　ｄ＝ｅ
である。■

【性質３】
　（ａｘ，ａｙ）＝ａ（ｘ，ｙ）

【証明】
左辺をｄ，右辺の（ｘ，ｙ）をｅとおく。ｄ＝ａｅをいうのに、
　ａｅ≦ｄ　かつ　ｄ≦ａｅ
を示せばよい。

まず、
　ａ｜ａｘ，ａ｜ａｙ
よりａは、ａｘとａｙの公約数であるから
　ａ｜ｄ
である。よって
　ｄ＝ａｔ
となる自然数ｔがある。このとき、
　（ａｔ）ｓ＝ａｘ，（ａｔ）ｓ’＝ａｙ
となる自然数ｓ，ｓ’が存在するから、ａを消去して
　ｔｓ＝ｘ，ｔｓ’＝ｙ
を得る。よって、
　ｔ｜ｘ，ｔ｜ｙ
となり、ｔはｘとｙの公約数である。従ってｅの最大性より
　ｔ｜ｅ
となる。よって、
　ｄ＝ａｔ
　　≦ａｅ　　･･･①

一方、
　ａｅ｜ａｘ，ａｄ｜ａｙ
であるからａｅはａｘとａｙの公約数である。よって、
　ａｅ｜ｄ
となり、
　ａｅ≦ｄ　　･･･②
となる。

①，②より、
　ｄ＝ａｅ
が示された。■

６．素数は素元である

ここでは素数の素元性を導こう。

ｐを任意の素数とする。２つの自然数ａ，ｂがともにｐの倍数でないと仮定する：
　自然数ａ，ｂについて、
　　ｐ｜ａでない　かつ　ｐ｜ｂでない

このときｐが積ａｂで割り切れないこと：
　ｐ｜ａｂでない
を示せば（素元の定義の対偶が証明され）ｐが素元とわかる。

さて、仮定によってｐとａの最大公約数は１である。実際、ｄをｐとａの公約数：
　ｄ｜ｐ　かつ　ｄ｜ａ
とすると、ｄはｐの約数で、ｐは素数（つまり既約元）であるからｄはｐまたは１と同伴である：
　ｄ～ｐ　または　ｄ～１

ｄ～ｐであれば、ｄ｜ａより
　ｐ｜ａ
となって、最初の仮定の
　ｐ｜ａでない
に反する。

よって
　ｄ～１
となる。つまりｐとａの最大公約数ｄは１である。

同様にしてｐとｂの最大公約数も１である。

これらのことから、ｐと積ａｂの最大公約数も１であることが次のようにしてわかる。
　（ｐ，ａｂ）＝（（ｐ，ｐａ），ａｂ）
　　　　　　　＝（ｐ，（ｐａ，ａｂ））　　（∵性質２）
　　　　　　　＝（ｐ，ａ（ｐ，ｂ））　　　（∵性質３）
　　　　　　　＝（ｐ，ａ）
　　　　　　　＝１
よって、ａｂはｐの倍数ではない。

以上でｐが素元であることがわかった。

７．結論

自然数の乗法の世界において、素因数分解の一意性は、
　（Ⅱ）任意の自然数についてその約鎖条件を満足し（約鎖条件）
　（Ⅲ）素数が素元である（素元条件）
ことによって証明された。

ただし、素数が素元であることは、
　「自然数の最大公約数の定義について、定義１と定義２は同値である」
ということを認めた上で証明した。

従って、その証明を与えなければならない。その証明については後で考察しよう。