勉強時間の計測に時間時刻記録

2009年04月16日

素数かどうかを速く判定する方法


自然数nが素数かどうかを素数の定義に従って判定しようとすると
1より大きくn未満の自然数で割ってみなければなりません。

ところが全ての自然数は素数の積であらわせるから・・・@(証明は一番下)
そのうちの素数だけで割リ切れるかどうかを確かめればいいです。

しかし次の定理を使うともう少し楽になります。


「nが√n以下の素数で割り切れないならnは素数である」

このことを使って113が素数かどうかを判定してみよう。
100<113<121 なので
10<√113<11
よって√113以下の素数は2,3,5,7である。
113はこれらのどれでも割り切れないので素数である。


証明 

nが素数でないなら1より大きくn未満のある自然数s,tを用いて
n = st 
とあらわせる。
s > √n かつ t > √n とすると n = st > n となって矛盾するから
sまたはtは√n以下でなければならない。
よってs、tともに素数の積だからnは√n以下の素数で割り切れる。
すなわちnが素数でないならnは√n以下の素数で割り切れることが証明された。
この対偶より
nが√n以下の素数で割り切れないならnは素数である


証明終了




@の証明
nが素数の積であらわせないとすると
1より大きいある自然数s,tを用いて
n = st
とあらわせる。
nは素数の積で表せないないからsまたはtは素数でない。
よって同様にs、tのうち素数でないものを1より大きいある自然数の積で表せる。
nは素数の積で表せないのでこの操作を何度繰り返しても素数でないものがある。
よってnは2以上の自然数の無限個の積になってnより大きくなってしまう(n<2^nだから)ので矛盾である。


証明終了
タグ:素数

posted by qc at 17:12 | Comment(0) | その他 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
勉強時間の計測に時間時刻記録
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。