閉じる


エッセイ(数学)
『素数判定方程式』
著者:茜町春彦

 

概要:
素数を判定するための方程式(ディオファントス方程式)を紹介します.
つづいて、その導き方と使い方を説明します.ただし、2と3が素数かどうかをこの方程式では判定できませんが、これらを今さら判定しても意味は無いので、2と3は例外とします.また証明は行なっておりません.ご了承ください.

 

読者対象:
整数論やRSA暗号に興味のある方.

 

目次:

素数判定方程式、P=36mn+6m+6n+1の概略

素数判定方程式の導き方を説明します(その一)

素数判定方程式の導き方を説明します(その二)

素数判定方程式の使い方を説明します

 

計算例、P=169の場合

図式解法:P=169の場合

グラフ:P=169の場合

 

計算例、P=97の場合

図式解法:P=97の場合

グラフ:P=97の場合

 

計算例、P=101の場合

図式解法:P=101の場合

グラフ:P=101の場合

 

計算例、P=187の場合

図式解法:P=187の場合

グラフ:P=187の場合

 

計算例、P=741の場合

図式解法:P=247の場合

グラフ:P=247の場合

 

素数判定方程式の実用性について

後書き

奥付


素数判定方程式、P=36mn+6m+6n+1の概略

素数判定方程式を示して、概略を説明します.
(導き方と使い方は後述します.また素数2と素数3は除外します)

 

P=36mn+6m+6n+1

 

Pには、素数かどうかを判定したい数を代入します.
mとnは、変数です.

 

この素数判定方程式に、或る数Pを与えて、mとnの整数解を求めます.その結果により、Pが素数かどうかを判定します.

 

判定基準は、mとnの整数解が共に0以外であれば、Pは合成数と判定します.
なぜなら、
P=36mn+6m+6n+1=(6m+1)×(6n+1)
となり、Pが素因数分解できるからです.

 

mとnの整数解が共に0になるのは、P=1の場合だけです.
なぜなら、
P=36×0×0+6×0+6×0+1=1
となるからです.

 

上記以外の場合、つまり、mとnの片方だけが0となる整数解しかない場合、Pは素数と判定します.
P=(36m×0)+6m+(6×0)+1=6m+1
または
P=(36×0×n)+(6×0)+6n+1=6n+1
となり、素因数分解ができないからです.

 

例として、91が素数か合成数かを判定してみます.
素数判定方程式のPに91を代入します.

 

91=36mn+6m+6n+1

 

この式の整数解を求めると、(m、n)=(1、2)があります.
整数解が共に0以外なので、Pは合成数であり、素因数分解ができます.
P=(6m+1)×(6n+1)
91=(6×1+1)×(6×2+1)=7×13
となります.


素数判定方程式の導き方を説明します(その一)

すべての素数が |6N+1| の形で表せることを示します.
(N=0、±1、±2、±3、±4、・・・)
(記号| |は絶対値を表します)

 

まず、整数を六つに分類します.
6で割ったときの余りに基づいて分類します.
つまり、6N、6N+1、6N+2、6N+3、6N+4、6N+5の六つの分類です.

 

6N  : ・・・、-18、-12、-6、0、 6、12、18、24、・・・
6N+1: ・・・、-17、-11、-5、1、 7、13、19、25、・・・
6N+2: ・・・、-16、-10、-4、2、 8、14、20、26、・・・
6N+3: ・・・、-15、 -9、-3、3、 9、15、21、27、・・・
6N+4: ・・・、-14、 -8、-2、4、10、16、22、28、・・・
6N+5: ・・・、-13、 -7、-1、5、11、17、23、29、・・・

 

ここで絶対値を取ってみると:
|6N|                  6の倍数 (素数ではない)
|6N+1|                素数または合成数
|6N+2|=|2×(3N+1)|   2の倍数 (素数ではない)
|6N+3|=|3×(2N+1)|   3の倍数 (素数ではない)
|6N+4|=|2×(3N+2)|   2の倍数 (素数ではない)
|6N+5|                素数または合成数
となります.

 

|6N|と|6N+2|と|6N+3|と|6N+4|は、偶数または3の倍数となるので、素数ではありません.

 

従って素数は、|6N+1|もしくは|6N+5|の形となります.

 

|6N+1| ・・・、|ー17|、|ー11|、|-5|、1、 7、13、19、25、・・・

 

|6N+5| ・・・、|-25|、|ー19|、|-13|、 |-7|、|-1|、5、11、17、・・・

 

|6N+1|と|6N+5|の内容は全く同じであることから、どちらか一方を考察するだけで素数の判定ができます.このエッセイに於いては、|6N+1|を使って考察を行なうことにします.

 

また絶対値をつけたままで考察を続けても構わないのですが、計算式の取り扱いをさらに単純化するために、|6N+1|から絶対値の記号を外して考察をすることにします.そのかわり、負号は無視することにします.例えば、「-5」は「5」と見なし、「-11」は「11」と見なし、「-35」は「35」などと見なすと云うことです.

 

繰り返して言いますと、負号を無視すると全ての素数は、6N+1の形に表せると云うことです.


P=6N+1、(N=0、±1、±2、±3、±4、・・・)

 

・・・、-29、-23、-17、-11、-5、1、 7、13、19、25、31、37、43,49、55,61、・・・

 


素数判定方程式を導き方を説明します(その二)

6N+1 の形の整数同士の積も、6N+1 の形で表せることを示します.

 

まず、ふたつの6N+1 の形の整数を考えます.


P’=6m+1
P’’=6n+1
(m、n=0、±1、±2、±3、±4、・・・)

 

そして、P’とP’’の積を考えます.
P’×P’’=(6m+1)×(6n+1)=36mn+6m+6n+1=6×(6mn+m+n)+1
となります.

 

ここで、(6mn+m+n)をNと置きます.

すると、
P’×P’’=6N+1
となります.


つまり、6N+1の形の整数同士の積もまた6N+1の形になっている事が分かります.
P’×P’’=6N+1=P=36mn+6m+6n+1
と云うことです.

 

この右辺の二つの項を、素数判定方程式と呼ぶことにします.
P=36mn+6m+6n+1
です.


素数判定方程式の使い方を説明します

素数判定方程式
P=36mn+6m+6n+1
の使い方を説明します.

 

素数かどうかを判定したい数をPとします.


まず、Pを6で割ったときの余りを求めます.

 

その結果、余りが1であればPを素数判定方程式に代入して、mとnの整数解を求めます.
余りが5であれば、Pに負号をつけたものを素数判定方程式に代入して、mとnの整数解を求めます.

 

mとnが共に0以外の整数解があればPは合成数であり、なければ素数となります.
(m、n共に0になるのはP=1のときだけです)

 

余りが0、2、3、4の場合、Pは偶数か3の倍数です.

 

使い方は以上ですが、もう少し補足してみます.

 

m≠0かつn≠0となる整数解が見つかれば、Pは合成数と判定します.
P’=6m+1
P’’=6n+1
P=P’×P’’=(6m+1)×(6n+1)
となり、素因数分解ができるからです.

 

m=0かつn≠0しか整数解がない場合は、Pは素数と判定します.
P’=6m+1=6×0+1=1
P’’=6n+1
P=P’×P’’=1×(6n+1)=6n+1
となり、素因数分解ができないからです.

 

同様に、m≠0かつn=0しか整数解がない場合も、Pは素数と判定します.
P’=6m+1
P’’=6n+1=6×0+1=1
P=P’×P’’=(6m+1)×1=6m+1
となり、素因数分解ができないからです.

 

以上のように判定を行ないます.



読者登録

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