整数や素数の性質について、ちゃんと証明をしておこうというのが今回の目的になります。
証明する事柄は次の２つ。
１）素数は無限に存在すること
２）素因数分解はただ一通りしかないこと
では、いってみましょう。
１．背理法
証明の方法として、
・証明したいことの「否定」が正しいと仮定する
・そこから矛盾を引き出す
・それによって、もとの仮定が間違っていること、
つまり証明したいことが正しいことを結論する
厳密な数学としては色々問題があります。
ここではそういう難しすぎる話は置いておきます。
２．自然数の性質
自然数には最小の数１が存在します。
また、飛び飛びの値をとるので、x>2という範囲を考えたときに、
有理数のようにいくらでも２に近いが2ではない数、というものを考えることはできません。
つまり、
自然数の（空でない）部分集合には最小値が存在する
のです。これは重要な性質で今回の証明でも使います。
では、これらを踏まえて証明いってみましょう。
１）素数は無限にあることの証明
証明の流れ
（１）素数が有限、つまり最大値があることを仮定する
（２）その最大値より大きな素数が作れてしまうことを示す
（３）よって、最大値があるという仮定が間違っている＝無限にある、と結論
証明
素数がN個あり、最大の素数が存在すると仮定する。
すべての素数を列挙して、p1,p2,...pNとおく。
そこで次の数、
a = p1 × p2 × … × pN + 1
を考える。
この自然数aは、いま列挙したすべての素数で割ると必ず１余る。
つまり、どの素数もこの自然数aを割り切ることはできないので、これは素数になる。
a > pNより、aはpNよりも大きい素数となり、これは最初の仮定に反する。
したがって、素数には最大値がない。
つまり、素数は無限に存在する。
証明終
素数の個数に関しては次のようなものもあります。
ある整数x以下の素数の個数をπ(x)と書くことにしますと、
一番簡単な形での素数定理は、
π(x) ～ x/log(x)
というものでしょう。
なぜ素数の 個数がこのような関数で書かれるのかはかなり難しいですが、
これよりもより精度の高い式も考案されています。
２）素因数分解の一意性
つぎに、素因数分解がだた一通りにできるということを証明します。
これも背理法になります。
証明
いまNを少なくとも2通りの素因数分解に表せる最も小さい自然数とする。
これを
N = p1 p2 p3 ... p_i
N = q1 q2 q3 ... q_j
と2通りに表します。iとjはそれぞれ因数の個数です。
（１）2通りの表し方に同じ因数は存在しない
もし、同じ因数が存在したとき、それで割った数はNよりも小さく、
さらに2通りの素因数分解ができますから、これは仮定に反します。
（２）素因数の個数は2以上
もし素因数が1個ということは、その自然数は素数であるということになります。
これはpとqが異なる素数という仮定に反します。
（３）証明の本体
ここで、素因数を小さい順に並べます。
そして、もっとも小さい素因数が小さいほうをp1、大きいほうをq1としましょう。
このとき、
M = N -p1 q2 q3 ... q_j
という数を考えると、この数は、
M = (q1-p1) q2 q3 ... q_j
となります。このとき、(q1-p1)はp1の倍数ではありません。
もし倍数ならばq1もp1の倍数となり、これが素数であるという仮定に反するからです。
すなわち、このMの素因数分解にp1は含まれません。
一方、Nの素因数分解をもう一方で表せば、
M = p1(p2 p3 ... p_i - q2 q3 ... q_j)
となって、これはp1を素因数として含みますが、
これは上の素因数分解と異なる分解となるはずです（p1を含まないので）
そうすると、M<Nですから、MはNより小さい2通りの素因数分解ができる自然数となってしまい、
これは最初の仮定と反する結論になります。
したがって、素因数分解が2通り以上できる個数は存在しないことになります。
証明終
式が見づらいところについては後日修正します。
素因数分解の一意性の証明はほかにもまだたくさんあります。
興味のある方は調べてみるとおもしろいかもしれません。
それぞれが背景とする数学の性質の違いなどが分かります。
今日のところはこの辺で。
Powered by "Samurai Factory"