![見出し画像](https://assets.st-note.com/production/uploads/images/29008352/rectangle_large_type_2_ca4d7498ac56eb2356af6298e9b8e3cc.jpeg?width=1200)
【分解する物語(9)】最大公約数
自然数の素因数分解が一意的であることを証明しよう。前回の考察から、一意分解条件を示すには次の2つの条件:
(Ⅱ)約鎖条件
(Ⅲ)素元条件
を満足することを確認すればよい。ここではこの2つを確認しよう。
ただし(Ⅲ)素元条件については、「最大公約数の2つの定義について、両者は同値である」ということを認めた上で証明する。この2つの定義の同値性の証明はここでは与えず、先に素元性を導こう。
1.約鎖条件の確認
任意の自然数aを持ってきて、a=a(0)の約元の列を作る:
・・・|a(n)|・・・|a(1)|a(0)
このとき、自然数の減少列となる:
a(0)≧a(1)≧・・・≧a(n)≧・・・
自然数だからこの減少列はすべて0より大きいから、ある番号Nが存在して、すべてのn≧Nについて
a(n)=a(n+1)
となる。よって、特に
a(n)~a(n+1)
である。
これで約鎖条件が確認された。
2.素元条件の確認
自然数の乗法に関する世界における既約元とは素数のことであった。つまり、素数が素元であることを示せばよい。つまり、
pが素数のとき、
p|ab ⇒ p|a または p|b
を示せばよい。
一見、素数に関するこの性質は疑う余地がないかもしれないが、素因数分解の一意性がまだ証明されていないのに、その証明に素因数分解の一意性を使うことはできない。ここでは素数の定義と何か初等的な原理を使って導かなくてはならない。
ではこのことは一体何が原理になって機能するのだろう。
3.最大公約数の定義
その鍵は、最大公約数の考察にある。
最大公約数とは何だったか思い出そう。
まずaとbを2つの自然数とする。aとbの約数で共通する自然数を、aとbの公約数と呼んだ。
整除関係”|”の記号を使って書けば、a,bの公約数は
d’|a かつ d’|b
を満たす自然数d’をいう。
どんな自然数でも1は必ず約数としてもつから、公約数はひとつもないことはない。そして、公約数は有限個しかない。
そして、自然数a,bの公約数の中で、大小関係(≦)において最大であるものを最大公約数と呼んだ。これを定式化すると、次の定義1になる。
【定義1】
任意の2つの自然数a,bについて、次の2条件を満たす自然数dをaとbの最大公約数という:
(1)d|a かつ d|b
(2)d’|a かつ d’|b ⇒ d’≦d
条件(1)は公約数の条件で、条件(2)は公約数の中での最大値という条件をいっている。
例えば、a=12とb=8の場合、
12の約数:1,2,3,4,6,12
8の約数:1,2,4,8
であるから、この2数の公約数d’は
d’=1,2,4
であり、最大公約数dはこの公約数のうち最大の自然数であるから
d=4
である。
さてこの定義は馴染みのあるわかりやすいのであるが、次のような同値な定義もある:
【定義2】
任意の2つの自然数a,bについて、次の2条件を満たす自然数dをaとbの最大公約数という:
(1)d|a かつ d|b
(2)d’|a かつ d’|b ⇒ d’|d
条件(1)は公約数の条件であるのは定義1と同じである。
条件(2)は条件(1)を満たすもの(公約数)の集合における整除関係”|”(これは順序関係であった)に関する最大性を意味する。
自然数の場合はこの定義2と、もとの定義1が一致する。
例えば、上と同じa=12とb=8の例では、公約数が
1,2,4
であったが、確かに最大公約数4はどの公約数も約数に持つ。
1|4,2|4,4|4
一般の場合でも両定義は同値である。しかしその証明は後にしよう。今はこれを認めた上で、定義2を使って議論を進めよう。
さて、a,bの最大公約数(greatest common divisor)を
(a,b)
と書く。あるいは、もっと丁寧には
gcd(a,b)
と書くこともある。
なお、最大公約数は2つの自然数の組でなくても同様に定義される。3つ以上の場合、次のようになる:
3つ以上の有限個の自然数a,b,c,・・・について次の2条件を満たす自然数dをa,b,c,・・・の最大公約数という:
(1)d|a かつ d|b かつ d|c かつ ・・・
(2)d’|a かつ d’|b かつ d’|c かつ ・・・ ⇒ d’|d
やはり、このdを
(a,b,c,・・・)
と書く。あるいは、もっと丁寧には
gcd(a,b,c,・・・)
と書くこともある。
4.最大公約数の存在性
任意の2つの自然数の公約数は有限個であるから、通常の大小関係に関する公約数の最大値が存在する。それが定義1による最大公約数であるから、最大公約数が常に存在することがわかる。
そして2つの自然数の最大公約数の存在性から、3つ以上の自然数の最大公約数の存在も、次節の性質2によって2つずつを組にして帰納的に証明される。
5.最大公約数の諸性質
ここではのちの証明で使えるように、先に最大公約数の性質を3つ見ておこう。
【性質1】
有限個の自然数a,b,c,・・・の最大公約数は、それらの元の並び順は関係ない。例えば、
(a,b,c,・・・)=(a,c,b)=(b,c,a,・・・)=・・・
等が成り立つ。
これは定義より明らかである。
【性質2】
(a,b,c,・・・)=((a,b),c,・・・)
【証明】
左辺の値をd,右辺の値をeとおこう。d=eをいうのに、
d|e かつ e|d
(すなわちeとdは互いに同伴である)を示せばよい。
まずdの公約数性だから
d|a,d|b,d|c,・・・
である。そして最大公約数(a,b)の最大性によって
d|(a,b),d|c,・・・
とわかる。よって右辺の最大公約数の最大性によって
d|e
である。
次に、eの公約数性から
e|(a,b),e|c,・・・
である。特に
e|a,e|b,e|c,・・・
であるから左辺の最大公約数の定義によって
e|d
である。
左辺dと右辺eの両者は互いに割り合うから同伴である。自然数の同伴とは等号に他ならない。よって、
d=e
である。■
【性質3】
(ax,ay)=a(x,y)
【証明】
左辺をd,右辺の(x,y)をeとおく。d=aeをいうのに、
ae≦d かつ d≦ae
を示せばよい。
まず、
a|ax,a|ay
よりaは、axとayの公約数であるから
a|d
である。よって
d=at
となる自然数tがある。このとき、
(at)s=ax,(at)s’=ay
となる自然数s,s’が存在するから、aを消去して
ts=x,ts’=y
を得る。よって、
t|x,t|y
となり、tはxとyの公約数である。従ってeの最大性より
t|e
となる。よって、
d=at
≦ae ・・・①
一方、
ae|ax,ad|ay
であるからaeはaxとayの公約数である。よって、
ae|d
となり、
ae≦d ・・・②
となる。
①,②より、
d=ae
が示された。■
6.素数は素元である
ここでは素数の素元性を導こう。
pを任意の素数とする。2つの自然数a,bがともにpの倍数でないと仮定する:
自然数a,bについて、
p|aでない かつ p|bでない
このときpが積abで割り切れないこと:
p|abでない
を示せば(素元の定義の対偶が証明され)pが素元とわかる。
さて、仮定によってpとaの最大公約数は1である。実際、dをpとaの公約数:
d|p かつ d|a
とすると、dはpの約数で、pは素数(つまり既約元)であるからdはpまたは1と同伴である:
d~p または d~1
d~pであれば、d|aより
p|a
となって、最初の仮定の
p|aでない
に反する。
よって
d~1
となる。つまりpとaの最大公約数dは1である。
同様にしてpとbの最大公約数も1である。
これらのことから、pと積abの最大公約数も1であることが次のようにしてわかる。
(p,ab)=((p,pa),ab)
=(p,(pa,ab)) (∵性質2)
=(p,a(p,b)) (∵性質3)
=(p,a)
=1
よって、abはpの倍数ではない。
以上でpが素元であることがわかった。
7.結論
自然数の乗法の世界において、素因数分解の一意性は、
(Ⅱ)任意の自然数についてその約鎖条件を満足し(約鎖条件)
(Ⅲ)素数が素元である(素元条件)
ことによって証明された。
ただし、素数が素元であることは、
「自然数の最大公約数の定義について、定義1と定義2は同値である」
ということを認めた上で証明した。
従って、その証明を与えなければならない。その証明については後で考察しよう。
良ければサポート頂けますととても助かります。数学に関してより本質への追究と普及のための活動費として使わさせて頂きます。