素数であるか否かを証明する問題

「2以上の自然数nに対し、nとn²＋2がともに素数になるのはn＝3の場合に限ることを示せ。

　　K都大学」

素数とは

　2、3、5、7、11、13、……

と

1とそれ自身以外に約数を持たない数

考えられる攻め手としては……
（a）素数のうち「2」以外は奇数
（b）素数が2つあればそれらは必然的に互いに素

ただ（b）はこれだけでは不足

「9」と「16」は互いに素だけれど

どちらも素数ではない

そこからもう一工夫必要そう

まず（a）で攻めてみます

nとn²＋2について考える

n＝2のとき

n²＋2＝2²＋2

　　　　＝6

この「n²＋2＝6」は素数ではない

n≠2のとき

nは3以上の素数

3以上の素数は奇数なので

　　n＝2k＋1（kは自然数）

とおける

このとき

　　n²＋2＝（2k＋1）²＋2

　　　　　 ＝4k²＋4k＋3

この「4k²＋4k＋3」は素数でないと言えるか？

もし因数分解が可能ならば

1と自身以外の約数を持つので素数でないといえる

しかしこの式はkを含んだままでは

因数分解ができそうにない

なんとなく（a）の攻め手はアウトっぽい

それでは

「（b）素数が2つあればそれらは必然的に互いに素」

を試してみます

「互いに素であることを示す」場合は

いったん

「2数が互いに素でないとする」

と仮定してそこから矛盾を導く背理法がよく使われます

以下その手順で……

nとn²＋2について

この2数が互いに素でないと仮定すると

　n＝ka　…（A）
　n²＋2＝kb　…（B）
　　（kは1より大きい自然数、aとbは互いに素である自然数）

とおける

（A）を（B）に代入し
 

（ka）²＋2＝kb

k²a²＋2＝kb

kb－k²a²＝2

k（b－ka²）＝2

ここで「k」「b－ka²」は整数なので

その積が右辺の2に等しい場合

（k、b－ka²）＝（2、1）

　　k＝2　…（C）

　　b－ka²＝1　…（D）

（C）を（D）に代入し

　　b－2a²＝1

この式からaとbが互いに素でないことが言えれば

それが仮定の矛盾となるけれど

ちょっとそこまで至らない

（a）、（b）ともアウトっぽい

初心に帰って実験

nとn²＋2について

nが素数のときに両者の値を具体的に羅列してみる

素数がキーなので値は素因数分解したものも併記

n＝2のとき

n²＋2＝2²＋2＝6

　　　　　　　　　＝2・3

n＝3のとき

n²＋2＝3²＋2＝11

n＝5のとき

n²＋2＝5²＋2＝27

　　　　　　　　　＝3³

n＝7のとき

n²＋2＝7²＋2＝51

　　　　　　　　　＝3・17

n＝11のとき

n²＋2＝11²＋2＝123

　　　　　　　　　　＝3・41

n＝13のとき

n²＋2＝13²＋2＝171

　　　　　　　　　　＝3²・19

n＝17のとき

n²＋2＝17²＋2＝291

　　　　　　　　　　＝3・97

……

気付いたこと

「n＝3のとき以外は

　n²＋2の値はすべて3の倍数になっているのでは？」

となると3番目の方針が立ちますね

（c）nについて3で割ったときの余りで分類して考える

（c）を試してみます

ⅰ）n＝3k（kは自然数）のとき

　　nは3の倍数

　　k＝1のときn＝3となり

　　このとき

　　n²＋2＝3²＋2

　　　　　　＝11

　　これは素数である

　　k≧2のとき

　　n＝3kは3の素因数を持ち

　　素数ではない

ⅱ）n＝3k－2（kは自然数）のとき

　　nは3で割って1余る数

　　このとき

　　n²＋2＝（3k－2）²＋2

　　　　　　＝9k²－12k＋6

　　　　　　＝3（3k²－4k＋2）

　　これは3の倍数で

　　素数ではない

ⅲ）n＝3k－1（kは自然数）のとき

　　nは3で割って2余る数

　　このとき

　　n²＋2＝（3k－1）²＋2

　　　　　　＝9k²－6k＋3

　　　　　　＝3（3k²－2k＋1）

　　これは3の倍数で

　　素数ではない

ⅰ）、ⅱ）、ⅲ）より

nが3のときには

n²＋2は素数となり

nが3の倍数でないときには

n²＋2は3の倍数となり素数ではない

また3以外のすべての素数は

「3の倍数でない数」に含まれる

∴nとn²＋2がともに素数になるのはn＝3の場合に限る