閉じる


素数を判定する為のちょっとしたアイデア(ベータ版)

 

著者:茜町春彦

 

対象読者:整数論(素数)に興味のある人


1ページ

《はじめに》

与えられた数が素数であるかどうかを判定するための素数判定式を考案したので紹介します.

ただし、2と3は判定できません.取り敢えず、この二つの素数は例外とします.まあ、今更2と3が素数かどうかを考えても特に意味はなさそうなので、本質的な問題はないと思っています.

 

《素数判定する前の準備、その1》
まず自然数を下記のように、6つのグループに分けます.

 

P=6n+1
P=6n+2
P=6n+3
P=6n+4
P=6n+5
P=6n+6

 

Pは自然数です.nは0以上の整数です.

 

すると、
P=6n+2は、2の倍数なので全て合成数です.ただし、2は例外とします.
P=6n+3は、3の倍数なので全て合成数です.ただし、3は例外とします.
P=6n+4は、2の倍数なので全て合成数です.
P=6n+6は、6の倍数なので全て合成数です.

 

よって、素数は、P=6n+1またはP=6n+5のグループに属していることになります.(n=0、1、2、3、4、5・・・)


P=6n+1={1、7、13、19、25、31,37・・・}
P=6n+5={5、11、17、23、29、35,41・・・}



2ページ

《素数判定する前の準備、その2》

素数が二つのグループに分かれていると扱いづらいので、すべての素数がひとつのグループに属するように変換します.ちょっとトリッキーな手法を使います.

 

まずグループは、P=6n+1を使うことにします.

 

そして、nを全ての整数に拡張します.
つまり(n=0、±1、±2、±3、±4、±5・・・)と云う事です.

 

すると、
P=6n+1={・・・ -35、-29、-23、-17、-11、-5、1、7、13、19、25 ・・・}
となります.

 


ここで例えば、

n=-1の時、P=-5
n=-2の時、P=-11
n=-3の時、P=-17

のように、nが負数の場合にはPも負数になってしまいますが、これを強引に正の整数であると解釈することにします.つまり-5は5である、-11は11である、-17は17である、等々、と心の中で思うと云う事です.

 

本当は、絶対値をつけて
P=|6n+1|
とすればいいのでしょうが、そうすると絶対値を外すのに場合分けをしなければならなくなり、場合分けの記述が複雑になって書き示すのはちょっと大変なのです.そう云う事で絶対値は使わずに、負数を正数と見做すと云う事で対応したいと思います.

 

余談ですが、P=|6n+1|とP=|6n+5|の内容は同じなので、どちらのグループを使っても結果は同じになります.しかし6n+1の方が記述しやすいので、こちらを使うことにしました.


3ページ

《拡張したP=6n+1のグループに含まれるもの》

 

・・・ -65、-59、-53、-47、-41、-35、-29、-23、-17、-11、-5、1、7、13、19、25、31、37、43、49、55、61 ・・・

 

このグループには、1と素数と合成数が含まれています.従って、このグループから1と合成数を除けば、素数だけが残ることになります.

 

 

1はそのまま除外して終わりです.

そこで合成数の除き方を、次に考えることにします.


4ページ

《拡張したP=6n+1に含まれる合成数の除き方》

 

P=6n+1に含まれる合成数は、このグループの数同士の積になっていることを示します.

 

まず、PaとPbの二つの数を考えます.それは、
Pa=6k+1
Pb=6m+1
です.(kとmは0以外の整数とします)

 

そして、PaとPbの積を考えると、
Pa*Pb=(6k+1)*(6m+1)
=36mk+6k+6m+1
=6*(6mk+k+m)+1
となります.

 

ここで、
n=6mk+k+m
と置くと、

Pa*Pb=6n+1
となります.

 

つまり、Pa*Pbは6n+1のグループに属する合成数と云う事です.

 

従って、6n+1のグループの中からPa*Pbを見付け出して除外すれば、素数が残ると云う事です.

 


例えば、
7*7=49
-5*7=-35
-5*-11=55
などを除外すると云う事です.



読者登録

茜町春彦さんの更新情報・新作情報をメールで受取りますか?(読者登録について