一般的に、与えられた数が素数かそうでないかを判定するのは難しい問題です。
ここでは、ある式の値が素数に関係する問題について考えます。
入試問題にでる素数判定
素数判定が難しいことは何度も書いていますが、それでも、入試問題に「素数であることを示せ」だとか「素数でないことを示せ」などという問題はよく出ます。
最近で有名な入試問題は、「素数p,qを用いて\(p^q+q^p\)で表される素数を全てもとめよ。」です。
自然数\(p^q+q^p\)が素数かどうかを判定する問題です。解答は京都大学2016理系数学を参照
素数判定は難しいですが、不可能なことではありませんし、ある視点からみると、場合によってはあっさりと示せる場合もあるということです。
素数判定の基礎の基礎
素数判定の基礎の基礎は素数の定義に従うことです。全ては、ここから始まっています。
素数とは約数が１かそれ自身の１より大きい自然数のことですから、約数を調べることになります。
約数を調べるということは、素因数分解を考えるということです。素因数分解が得られれば、すべての約数は求められます。
素因数分解するためには、積の形に表すということです。式が因数分解できる場合にはまずそれが素数判定に役立ちます。
素数とは積に関する性質なので積の形で表すと非常に扱いやすいのです。
それでは、例題として下記の入試問題を考えます。
積に分解して解く問題
例題１：\(n^4-16n^2+100\)の形
「\(n^4-16n^2+100\)が素数となる整数nを求めよ。」2011年の中京大学問題、問題文は編集しています。
左辺を因数分解せよというのが最初の小問に与えられています。この因数分解はちょっと慣れていないと難しいかもしれません。\(n^2-16n+100\)は因数分解できないのですが、\(n^4-16n^2+100\)は下記のようにできます。
\(n^4-16n^2+100\)
\(=n^4+20n^2+100-36n^2\) //ここがちょっと難しい\(=n^4-20n^2+100+4n^2\)だと失敗
\(=(n^2+10)^2-36n^2\) //ここまでくれば楽勝
\(=(n^2+10+6n)(n^2+10-6n)\) //因数分解できたヤッタ－
二つの積が素数ということは、片方が1または-1ということです。ただし、これは必要条件であって十分条件ではないことに注意しなければなりません。
あとは\(n^2+10±6n=±1(複合任意)\)の４つの方程式からnを求め、\(n^4-16n^2+100\)が素数となるnだけを選択します。
結果として、n=±3が候補して残りますが、このとき、\(n^4-16n^2+100\)は37で素数となっていますので、、n=±3が答えとなります。
例題2：\(a^b-1\)の形
「a,bは2以上の整数とする。\(a^b-1\)が素数ならa=2であり、bは素数であることを証明せよ。」2007年の千葉大後期問題、問題文は編集しています。
b>1なら左辺が因数分解できます。
\(a^b-1=(a-1)(a^{b-1}+a^{b-2}+…+1)\)
これは、等比数列の和の公式をちょっと変形した式です。
これから、a-1=1をつかってa=2を導きます。
因数分解できればここまではわりと簡単ですが、ここから先は結構茨の道です。
しかしa=2というかなり強い条件が得られたおかげで道が開けます。\(2^b-1\)の形を考えればよいので。
\(b=pq(p≧q>1)\)と分解できたとします。
\(A=a^p=2^p\)とおくと
\(a^b-1\\=A^q-1=(A^q-1)(A^{q-1}+A^{q-2}+…+1)\)
と因数分解できて道が開けます。
ところどころ補充が必要ですが、証明の概略は上記のようになります。因数分解して条件をより絞り込んでいくわけです。
ところで、実際に、\(2^b-1\)を計算すると
\(2^1-1=1\)
\(2^2-1=3(素数)\)
\(2^3-1=7(素数)\)
\(2^4-1=15=3*5\)
\(2^5-1=31(素数)\)
\(2^6-1=63=3^2*7\)
\(2^7-1=127(素数)\)
\(2^8-1=255=3*5*17\)
\(2^9-1=511=7*73\)
\(2^{10}-1=1023=3*11*31\)
\(2^{11}-1=2047=23*89\) //★注目！素数じゃない
\(2^{12}-1=4095=3^2*5*7*13\)
\(2^{13}-1=8191(素数)\)
実は、\(b\)が素数でも\(2^b-1\)が合成数となる場合があります(b=11の場合)。「\(b\)が素数」は「\(2^b-1\)が素数」の十分条件にはなっていないということですね。
例題3:ｎ２を１２０で割ると１余るような、１２０以下の正整数ｎ
第3回の日本数学オリンピック予選問題。
\(n^2=120k+1\)となる正の整数n≦120,kを求めれば良い
\(n^2-1=120k\)
\(n-1)(n+1)=2^3*3*5*k\)
となるので、\(n-1)(n+1)\)の組合せが絞り込まれる。
答えは、16組ある。すなわち、
n=1,11,19,29,31,41,49,59,61,71,79,89,91,101,109,119
素数でないことを示す問題
逆に素数でないことを示す問題もあります。
さきほどの京都大学の問題にでてきた式\(p^q+q^p\)は、一部の例外を除いて素数でないことを示す問題だったのです。素数でないことを示す方法として、具体的な素因数を示す方法があります。
この京都大学の問題の場合は、素因数3をつかってうまく証明できます。
まとめ
素数かどうかを判定するには
（１）約数を調べる。そのために因数分解できれば、条件を分解できる。
（２）合成数の証明には、素因数をみつけて、それで割れることを示す。素因数として2や3がよく使われます。それは、2や3の場合は剰余が少ないので、うまく絞りこめる場合が多いからです。
[ad#foot]
