素数かどうかの判定に関する問題です。

問題

2以上の自然数nに対し、\(nとn^2+2\)がともに素数になるのは、\(n=3\)の場合に限ることを示せ。

2016年京大の問題と類似しています

与えられた式の値が素数かどうかを判定するのは一般的に難しいです。

素数でないことは、1かその数自身以外の約数を見つければ示せます。

この問題はそのタイプの問題です。

考え方

まずは、nに数値を代入し、どのような傾向になるのかあたりをつけます。

規則がみつかれば、数学的帰納法なのでそれを証明します。

\(n^2+2\)の\(n\)にそれぞれ、1,2,3,…と代入すると、
3,6,11,18,27,38,51,66,83,102,123,146,171,…
素数かどうか素因数分解すると、

\(
n=1の時, \;n^2+2=3=3^1\\
n=2の時, \;n^2+2=6=2^1 3^1\\
n=3の時, \;n^2+2=11=11^1\\
n=4の時, \;n^2+2=18=2^1 3^2\\
n=5の時, \;n^2+2=27=3^3\\
n=6の時, \;n^2+2=38=2^1 19^1\\
n=7の時, \;n^2+2=51=3^1 17^1\\
n=8の時, \;n^2+2=66=2^1 3^1 11^1\\
n=9の時, \;n^2+2=83=83^1\\
n=10の時, \;n^2+2=102=2^13^117^1\\
n=11の時, \;n^2+2=123=3^1 41^1\\
n=12の時, \;n^2+2=146=2^1 73\\
n=13の時, \;n^2+2=171=3^2 19^1\\
…\)(数字の切れ目がわかりにくいので1乗も明記しました)

11や83など素数になるところもでてきてる・・・・

でも、そのときのnは3や9です。3は素数ですが、9は素数ではありません。

問題文より\(nまたはn^2+2\)が素数、しかも3は例外となってます。

ここで、nが3の倍数を除いて考えることにします。するとその条件では、\(n^2+2\)が3で割れていることが予想できます。実は、ここまでたどり着けばこの問題は解けたも同然です。

\(
n=1の時, \;n^2+2=3=3^1\\
n=2の時, \;n^2+2=6=2^1 3^1\\
n=4の時, \;n^2+2=18=2^1 3^2\\
n=5の時, \;n^2+2=27=3^3\\
n=7の時, \;n^2+2=51=3^1 17\\
n=8の時, \;n^2+2=66=2^1 3^1 11^1\\
n=10の時, \;n^2+2=102=2^1 3^117^1\\
n=11の時, \;n^2+2=123=3^1 41^1\\
n=13の時, \;n^2+2=171=3^2 19^1\\
…\)

結果的に、数学的帰納法の出動あなくても解けます。というか、この場合、数学的帰納法の適用は難しいです。

解法

1は素数でないので、n=1の時、\(nとn^2+2\)がともに素数になっていない。

nが3の倍数のとき、n=3mとなる自然数mが存在する。このとき、m=1を除いてnは素数でない。

n=3の場合、\(n^2+2=11\)で、\(nとn^2+2\)がともに素数。

n=3m+1となる自然数mが存在するとき、
\(n^2+2=9m^2+6m+3=3(3m^2+2m+1)\)で3を約数にもつから、\(nとn^2+2\)がともに素数になっていない。

n=3m-1となる自然数mが存在するとき、
\(n^2+2=9m^2-6m+3=3(3m^2-2m+1)\)で3を約数にもつから、\(nとn^2+2\)がともに素数になっていない。

よって、\(nとn^2+2\)がともに素数になるのは、n=3の時に限る。

コメント

解法では端折りましたが、nの場合分けが、3m-1,3m,3m+1ですべて網羅されていることを示した方がよいです。あまりに注目して、3m-1は3m+2としたほうがよいかもしれません。その場合、mを0以上にするか、n=2の場合を追加する必要があります。

\(n^2+2=(n+1)(n-1)+3\)です。

連続する3つの整数の積は6で割り切れる(したがって3で割れる)という法則があります。

\((n+1)n(n-1)\)は6で割りきれます。これに関連して、\((n+1)(n-1)\)は、nが3の倍数でないとき、3で割り切れることを覚えておくのもよさそうです。