閉じる


<<最初から読む

4 / 23ページ

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

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
となり、素因数分解ができないからです.

 

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


計算例、P=169の場合

素数判定方程式を使って、実際に計算をしてみます.


169が素数なのか合成数なのかの判定は、次のように行ないます.

 

169は6で割ると1余るので、6N+1の形をしています.

そこで169を素数判定方程式のPに代入しますと、
169=36mn+6m+6n+1
となります.


この方程式のmとnの整数解を求めます.
mとnに0以外の整数解があれば、Pは合成数であり、なければ素数となります.

 

この方程式を満たす整数解には、
(m、n)=(2、2)
があります.従って、169は合成数です.

 

P’=6m+1=6×2+1=13
P’’=6n+1=6×2+1=13

 

つまり、
P=169=P’×P’’=13×13
と素因数分解できます.


図式解法:P=169の場合

計算の代わりに図を使って判定する方法を紹介します.

 

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

 

この素数判定法定式を次のように変形します.

 

169ー1=36mn+6m+6n
168=36mn+6m+6n
168÷6=(36mn+6m+6n)÷6
28=6mn+m+n
28=m(6n+1)+n
28ーn=m(6n+1)
(28ーn)÷(6n+1)=m
m=(28ーn)÷(6n+1)

 

縦軸をm、横軸をnとして、上記の最後の式をグラフを書いて整数解を求めます.


グラフ:P=169の場合



読者登録

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