もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君　MENU 　MENU

【数学】エラトステネスの篩を集合で表してみる

数学

170113_16

　某質問サイトを見て気になったため試してみました.

　合ってる…と思います.

 

 

解

　まず { \displaystyle \mathbb{N} } を正整数, { \displaystyle n } は { \displaystyle 2 } 以上の自然数とします.

 

　次に以下のような集合を考えます.

 

 { \displaystyle M(n) := n\mathbb{N}\backslash\{ n \} = \{2n, 3n, 4n,\dots\} }

 

つまり { \displaystyle M(n) } は { \displaystyle n } の正倍数の集合のうち, { \displaystyle n } 自身を取り除いたものです.

 

　定義から, 2以上の任意の自然数 { \displaystyle m, n } について次が成り立つのは直ぐに分かると思います.

 

 { \displaystyle M(mn) \subset M(n) }

 

　厳密には「真部分集合」の関係にあります.

　 { \displaystyle m=1 } の場合はトリビアルなのでわざわざ考えることもないでしょう(後編でちょっと違う理由で触れますが).

 

 

合成数の場合

　さて, { \displaystyle n } は必ず素数か合成数かのどちらかです, まず合成数である場合について考えます.

 

　任意の合成数 { \displaystyle m } は自分自身より小さい正約数の積で表すことができます, つまりある正整数 { \displaystyle s, t } が存在して

 

{ \displaystyle m=st }

 

ですね.

　そして { \displaystyle M(n) } の定義から

 

{ \displaystyle m=st\in M(s) \\ m=st\in M(t) }

 

の2式が成り立つことも明らかです.

 

　この2式が意味する所はなんでしょう？言ってしまえば

 

「任意の合成数 { \displaystyle m } は, 自身の任意の約数 { \displaystyle m' } における { \displaystyle M(m') } の要素である 」

 

ということです.

　これは更に突き詰めれば次のように言いかえられます.

 

「任意の合成数 { \displaystyle m } は, 自身の任意の素因数 { \displaystyle p } における { \displaystyle M(p) } の要素である 」

 

　今更ですが, { \displaystyle M(n) } はその定義から「nで篩ったもの」の集まりとも言えます.

　つまり { \displaystyle M(2), M(3), M(4),\dots } という感じで篩っているわけですね.

　従ってこれが意味するところは

 

 

「任意の合成数 { \displaystyle m } は, 自身の素因数のうち最小である { \displaystyle p } における { \displaystyle M(p) } で既に篩われている 」

 

 

ということです.

　更に言えば, 任意の合成数 { \displaystyle m } (最小の正素因数 { \displaystyle p } )は, { \displaystyle p-1 } 回目で篩われていることになります.

 

 

o

素数の場合

　では同じことを素数で考えてみましょう.

　任意の素数 { \displaystyle p } は, 可換性を省略すれば正整数について

 

{ \displaystyle p=1\times p }

 

の1通りでしか素因数因数分解できません.

　従って先程と同じように考えれば

 

 { \displaystyle p\in M(1) \\ p\in M(p) }

 

となります.

　しかし { \displaystyle M(1) } とは { \displaystyle \mathbb{N}\backslash\{1\} } ですからこんなもの当たり前の話ですし, そもそも { \displaystyle n\geq 2 } で考えていますから { \displaystyle M(1) } は除外されます.

　また { \displaystyle p\in M(p) } は { \displaystyle M(n) } の定義から明らかに成り立ちません.

　{ \displaystyle p } と互いに素な正整数 { \displaystyle q } における { \displaystyle M(q) } に { \displaystyle p } が含まれるなど以ての外, 従って

 

 

「任意の素数 { \displaystyle p } は, 1を除く任意の正整数 { \displaystyle n } における { \displaystyle M(n) } の要素でない 」

 

ということが言えます.

　従ってエラトステネスの篩はこれらの「篩い」から抜け出た要素のみ取りだすわけで, { \displaystyle M(n) } 達はその篩いにひっかかった数たちです,なので 結局求める集合 { \displaystyle P } は以下を成していると言えます.

 

 

 { \displaystyle P = (\mathbb{N}\backslash \{1\})\backslash \cup_{k=2}^{\infty}M(k) }

 

　{ \displaystyle M(n) } はこちらが勝手に作った記号なので戻すと

 

 

 { \displaystyle P = (\mathbb{N}\backslash\{1\})\backslash \cup_{k=2}^{\infty}(k\mathbb{N}\backslash\{k\}) }

 

 

〆

　つまり, 正しければこれが素数集合の別表現…ということになるわけですね.

 

　プログラミングのアルゴリズムに使えるような解釈には感じられませんね…

 

 

訂正

 

2017.01.14

　大まかに2箇所訂正しました.

(1)

　×：しかし { \displaystyle M(1) } とは { \displaystyle \mathbb{N} } 自身ですから

　○：しかし { \displaystyle M(1) } とは { \displaystyle \mathbb{N}\backslash\{1\} } ですから

 

(2)

　集合 { \displaystyle P } は素数をすべて集めた集合としていますから, { \displaystyle P = \mathbb{N}\backslash \cup_{k=2}^{\infty}M(k) } などの上記2式では1が含まれているため, 1を { \displaystyle \mathbb{N} } から予め取り除きました.

 

 

 

thetheorier