1素因数分解の一意性
今回証明する定理は図1-1です。
正の整数は素数の積で表せ、その表し方は積の順序を無視すれば1通りに限られる。
第3話で説明した、「素因数分解の一意性」と呼ばれる定理です。
1.1素因数分解の可能性の証明
まずは、「正の整数が必ず素数の積で表せる」という部分を証明しましょう。
「
」は、
個の素数の積で表せると定義することで、素数の積で表せると言えます。 このように適切に定義しておかないと、素因数分解の一意性が成り立たなくなるため、適切に定義しておきます。
」は、個の素数の積で表せると定義することで、素数の積で表せると言えます。 このように適切に定義しておかないと、素因数分解の一意性が成り立たなくなるため、適切に定義しておきます。
以上の整数については、背理法を使います。 以上の整数のうち、素数の積で表せない数があると仮定し、そのうち最小の数を
とします。 が素数だとすると、「」のように素数の積で表せてしまうため、は素数ではありません。素数でない数は、より大きくより小さい何らかの整数が割り切るため、はより大きくより小さい整数
を使って「
」と表せます。
より大きくより小さい何らかの整数が割り切るため、はより大きくより小さい整数を使って「」と表せます。仮定より、が素数の積で表せない「最小の数」だったため、よりもさらに小さいは素数の積で表せるはずです。 すると、はそれらの素数の積で表せることになりますが、は素数の積で表せない数だったため矛盾します。 よって、素数の積で表せない正の整数はありません。 (証明終)
が素数の積で表せない「最小の数」だったため、よりもさらに小さいは素数の積で表せるはずです。 すると、はそれらの素数の積で表せることになりますが、は素数の積で表せない数だったため矛盾します。 よって、素数の積で表せない正の整数はありません。 (証明終)1.2ベズーの補題の一部
さて次に、素因数分解の一意性を証明する準備として、図1-2の定理を証明します。
整数が互いに素ならば、
を満たす整数が存在する。
証明しましょう。
任意の整数に対し、が取りうる数全体の集合を
とします。 例えば、「
」などがの元です。 「」や「」もの元です。
に対し、が取りうる数全体の集合をとします。 例えば、「」などがの元です。 「」や「」もの元です。このとき、の2つの元を
とすると、任意の整数
について、「」もの元となります。 このことを「定理」と呼ぶことにします。
の2つの元をとすると、任意の整数について、「」もの元となります。 このことを「定理」と呼ぶことにします。なぜなら、「」「」とすると、「
」が成り立ち、「」の形になるからです。
」「」とすると、「」が成り立ち、「」の形になるからです。ここでの元のうち、より大きい最小の整数を
とします。
の元のうち、より大きい最小の整数をとします。このとき、の元の中にの倍数でない
が存在したと仮定します。 すると、第3話で説明した割り算の「商」と「余り」を使って、「
(
)」で表せます。 をで割った商をとして、余りをとしています。 式を変形して「」とすると、仮定よりはの元であり、定理よりもの元ですので、定理により「」()もの元になります。
の元の中にの倍数でないが存在したと仮定します。 すると、第3話で説明した割り算の「商」と「余り」を使って、「 ()」で表せます。 をで割った商をとして、余りをとしています。 式を変形して「」とすると、仮定よりはの元であり、定理よりもの元ですので、定理により「」()もの元になります。しかし、である整数がの元であることは、が「の元のうちより大きい最小の整数」としていたことと矛盾します。 よって背理法により、の元の中にの倍数でない数は存在せず、よっての元はすべての倍数でなければなりません。
である整数がの元であることは、が「の元のうちより大きい最小の整数」としていたことと矛盾します。 よって背理法により、の元の中にの倍数でない数は存在せず、よっての元はすべての倍数でなければなりません。前述の通りはそれぞれの元なので、はそれぞれの倍数になりますが、は互いに素なため、これを満たすにはでなければならず、従ってはの元です。 つまり「」はが取りうる数です。
はそれぞれの元なので、はそれぞれの倍数になりますが、は互いに素なため、これを満たすにはでなければならず、従ってはの元です。 つまり「」はが取りうる数です。よって、を満たす整数が存在します。 (証明終)
を満たす整数が存在します。 (証明終)1.3ユークリッドの補題
次に、もう一つ準備として、図1-3の定理を証明します。
素数が2つの整数の積を割り切るならば、はかの少なくとも1つを割り切る。
証明しましょう。
がを割り切るとし、このときがを割り切る場合と割り切らない場合で場合分けをします。がを割り切る場合、これは証明したい命題を満たします。素数がを割り切らない場合、割り切らないということはとは互いに素なので、先ほどの証明より、となる整数が存在します。
がを割り切らない場合、割り切らないということはとは互いに素なので、先ほどの証明より、となる整数が存在します。両辺にを掛けて、とします。 ここで左辺を見ると、はを割り切るため、はの倍数です。 また明らかにもの倍数です。 よって、の倍数同士を足した左辺はの倍数であるため、右辺のもの倍数です。
を掛けて、とします。 ここで左辺を見ると、はを割り切るため、はの倍数です。 また明らかにもの倍数です。 よって、の倍数同士を足した左辺はの倍数であるため、右辺のもの倍数です。従って、がを割り切るため、はかの少なくとも1つを割り切ることが分かります。 (証明終)
がを割り切るため、はかの少なくとも1つを割り切ることが分かります。 (証明終)1.4ユークリッドの補題の拡張
ちなみに、今証明したことを拡張して、図1-4が導出できます。
素数が、いくつかの整数
の積「」を割り切るならば、はの少なくとも1つを割り切る。
証明しましょう。
がを割り切るなら、は「」か「」の少なくとも1つを割り切ることは先ほど証明済みです。ここでが「」を割り切らない場合、「」を割り切ることになるので、同様に、は「」か「
」の少なくとも1つを割り切ることになります。
が「」を割り切らない場合、「」を割り切ることになるので、同様に、は「」か「」の少なくとも1つを割り切ることになります。これを回繰り返すと最終的に、は「」の少なくとも1つを割り切ることになります。 (証明終)
回繰り返すと最終的に、は「」の少なくとも1つを割り切ることになります。 (証明終)1.5素因数分解の一意性の証明
最後に、いよいよ、「正の整数は素数の積で表せ、その表し方は積の順序を無視すれば1通りに限られる」ことを証明します。
「正の整数は素数の積で表せる」ことは、既に証明しました。 残りの「その表し方は積の順序を無視すれば1通りに限られる」ことを証明しましょう。
まず、ある正の整数を、「」と「
」の2通りに素数の積で表せたとします。 のほうが
より多い場合には立場を入れ替えて、
となるようにしておきます。
」と「」の2通りに素数の積で表せたとします。 のほうがより多い場合には立場を入れ替えて、となるようにしておきます。このとき、「」ですので、「」の約数であるは、「」の約数でもあるため、「」を割り切ります。 よって先ほどの証明により、は「」のうち少なくとも1つを割り切ります。
」ですので、「」の約数であるは、「」の約数でもあるため、「」を割り切ります。 よって先ほどの証明により、は「」のうち少なくとも1つを割り切ります。は互いに入れ替えられるため、適宜入れ替えて、が割り切った数を改めてとします。は素数のため、を割り切る正の整数はかしかありません。 ここで素数(
)がを割り切るため、「」であることが分かります。「」の両辺を()で割ると、「」となります。 以上を回繰り返すことで、が得られます。
」の両辺を()で割ると、「」となります。 以上を回繰り返すことで、が得られます。ここでと仮定すると、最終的に両辺は、()で割って、「
」となりますが、これは「」がより大きいため成り立たず、よってではありません。 つまり、となります。
と仮定すると、最終的に両辺は、()で割って、「」となりますが、これは「」がより大きいため成り立たず、よってではありません。 つまり、となります。従って、「」と「」は同じ素数の積となるため、「正の整数は素数の積で表せ、その表し方は積の順序を無視すれば1通りに限られる」ことが成り立ちます。 (証明終)
」と「」は同じ素数の積となるため、「正の整数は素数の積で表せ、その表し方は積の順序を無視すれば1通りに限られる」ことが成り立ちます。 (証明終)