茜町BOOKS

絵本とかエッセイとか

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

《はじめに》

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

 

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

ただし、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・・・}

 

f:id:akanemachi:20190710172725p:plain

 


素数判定する前の準備、その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 ・・・}
となります.

 

f:id:akanemachi:20190710172820p:plain


ここで例えば、
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と合成数を除けば、素数だけが残ることになります.

 

f:id:akanemachi:20190710172912p:plain

 

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を見付け出して除外すれば、素数が残ると云う事です.

 

f:id:akanemachi:20190710173039p:plain


例えば、
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で現れる事を示しています.

 

f:id:akanemachi:20190710173107p:plain


ここで周期性があることから、或るアイデアを思い付きました.それは三角関数を応用して、与えられた数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で現れています.

 

f:id:akanemachi:20190710173151p:plain


ここで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で現れています.

 

f:id:akanemachi:20190710173212p:plain


ここで-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は素数と判定できます.

 

f:id:akanemachi:20190710173314p:plain

 

 

 


例えば、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は素数と判定できます.(心の中で負号は外します)

 

f:id:akanemachi:20190710173340p:plain

 

 

 


例えば、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は合成数と判定できます.

 

f:id:akanemachi:20190710173402p:plain

 

 

素数を判定する手順としては、以上で終わりなのですが、これを一般化した数式をチョット思いついたので、それを次に示してみます.

 

 

素数判定式》
P=6n+1の時、Pが素数かどうかを判定する数式を考えます.

まず、Pより絶対値が小さい数は{-5、7、-11、13、-17 ・・・ 6n-11、-6n+7、6n-5、-6n+1}です.

Pがこれらの小さな数の倍数でなければ、Pは素数です.

ここで、前述の倍数かどうかを判定する三角関数を使います.

繰り返しの説明になりますけれど、Pが-5の倍数かどうかの判定は、次の式の計算結果から判定します.
y=sin((P+5)÷(-30))π
y=0ならPは-5の倍数です.y≠0なら倍数ではありません.

Pが7の倍数かどうかの判定は、次の式を計算して、y=0ならPは7の倍数です.y≠0なら倍数ではありません.
y=sin((P-7)÷42)π

Pが-11の倍数かどうかの判定は、次の式を計算して、y=0ならPは-11の倍数です.y≠0なら倍数ではありません.
y=sin((P+11)÷(-66))π

この後もPが13、-17、19、-23、25 ・・・ 6n-5、-6n+1まで、同様に考えます.

Pが6n-5の倍数かどうかの判定は、次の式を計算して、y=0ならPは6n-5の倍数です.y≠0なら倍数ではありません.
y=sin((P-6n+5)÷(36n-30))π

Pが-6n+1の倍数かどうかの判定は、次の式を計算して、y=0ならPは-6n+1の倍数です.y≠0なら倍数ではありません.
y=sin((P+6n-1)÷(-36n+6))π


そして、上記のy全ての積を作れば、いっぺんに結果が出せると思ったのです.そこで、次の数式を考えました.


Y=sin((P+5)÷(-30))π*sin((P-7)÷42)π*sin((P+11)÷(-66))π*sin((P-13)÷78)π ・・・・・・ sin((P-(6n-5))÷(36n-30))π*sin((P-(-6n+1))÷(-36n+6))π

 

f:id:akanemachi:20190710173432p:plain

 


この数式Yが素数判定式です.

与えられた数Pを右辺に代入して、Y=0となればPは合成数です.

Y≠0であればPは素数であると判定します.Pが、Pより小さい数の倍数になっていないからです.

 

 

例えばP=91の場合:

91より小さい数は、-5、7、-11、13、-17、19、-23、25、-29、31、-35、37、-41、43、-47、49、-53、55、-59、61、-65、67、-71、73、-77、79、-83、85、-89です.

よって、素数判定式は次の通りです.

Y=sin((91+5)÷(-30))π*sin((91-7)÷42)π*sin((91+11)÷(-66))π*sin((91-13)÷78)π*sin((91+17)÷(-102))π*sin((91-19)÷114)π*sin((91+23)÷(-138))π*sin((91-25)÷150)π*sin((91+29)÷(-174))π*sin((91-31)÷186)π*sin((91+35)÷(-210))π*sin((91-37)÷222)π*sin((91+41)÷(-246))π*sin((91-43)÷258)π*sin((91+47)÷(-282))π*sin((91-49)÷294)π*sin((91+53)÷(-318))π*sin((91-55)÷330)π*sin((91+59)÷(-354))π*sin((91-61)÷366)π*sin((91+65)÷(-390))π*sin((91-67)÷402)π*sin((91+71)÷(-426))π*sin((91-73)÷438)π*sin((91+77)÷(-462))π*sin((91-79)÷474)π*sin((91+83)÷(-498))π*sin((91-85)÷510)π*sin((91+89)÷(-534))π

計算結果は、Y=0となるので、91は合成数と判定します.

 

f:id:akanemachi:20190710173517p:plain

 

 

 

例えばP=-29の場合:

-29より小さい数は、-5、7、-11、13、-17、19、-23、25です.

よって、素数判定式は次の通りです.

Y=sin((-29+5)÷(-30))π*sin((-29-7)÷42)π*sin((-29+11)÷(-66))π*sin((-29-13)÷78)π*sin((-29+17)÷(-102))π*sin((-29-19)÷114)π*sin((-29+23)÷(-138))π*sin((-29-25)÷150)π

計算結果は、Y=0.008255・・・となります.

Y≠0なので、-29は素数と判定します.
(-29は29と解釈してください)

 

f:id:akanemachi:20190710173541p:plain

 

 

《この判定式の問題点》
数式Yは、このままでは計算に手間がかかります.多分、エラトステネスの篩をつかって素数判定を行なうよりも手間がかかるでしょう.

そこで、数式Yがsinの積になっているので、倍角の公式を応用するとか、複素関数を応用すれば簡略化できるような気がしたんですけども、どうも上手く行かないんですね.それで、今のところ手詰まり状態です.と云う事で、今回はここまでとします.なにか閃いたら別途記事を投稿します.
(了)


―― 奥付 ――
題名:素数を判定する為のちょっとしたアイデア(ベータ版)
著者:茜町春彦

タグ:#素数 #整数論 #合成数 #素因数分解 #リーマン予想 #素数定理