それにしても、なんだって素数というものに注目するのでしょう。
その一番の理由は、そう、素因数分解です。
どんな自然数も、素数の積として、順番を除いてただ一通りに表される、
という定理があるからです。
自然数 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 となり、
めでたく分解はただ一通りであることが分かります。
というわけで、素数の「素」は素材の「素」でもあるわけでした。
その一番の理由は、そう、素因数分解です。
どんな自然数も、素数の積として、順番を除いてただ一通りに表される、
という定理があるからです。
自然数 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 を引いてみると、
第一級の、主要な、最高の、重要な、根本的な、
といった意味がずらりと並んでいます。
ははあ。
ということは、素数というのは
「素敵な数」「素晴らしい数」ということなのかもしれません。
そんな素数の定義を復習しておくと、
１と自分自身以外に約数を持たない自然数のことを言うのでした。
一番小さな素数は２です。
実際、２以下の自然数がそもそも１と２の二つしかないので、
確かに２は素数になります。
その次に小さな素数は３です。
実際、３以下の自然数は１，２，３の三つで、
３を２で割ると１余るので、３は１と３しか約数に持たず、確かに素数です。
４は素数ではありません。１と４以外にも、２で割り切れるからです。
といった具合にして調べていくと、
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 が１と 97 以外に約数を持たないことを確かめなくてはいけませんが、
そのためには、２から 96 までの 95 個の自然数について
97 が割り切れないことを確かめなくてはならない…わけではありません。
だって、たとえば 97 が 96 なんかで割り切れないのは、
計算しなくったってほとんど自明です。
もう少し丁寧に見ると、
もし 97 が１でも 97 でもないある自然数ｄで割り切れたと仮定すると、
97÷ｄは１ではない自然数のはずなので（１になるのはｄ＝97のときだけです）、
不等式 97÷ｄ≧２ つまり ２ｄ≦97 が成り立つはずなので、
従って実際には２から 47 までの 46 個の自然数について
97 が割り切れないことを確かめれば十分です。
（97 が 48 以上の数で割りきれるはずがない！ということです）
いえいえ、もっと強いことが言えます。
もし 97 が１でも 97 でもない約数を持ったと仮定して、
そのような約数のうち最小のものをｄとしましょう。
このとき ｍ＝97÷ｄ は自然数ですが、97＝ｄ×ｍ なので
ｍも「１でも 97 でもない 97 の約数」になります。
すると、仮定より ｍ≧ｄ です。
従って 97＝ｄ×ｍ≧ｄ×ｄ つまり ｄ≦√97＜10 ということになります。
というわけで、実際には
２から９までの８個の自然数で97が割り切れないことを確かめれば、
それだけで 97 は素数でなくてはならないことが分かります。
更に言えば、
たとえば９で割り切れるならば３で割り切れているはずだし、
８で割り切れるならば２で割り切れているはずだし、
といった具合に考えると、
実際には 10 より小さい素数である
２，３，５，７の４つの数で割りきれなければ
97 は素数であると結論して良いことになります。
ね？
最初に思った「２から 96 までの 95 個」に比べると
ずいぶん少ない回数の割り算チェックで済むことが分かりましたよ。
今年もちょこちょこと書いていこう。
さてさて。
今回からしばらく、素数について書いてみようと思います。
特にプランがあるわけではないので行き当たりばったりです。
素数は英語では prime number と言います。
辞書で prime を引いてみると、
第一級の、主要な、最高の、重要な、根本的な、
といった意味がずらりと並んでいます。
ははあ。
ということは、素数というのは
「素敵な数」「素晴らしい数」ということなのかもしれません。
そんな素数の定義を復習しておくと、
１と自分自身以外に約数を持たない自然数のことを言うのでした。
一番小さな素数は２です。
実際、２以下の自然数がそもそも１と２の二つしかないので、
確かに２は素数になります。
その次に小さな素数は３です。
実際、３以下の自然数は１，２，３の三つで、
３を２で割ると１余るので、３は１と３しか約数に持たず、確かに素数です。
４は素数ではありません。１と４以外にも、２で割り切れるからです。
といった具合にして調べていくと、
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 が１と 97 以外に約数を持たないことを確かめなくてはいけませんが、
そのためには、２から 96 までの 95 個の自然数について
97 が割り切れないことを確かめなくてはならない…わけではありません。
だって、たとえば 97 が 96 なんかで割り切れないのは、
計算しなくったってほとんど自明です。
もう少し丁寧に見ると、
もし 97 が１でも 97 でもないある自然数ｄで割り切れたと仮定すると、
97÷ｄは１ではない自然数のはずなので（１になるのはｄ＝97のときだけです）、
不等式 97÷ｄ≧２ つまり ２ｄ≦97 が成り立つはずなので、
従って実際には２から 47 までの 46 個の自然数について
97 が割り切れないことを確かめれば十分です。
（97 が 48 以上の数で割りきれるはずがない！ということです）
いえいえ、もっと強いことが言えます。
もし 97 が１でも 97 でもない約数を持ったと仮定して、
そのような約数のうち最小のものをｄとしましょう。
このとき ｍ＝97÷ｄ は自然数ですが、97＝ｄ×ｍ なので
ｍも「１でも 97 でもない 97 の約数」になります。
すると、仮定より ｍ≧ｄ です。
従って 97＝ｄ×ｍ≧ｄ×ｄ つまり ｄ≦√97＜10 ということになります。
というわけで、実際には
２から９までの８個の自然数で97が割り切れないことを確かめれば、
それだけで 97 は素数でなくてはならないことが分かります。
更に言えば、
たとえば９で割り切れるならば３で割り切れているはずだし、
８で割り切れるならば２で割り切れているはずだし、
といった具合に考えると、
実際には 10 より小さい素数である
２，３，５，７の４つの数で割りきれなければ
97 は素数であると結論して良いことになります。
ね？
最初に思った「２から 96 までの 95 個」に比べると
ずいぶん少ない回数の割り算チェックで済むことが分かりましたよ。
昔、一時期はまっていたことがあるのです、フィボナッチ数列。
ねんのため復習しておくと、フィボナッチ数列というのは、漸化式
F(1)=F(2)=1, F(n+2)=F(n+1)+F(n)
によって定義される数列で、初めのほうは
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, ...
といった具合になっています。
これは色々な性質を満たすのだけれども、
昔私が気付いたこと（もちろん well-known な結果だけれども）
についてちょっと書いてみます。
フィボナッチ数列の持つ性質の一つとして、
m | n ならば F(m) | F(n)
というものがあります。
たとえば F(3)=2 なので、
F(3), F(6), F(9), F(12), ... などはすべて 2 で割り切れます。
同じように F(4)=3 なので
F(4), F(8), F(12), F(16), ... などはすべて 3 で割り切れます。
では、p を勝手な素数としたとき、
p | F(n) となるような自然数 n はいつでもあるでしょうか？
実はそのような自然数 n は必ず存在することが分かるのですが、
それらのうちで最小のものを n(p) と書くことにします。
たとえば 5 で割り切れる F(n) のうちで n が最小のものは F(5)=5 なので n(5)=5、
7 で割り切れる F(n) のうちで n が最小のものは F(8)=21 なので n(7)=8 といった具合。
いくつか例を挙げると、
n(2)=3, n(3)=4, n(5)=5, n(7)=8, n(11)=10, n(13)=7, ...
といった具合。
ここに某かの規則性を見出すことは出来るでしょうか？
実は、次のような性質があることが観察されます。
p≠5 ならば p≡±1 (mod n(p))
たとえば n(13)=7 なので 13≡-1 (mod 7) です。
この ±1 の規則性はどうやって決まっているのでしょうか。
そして、5 だけが例外なのはどうしてでしょうか。
この２つの問いは一度に解けて、実は次のようになっています。
【定理】任意の素数 p に対して p≡(5/p) (mod n(p)) が成り立つ。
ただし (m/p) はルジャンドルの記号を表す。
証明は、とても雑に言えば、
有限体 GF(p) でフィボナッチ数列を考えることで出来ます。
ねんのため復習しておくと、フィボナッチ数列というのは、漸化式
F(1)=F(2)=1, F(n+2)=F(n+1)+F(n)
によって定義される数列で、初めのほうは
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, ...
といった具合になっています。
これは色々な性質を満たすのだけれども、
昔私が気付いたこと（もちろん well-known な結果だけれども）
についてちょっと書いてみます。
フィボナッチ数列の持つ性質の一つとして、
m | n ならば F(m) | F(n)
というものがあります。
たとえば F(3)=2 なので、
F(3), F(6), F(9), F(12), ... などはすべて 2 で割り切れます。
同じように F(4)=3 なので
F(4), F(8), F(12), F(16), ... などはすべて 3 で割り切れます。
では、p を勝手な素数としたとき、
p | F(n) となるような自然数 n はいつでもあるでしょうか？
実はそのような自然数 n は必ず存在することが分かるのですが、
それらのうちで最小のものを n(p) と書くことにします。
たとえば 5 で割り切れる F(n) のうちで n が最小のものは F(5)=5 なので n(5)=5、
7 で割り切れる F(n) のうちで n が最小のものは F(8)=21 なので n(7)=8 といった具合。
いくつか例を挙げると、
n(2)=3, n(3)=4, n(5)=5, n(7)=8, n(11)=10, n(13)=7, ...
といった具合。
ここに某かの規則性を見出すことは出来るでしょうか？
実は、次のような性質があることが観察されます。
p≠5 ならば p≡±1 (mod n(p))
たとえば n(13)=7 なので 13≡-1 (mod 7) です。
この ±1 の規則性はどうやって決まっているのでしょうか。
そして、5 だけが例外なのはどうしてでしょうか。
この２つの問いは一度に解けて、実は次のようになっています。
【定理】任意の素数 p に対して p≡(5/p) (mod n(p)) が成り立つ。
ただし (m/p) はルジャンドルの記号を表す。
証明は、とても雑に言えば、
有限体 GF(p) でフィボナッチ数列を考えることで出来ます。
なんだかついつい堅めの話題ばかりになっちゃうので、
もうちょっと気楽に、日常的な数字の話をしてみるよ。
買い物に行って、たとえばお釣りが３１４円とかだったりすると、
思わず「おお、円周率だ！」とか思っちゃうことってないですか？
私はしょっちゅうです。
“キリ番”でない数字にもついつい反応してしまう、
そんな数字のうち、４桁のものをいくつか挙げてみます。
（買い物の総額でわりと目にする機会の多そうな桁数として４桁にしてみました）
★ ２のべき系統
１０２４ ２０４８ ４０９６ ８１９２
★ 昔覚えた語呂合わせ系統：平方根の近似値
１４１４ １７３２ ２２３６
★ 問題文中でよく見かけた数：常用対数の近似値（ややマニアックか？）
３０１０ ４７７１
★ 特別な定数の近似値：円周率、自然対数の底、黄金比
３１４１ ２７１８ １６１８
★ タクシーナンバー（ちなみに大山の標高も1729mです。トリビア。）
１７２９
もうちょっと気楽に、日常的な数字の話をしてみるよ。
買い物に行って、たとえばお釣りが３１４円とかだったりすると、
思わず「おお、円周率だ！」とか思っちゃうことってないですか？
私はしょっちゅうです。
“キリ番”でない数字にもついつい反応してしまう、
そんな数字のうち、４桁のものをいくつか挙げてみます。
（買い物の総額でわりと目にする機会の多そうな桁数として４桁にしてみました）
★ ２のべき系統
１０２４ ２０４８ ４０９６ ８１９２
★ 昔覚えた語呂合わせ系統：平方根の近似値
１４１４ １７３２ ２２３６
★ 問題文中でよく見かけた数：常用対数の近似値（ややマニアックか？）
３０１０ ４７７１
★ 特別な定数の近似値：円周率、自然対数の底、黄金比
３１４１ ２７１８ １６１８
★ タクシーナンバー（ちなみに大山の標高も1729mです。トリビア。）
１７２９
今野 浩：役に立つ一次式 ー 整数計画法「気まぐれな王女」の50年
日本評論社 (2005/11) 1900円＋税
与えられた連立一次不等式が定める凸領域内において
ある一次関数を最大化する点を求めよ、
というのが「線型計画法」と呼ばれる問題。
念頭に置いているのは、たとえば
「決められた予算内で事業の利益を最大化するには
どのように予算配分すべきか？」
といった類の「最適化」問題です。
そのヴァリエーションとして、特に変数の取りうる値の範囲を整数値に限って
最大値を与える点を求めるという問題が
サブタイトルにある「整数計画法」。
これはつまり、変数が「人数」「径路数」のような場合を想定しているわけだね。
この整数計画法における画期的な「美しい理論」が生まれ、注目を浴び、
しかし実用性の面から見捨てられ、後に再び息を吹き返して「役に立つ」という物語。
これは面白いなー！一気に読んでしまった。
確かに、こういう問題を考える上で線形代数は基本的な道具なんだよ、
ということを（歴史も含めて）お話として知っているだけでも、
訳も分からず勉強するよりは現実感があって身が入るかもしれないなー。
学部生の頃の自分に読ませたい度：★★★★★
日本評論社 (2005/11) 1900円＋税
与えられた連立一次不等式が定める凸領域内において
ある一次関数を最大化する点を求めよ、
というのが「線型計画法」と呼ばれる問題。
念頭に置いているのは、たとえば
「決められた予算内で事業の利益を最大化するには
どのように予算配分すべきか？」
といった類の「最適化」問題です。
そのヴァリエーションとして、特に変数の取りうる値の範囲を整数値に限って
最大値を与える点を求めるという問題が
サブタイトルにある「整数計画法」。
これはつまり、変数が「人数」「径路数」のような場合を想定しているわけだね。
この整数計画法における画期的な「美しい理論」が生まれ、注目を浴び、
しかし実用性の面から見捨てられ、後に再び息を吹き返して「役に立つ」という物語。
これは面白いなー！一気に読んでしまった。
確かに、こういう問題を考える上で線形代数は基本的な道具なんだよ、
ということを（歴史も含めて）お話として知っているだけでも、
訳も分からず勉強するよりは現実感があって身が入るかもしれないなー。
学部生の頃の自分に読ませたい度：★★★★★