わりと好きかもしれません。

お気に入りの数学の話題について、ぽつりぽつりと書きつづっていければと思います。

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
それにしても、なんだって素数というものに注目するのでしょう。
その一番の理由は、そう、素因数分解です。
どんな自然数も、素数の積として、順番を除いてただ一通りに表される、
という定理があるからです。

自然数 n に対して、もし n 自身が素数ならばそこでおしまい、
もし素数でなければ n は 1 でも n でもない約数 d を持つので、
ある自然数 m が存在して n=dm と書けます。
ここで、もし d も m も素数ならばここでおしまい、
もしそうでなければ、おのおのについて同じことを繰り返すことで
いつかは素数の積にまで分解するでしょう、というのが
「素因数分解の存在」の理屈。
これはちょうど、素因数分解の再帰的なアルゴリズムの説明にもなっています。

ではでは、素因数分解は順番を除いてただ一通りであることの証明は?
n=p_1^{e_1}...p_k^{e_k}=q_1^{f_1}...q_m^{f_m}
と二通りに分解したと仮定します。
このとき、p_1 は右辺を割り切ることから、
p_1 は q_i のいずれかと一致しなければなりません。
というのも、素数 p が積 ab を割り切るならば、
a か b のいずれかは p で割り切れなくてはならないからです。
(この事実がネック。もちろん証明が必要)
この理屈を重ねていくことで、k=m かつ適当に並び替えることで
p_i=q_i としてよい、ということが分かり、
あとは一方の分解が他方の分解を割り切ることから
e_i≧f_i かつ e_i≦f_i で、e_i=f_i となり、
めでたく分解はただ一通りであることが分かります。

というわけで、素数の「素」は素材の「素」でもあるわけでした。
スポンサーサイト
年が明けてずいぶんたってしまいました。
今年もちょこちょこと書いていこう。

さてさて。
今回からしばらく、素数について書いてみようと思います。
特にプランがあるわけではないので行き当たりばったりです。

素数は英語では prime number と言います。
辞書で prime を引いてみると、
第一級の、主要な、最高の、重要な、根本的な、
といった意味がずらりと並んでいます。
ははあ。
ということは、素数というのは
「素敵な数」「素晴らしい数」ということなのかもしれません。

そんな素数の定義を復習しておくと、
1と自分自身以外に約数を持たない自然数のことを言うのでした。

一番小さな素数は2です。
実際、2以下の自然数がそもそも1と2の二つしかないので、
確かに2は素数になります。
その次に小さな素数は3です。
実際、3以下の自然数は1,2,3の三つで、
3を2で割ると1余るので、3は1と3しか約数に持たず、確かに素数です。
4は素数ではありません。1と4以外にも、2で割り切れるからです。
といった具合にして調べていくと、

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

などが素数であることが分かります。
実は、100 以下の素数はこれで全部です。
こうして結果だけを書くと「ふうん」というぐらいのものですが、
たとえば 97 が素数であることを確かめるのはどれぐらい大変でしょうか。

97 が1と 97 以外に約数を持たないことを確かめなくてはいけませんが、
そのためには、2から 96 までの 95 個の自然数について
97 が割り切れないことを確かめなくてはならない…わけではありません。

だって、たとえば 97 が 96 なんかで割り切れないのは、
計算しなくったってほとんど自明です。
もう少し丁寧に見ると、
もし 97 が1でも 97 でもないある自然数dで割り切れたと仮定すると、
97÷dは1ではない自然数のはずなので(1になるのはd=97のときだけです)、
不等式 97÷d≧2 つまり 2d≦97 が成り立つはずなので、
従って実際には2から 47 までの 46 個の自然数について
97 が割り切れないことを確かめれば十分です。
(97 が 48 以上の数で割りきれるはずがない!ということです)

いえいえ、もっと強いことが言えます。

もし 97 が1でも 97 でもない約数を持ったと仮定して、
そのような約数のうち最小のものをdとしましょう。
このとき m=97÷d は自然数ですが、97=d×m なので
mも「1でも 97 でもない 97 の約数」になります。
すると、仮定より m≧d です。
従って 97=d×m≧d×d つまり d≦√97<10 ということになります。
というわけで、実際には
2から9までの8個の自然数で97が割り切れないことを確かめれば、
それだけで 97 は素数でなくてはならないことが分かります。

更に言えば、
たとえば9で割り切れるならば3で割り切れているはずだし、
8で割り切れるならば2で割り切れているはずだし、
といった具合に考えると、
実際には 10 より小さい素数である
2,3,5,7の4つの数で割りきれなければ
97 は素数であると結論して良いことになります。

ね?
最初に思った「2から 96 までの 95 個」に比べると
ずいぶん少ない回数の割り算チェックで済むことが分かりましたよ。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。