整数問題『テーマ:素数』②

integer数学
スポンサーリンク

この記事は、整数問題『テーマ:素数』① の続きです。

今回も素数がテーマの整数問題を扱います。

雰囲気をつかんでもらうことをゴールとしています。

では早速今回の問題を見てみましょう。

今回は初見ではかなり難しいと思います。

問題

(1) \(n^4+4\) の形の素数は5だけである。

(2) \(2^n-1\) が素数ならば、\(n\) も素数である。

解答

(1) \(n^4+4\) の形の素数は5だけである。

ポイント:因数分解する!

\begin{eqnarray}n^4+4 &=& n^4+4n^2+4-4n^2 \\ &=& (n^2+2)^2-(2n)^2 \\ &=& (n^2+2+2n)(n^2+2-2n)\end{eqnarray} \(n^4+4\) が素数であるためには、\(n^2+2+2n\) または \(n^2+2-2n\) のどちらかが 1 でなければならない。
ここで \(n\) は自然数(⇨ \(n \geq 1\))なので、
\(n^2+2+2n \geq n^2+2-2n\)
である。
よって \(n^2+2-2n = 1\)
これを解く。
\begin{eqnarray} n^2+2-2n &=& 1 \\ \therefore (n-1)^2 &=& 0 \\ \therefore n &=& 1 \end{eqnarray} このとき \(n^4+4 = 1+4 = 5\)
以上より \(n^4+4\) の形の素数は 5 しかないと分かる。

(2) \(2^n-1\) が素数ならば、\(n\) も素数である。

ポイント:\(2^n-1\) が素数という仮定を式にすることはできない
     ⇨ 示すべき命題をそのまま示すのは難しい
     ⇨ 対偶を示す方向で攻める → \(n=pq\) とおく
      ただし \(p,q\) は 2 以上の整数

対偶、すなわち「\(n\) が素数でないならば、\(2^n-1\) も素数でない」という命題を示す。
\(n\) が素数でないとすると、\(n=pq\) (ただし \(p,q\) は 2 以上の整数)と表すことができる。
\begin{eqnarray} 2^n-1 &=& 2^{pq}-1 \\ &=& (2^p)^q – 1^q \\ &=& \{(2^p)-1\}\{(2^p)^{q-1}+(2^p)^{q-2}+ \cdot\cdot\cdot +(2^p)^2+(2^p)+1\} \end{eqnarray}
ここで \(\{(2^p)-1\}\) と \((2^p)^{q-1}+(2^p)^{q-2}+ \cdot\cdot\cdot +(2^p)^2+(2^p)+1\) は、いずれも 2 以上の整数である。
よってそれらの積である \(2^{pq}-1 = 2^n-1\) は素数ではない。
したがって、\(n\) が素数でないならば、\(2^n-1\) も素数でない。
対偶が示されたので、元の命題も示された。

まとめ

今回の問題はかなり難しかったと思います。

ですが大事なポイントは因数分解の利用です。

それに加えて、(2) では正面突破がほぼ不可能のときに、対偶を示すという技を使いました。

また (2) では「 \(n\) が素数でない」という条件を「 \(n=pq\) ただし\(p,q\) は 2 以上の整数」と表現しました。

これは初見では思いつかないと思うので、覚えておくしかないです。

コメント

タイトルとURLをコピーしました