ある整数$n$を使って$6n+5$と書ける素数を$6n+5$型の素数と呼びます｡ $6n+5$型の素数が無限個存在することを証明してください｡
$6n+5$型の素数が有限個しか存在しないと仮定して矛盾を導きます｡ $p_1, p_2, \dots, p_k$を$5$以外のすべての$6n+5$型の素数とします｡ そして, 次のように定義される自然数$N$を考えます｡ \[N = 6\prod_{i=1}^k p_i +5\]
この自然数$N$の性質を見ていきます｡ まず, $N$の定義から$N$は$6N+5$型の自然数であることがわかります｡ 次に, $N$は$5, p_1, p_2, \dots, p_k$のどの$6n+5$型の素数でも割り切れないことを示します｡
もし, $5\mid N$ならば, \[5 \mid N - 5 = 6\prod_{i=1}^k p_i\] より$5 \mid \prod_{i=1}^k p_i$となります｡ しかし, これはどの$p_i$も$5$でないことから矛盾です｡ よって$5\nmid N$がわかりました｡
そして, もし$p_i \mid N$となる$p_i$が存在すると仮定すると \[p_i \mid N-6 \prod_{i=1}^k p_i = 5\] となり, これも$p_1\neq 5$であることから矛盾であることがわかり$p_i \nmid N$が従います｡
以上の考察により, 自然数$N$の素因数はすべて$6n+5$以外の素数から構成されていることがわかります｡ そのような素数は$2$と$3$の他はすべて$6n+1$型の素数です｡ これらの素数をどのように掛け合わせても$6n+5$型の自然数は構築できないことを示します｡ これが示されれば, $N$が$6n+5$型の自然数であることから矛盾を導くことができ証明が完了します｡
まず, $2^a$ ($a$は自然数) を考えると, この数は$6n+2$型か$6n+4$型の自然数だとわかります｡ 同様に, $3^b$ ($b$は自然数) を考えると, この数は常に$6n+3$型の自然数だとわかります｡ そして, $6n+1$型の素数をいくつ掛け合わせても$6n+1$型の素数です｡ この4タイプ($6n+1$型, $6n+2$型, $6n+3$型, $6n+4$型)の自然数を掛け合わせても$6n+5$型にならないこともすぐわかります｡ ゆえに, これは上で述べた矛盾になっています｡ よって$6n+5$型の素数が無限個存在することが示されました｡