差が 2 の素数が 3 つ並ぶのは 3、5、7 だけ？余りで候補を消していく

$p$、$p+2$、$p+4$ がそろって素数になるのは $p=3$ のときだけです。$3$、$5$、$7$ の 1 組しかありません。

大きい素数を探しても見つからない、という話ではありません。$3$ で割った余りを見た瞬間に、候補が 1 つに決まります。

3 で割った余りで分ける

$p$ を $3$ で割った余りは $0$、$1$、$2$ のどれかです。$p+2$ と $p+4$ の余りも、そこから決まります。

余りが $1$ なら $p+2$ の余りは $0$。余りが $2$ なら $p+4$ の余りが $0$ になります。

つまり 3 つのうち必ず 1 つが $3$ の倍数。$3$ の倍数で素数なのは $3$ そのものだけです^[3]。

$3$ の倍数になった項が $3$ 自身であれば、素数として生き残ります。それは $p=3$ の場合だけ。

例：3 つ組を書き下す

$p=3$ なら $3$、$5$、$7$ ですべて素数。$p=5$ なら $5$、$7$、$9$ で、$9=3^2$ が素数ではありません。

$p=11$ なら $11$、$13$、$15$。$15$ が $3$ の倍数です。$p=101$ でも $103$、$105$ のうち $105$ が落ちます。

いくら大きい $p$ を試しても同じ。$3$ で割った余りの並びが変わらないためです^[1]。

5 以上の素数は 6k ± 1 の形

$3$ より大きい素数は、$6k+1$ か $6k-1$ のどちらかで書けます^[3]。

$6$ で割った余りが $0$、$2$、$4$ なら偶数。$3$ なら $3$ の倍数。残るのは $1$ と $5$ だけです。

$5$ 以上の素数がすべて $6k\pm 1$ に入るので、$p^2$ を $24$ で割った余りも決まります。$p=6k\pm 1$ なら $p^2=36k^2\pm 12k+1$。

$36k^2\pm 12k=12k(3k\pm 1)$ で、$k$ と $3k\pm 1$ の一方は必ず偶数。だから $24$ で割り切れ、余りは $1$ です。

$5^2=25$、$7^2=49$、$11^2=121$。どれも $24$ で割ると $1$ 余ります。

例：p と p の 2 乗に 2 を足した数

$p$ と $p^2+2$ がどちらも素数になるのは、$p=3$ のときだけです。$3$ と $11$。

$p$ が $3$ の倍数でなければ、$p^2$ を $3$ で割った余りは $1$。すると $p^2+2$ の余りが $0$ になります。

$p^2+2$ は $3$ より大きいので、$3$ の倍数なら素数ではありません。残るのは $p=3$ だけ。

例：2 の n 乗から 1 を引いた数

$2^n-1$ が素数なら、$n$ も素数でなければなりません^[2]。

$n$ が合成数で $n=ab$ と書けたとすると、次の因数分解が使えます。

$$2^{ab}-1=(2^a-1)\left(1+2^a+2^{2a}+\cdots +2^{(b-1)a}\right)$$

$a$ も $b$ も $2$ 以上なので、両方の因数が $1$ より大きい。だから $2^n-1$ は合成数です。

逆は成り立ちません。$n=11$ は素数ですが $2^{11}-1=2047=23\times 89$ で合成数です。

必要条件と十分条件を分けて扱う。ここを混ぜると、証明が一方向だけになります。

例：4 乗に 4 を足した数

$n^4+4$ が素数になる自然数 $n$ を求めます。見た目には手がかりがありません。

平方の差の形を作ると、因数分解できます。

$$n^4+4=(n^2+2{)}^2-(2n{)}^2=(n^2-2n+2)(n^2+2n+2)$$

$n^2-2n+2=(n-1{)}^2+1$ なので、$n\ge 2$ では $2$ 以上。もう一方も $2$ 以上なので合成数です。

$n=1$ のときだけ $1\times 5=5$ となり素数。答えは $n=1$ の 1 つだけです。

絞り込みの型

素数を求める問題では、無限の候補を有限に落とす一手を探します。

余りを使うか、因数分解を使うか。どちらの型かは、式に文字の 2 乗や高い次数があるかで見当がつきます。

余りで大半を落とし、残った数個を手で確かめる。素数の問題は、この 2 段でほとんど片づきます。

出典