忍者ブログ
CUDA+GPGPU、C++、C#などのプログラムについての備忘録がわり
[92] [91] [90] [89] [88] [87] [86] [85] [83] [82] [81
Posted by - 2019.11.23,Sat
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

Posted by サンマヤ - 2014.02.17,Mon
約数と素数の話、第3回はちょっと専門的な話になります。
整数や素数の性質について、ちゃんと証明をしておこうというのが今回の目的になります。
証明する事柄は次の2つ。
1)素数は無限に存在すること
2)素因数分解はただ一通りしかないこと

では、いってみましょう。


証明に入る前に、次の2つが使えることは前提とします。

1.背理法
 証明の方法として、

・証明したいことの「否定」が正しいと仮定する

・そこから矛盾を引き出す

・それによって、もとの仮定が間違っていること、
つまり証明したいことが正しいことを結論する

という手法を「背理法」といい、数学の証明方法として非常に強力な手段となっています。
ただし、これは「否定の否定は肯定になる」という「排中律」というルールを認めることと同じで、
厳密な数学としては色々問題があります。
ここではそういう難しすぎる話は置いておきます。

2.自然数の性質

自然数には最小の数1が存在します。
また、飛び飛びの値をとるので、x>2という範囲を考えたときに、
有理数のようにいくらでも2に近いが2ではない数、というものを考えることはできません。
つまり、
自然数の(空でない)部分集合には最小値が存在する
のです。これは重要な性質で今回の証明でも使います。

では、これらを踏まえて証明いってみましょう。



1)素数は無限にあることの証明
証明の流れ
(1)素数が有限、つまり最大値があることを仮定する
(2)その最大値より大きな素数が作れてしまうことを示す
(3)よって、最大値があるという仮定が間違っている=無限にある、と結論

証明
素数がN個あり、最大の素数が存在すると仮定する。
すべての素数を列挙して、p1,p2,...pNとおく。
そこで次の数、
a = p1 × p2 × … × pN + 1
を考える。
この自然数aは、いま列挙したすべての素数で割ると必ず1余る。
つまり、どの素数もこの自然数aを割り切ることはできないので、これは素数になる。
a > pNより、aはpNよりも大きい素数となり、これは最初の仮定に反する。
したがって、素数には最大値がない。
つまり、素数は無限に存在する。
証明終


素数の個数に関しては次のようなものもあります。
ある整数x以下の素数の個数をπ(x)と書くことにしますと、
一番簡単な形での素数定理は、
π(x) ~ x/log(x)
というものでしょう。
なぜ素数の 個数がこのような関数で書かれるのかはかなり難しいですが、
これよりもより精度の高い式も考案されています。

2)素因数分解の一意性
つぎに、素因数分解がだた一通りにできるということを証明します。
これも背理法になります。

証明
いまNを少なくとも2通りの素因数分解に表せる最も小さい自然数とする。
これを
N = p1 p2 p3 ... p_i
N = q1 q2 q3 ... q_j
と2通りに表します。iとjはそれぞれ因数の個数です。

(1)2通りの表し方に同じ因数は存在しない
 もし、同じ因数が存在したとき、それで割った数はNよりも小さく、
さらに2通りの素因数分解ができますから、これは仮定に反します。

(2)素因数の個数は2以上
もし素因数が1個ということは、その自然数は素数であるということになります。
これはpとqが異なる素数という仮定に反します。

(3)証明の本体
ここで、素因数を小さい順に並べます。
そして、もっとも小さい素因数が小さいほうを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通り以上できる個数は存在しないことになります。
証明終


式が見づらいところについては後日修正します。
素因数分解の一意性の証明はほかにもまだたくさんあります。
興味のある方は調べてみるとおもしろいかもしれません。
それぞれが背景とする数学の性質の違いなどが分かります。

今日のところはこの辺で。

PR
Comments
Post a Comment
Name :
Title :
E-mail :
URL :
Comments :
Pass :   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
カレンダー
10 2019/11 12
S M T W T F S
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
フリーエリア
最新コメント
[11/19 矢野 忠]
[02/25 山本義和]
[07/08 hirota]
[07/06 hirota]
[02/05 矢野 忠]
最新トラックバック
プロフィール
HN:
サンマヤ
性別:
非公開
職業:
プログラマ
趣味:
ゲーム
バーコード
ブログ内検索
カウンター
忍者アナライズ
Template by mavericyard*
Powered by "Samurai Factory"
忍者ブログ [PR]