1人が本棚に入れています
本棚に追加
/2ページ
ページ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》
素数が二つのグループに分かれていると扱いづらいので、すべての素数がひとつのグループに属するように変換します.ちょっとトリッキーな手法を使います.
まずグループは、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の方が記述しやすいので、こちらを使うことにしました.
《拡張した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はそのまま除外して終わりです.
そこで合成数の除き方を、次に考えることにします.
《拡張した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
などを除外すると云う事です.
《具体例:7の倍数》
P=6n+1のグループに属していて、7の倍数となっている合成数をPcとします.
つまり、
Pc=7*(6n+1)
=42n+7
と云う事です.ここで、nは整数です.
すると、
n=0の時にPc=7で素数となりますが、
n=±1、±2、±3、±4、±5・・・の時には、Pcは全て7の倍数であり、従って全て合成数です.
例えば、
n=1の時、Pc=49
n=2の時、Pc=91
n=3の時、Pc=133
n=-1の時、Pc=-35
n=-2の時、Pc=-77
n=-3の時、Pc=-119
などです.
この事実から逆に、与えられた数Pが7の倍数かどうかを判定する方法を考えてみます.
P=42n+7
の数式をnについて変形しますと、
n=(P-7)÷42
が得られます.
nは整数なので、Pが7の倍数であれば、右辺は割り切れて商に余りは出ないはずです.
右辺の商に余りが出たら、Pは7の倍数ではないという事です.
例えば、P=49の場合、
n=(49-7)÷42=1
となり、割り切れているので、49は7の倍数です.
例えば、P=55の場合、
n=(55-7)÷42=1余り6
となり、割り切れないので、55は7の倍数ではありません.
例えば、P=-35の場合、
n=(-35-7)÷42=-1
となり、割り切れているので、-35は7の倍数です.
これは、どう云う事かというと、P=6n+1のグループの中で7の倍数は周期42で現れる事を示しています.
ここで周期性があることから、或るアイデアを思い付きました.それは三角関数を応用して、与えられた数Pが7の倍数かどうかを判定する、と云うアイデアです.ちょっと、トリッキーなんですけどね.
数式で示すと、
y=sin((P-7)÷42)π
と云うものです.ここでπは3.14ラジアン(180度)のことです.
この式では、Pが7の倍数の時だけ、yは0になります.
つまり、数式yが0になるか、どうかで、Pが7の倍数なのか違うのかが判定できると云う事です.
《具体例:13の倍数》
P=6n+1のグループに属していて、13の倍数となっている合成数をPdとします.
つまり、
Pd=13*(6n+1)
=78n+13
と云う事です.ここで、nは整数です.
すると、
n=0の時にPd=13で素数となりますが、
n=±1、±2、±3、±4、±5・・・の時には、Pdは13の倍数であり、従って全て合成数です.
例えば、
n=1の時、Pd=91
n=2の時、Pd=169
n=3の時、Pd=247
n=-1の時、Pd=-65
n=-2の時、Pd=-143
n=-3の時、Pd=-221
などです.
逆に、与えられた数Pが13の倍数かどうかを判断してみます.
P=78n+13
の数式を変形しますと、
n=(P-13)÷78
が得られます.
nは整数なので、Pが13の倍数であれば、右辺は割り切れて商に余りは出ないはずです.
右辺の商に余りが出たら、Pは13の倍数ではないと云う事です.
例えば、P=247の場合、
n=(247-13)÷78=3
となり、割り切れているので、247は13の倍数です.
例えば、P=325の場合、
n=(325-13)÷78=4
となり、割り切れているので、325は13の倍数です.
例えば、P=-209の場合、
n=(-209-13)÷78=-2余り-66
となり、割り切れないので、-209は13の倍数ではありません.
また、P=6n+1のグループの中で、13の倍数は周期78で現れています.
ここで13の倍数かどうかを判定する数式を示すと、
y=sin((P-13)÷78)π
となります.πは3.14ラジアン(180度)です.
Pが13の倍数の時だけ、yは0になります.
数式yが0になるか、どうかで、Pが13の倍数なのか違うのかが判定できます.
《具体例:-5の倍数》
P=6n+1のグループに属していて、-5の倍数となっている合成数をPeとします.
つまり、
Pe=-5*(6n+1)
=-30n-5
と云う事です.ここで、nは整数です.
すると、
n=0の時にPe=-5で素数となります.(心の中で負号を外してください)
n=±1、±2、±3、±4、±5・・・の時には、Peは全て-5の倍数であり、また合成数でもあります.
例えば、
n=1の時、Pe=-35
n=2の時、Pe=-65
n=3の時、Pe=-95
n=-1の時、Pe=25
n=-2の時、Pe=55
n=-3の時、Pe=85
などです.
逆に、与えられた数Pが-5の倍数かどうかを判断してみます.
P=-30n-5
の数式を変形しますと、
n=(P+5)÷(-30)
が得られます.
nは整数なので、Pが-5の倍数であれば、右辺は割り切れて商に余りは出ないはずです.
右辺の商に余りが出たら、Pは-5の倍数ではないと云う事です.
例えば、P=247の場合、
n=(247+5)÷(-30)=-8余り12
となり、割り切れないので、247は-5の倍数ではありません.
例えば、P=325の場合、
n=(325+5)÷(-30)=-11
となり、割り切れているので、325は-5の倍数です.
例えば、P=-209の場合、
n=(-209+5)÷(-30)=6余り-24
となり、割り切れないので、-209は-5の倍数ではありません.
また、P=6n+1のグループの中で、-5の倍数は周期30で現れています.
ここで-5の倍数かどうかを判定する数式を示すと、
y=sin((P+5)÷(-30))π
となります.πは3.14ラジアン(180度)です.
Pが-5の倍数の時だけ、yは0になります.
数式yが0になるか、どうかで、Pが-5の倍数なのか違うのかが判定できます.
《素数判定の具体例》
与えられた数をPとします.
P=6n+1の時、PがPより小さい数の倍数でなければ、Pは素数です.(Pより小さいとは、絶対値が小さいと云う意味です)
例えば、P=13が素数か、どうかを判定してみます.
13より小さい数は、-5と7とー11なので、前述の三角関数を使って示すと、
y=sin((P+5)÷(-30))π*sin((P-7)÷42)π*sin((P+11)÷(-66))π
となります.この式のPに13を代入してyを求めますと、
y=0.254・・・
となり、y≠0なので、Pは-5の倍数でも7の倍数でも-11の倍数でもありません.
従ってP=13は素数と判定できます.
例えば、P=-17が素数か、どうかを判定してみます.
-17より小さい数は、-5と7とー11と13なので、数式で示すと、
y=sin((P+5)÷(-30))π*sin((P-7)÷42)π*sin((P+11)÷(-66))π*sin((P-13)÷78)π
となります.この式のPに-17を代入してyを求めますと、
y=0.244・・・
となり、y≠0なので、Pは-5の倍数でも7の倍数でも-11の倍数でも13の倍数でもありません.
従ってP=-17は素数と判定できます.(心の中で負号は外します)
例えば、P=25が素数か、どうかを判定してみます.
25より小さい数は、-5と7とー11と13とー17と19と-23なので、数式で示すと、
y=sin((P+5)÷(-30))π*sin((P-7)÷42)π*sin((P+11)÷(-66))π*sin((P-13)÷78)π*sin((P+17)÷(-102))π*sin((P-19)÷114)π*sin((P+23)÷(-138))π
となります.この式のPに25を代入してyを求めますと、
y=0
となるので、Pは-5と7とー11と13とー17と19の中のどれかの倍数なっている事が分かります.
従ってP=25は合成数と判定できます.
素数を判定する手順としては、以上で終わりなのですが、これを一般化した数式をチョット思いついたので、それを次に示してみます.
最初のコメントを投稿しよう!