第3問

$k$ を $|a_0|$ より大きい素数とすると $k\nmid a_0$ なので $\gcd(a_0,k)=1$ であり、第1段階より $\gcd(P(k),k)=1$、すなわち $P(k)$ のすべての素因数は $k$ を割り切らない。$P$ は非定数なので、そのような素数 $k$ にわたって $|P(k)|\to\infty$ であり、$P(k)$ は常に素因数を持つ。非定数の整数係数多項式が固定された有限個の素数だけから作られる値を無限回とることはできないので、この方法で無限個の異なる素数 $p$ が現れ、それぞれがある素数 $k>|a_0|$ と対になり $p\mid P(k)$、$p\nmid k$ を満たす。