第3题

证明存在无穷多个正整数

n

，使得

n^2+1

有一个大于

2n+\sqrt{2n}

的素因数。

第 6/6 步：结论：无穷多个素数 p 给出无穷多个合法的 n

上一步下一步

p \ge 2n+\sqrt{2n}, \quad p\mid n^2+1, \quad p\to\infty \implies \text{infinitely many valid } n

详细分析

由第5步， $n\le\frac{p-h}2$ 且 $p\mid n^2+1$ ，于是由第1步的计算， $p$ 是 $n^2+1$ 的一个满足 $p>2n+\sqrt{2n}$ 的素因数。满足 $p\equiv1\pmod8$ 的素数有无穷多个（狄利克雷定理的一个特例，也可直接用分圆多项式证明）。相应的正整数 $n=p-x$ 不可能只取有限多个值：否则这些 $n^2+1$ 只有有限多个素因数，与上面构造出的无穷多个互不相同的素数 $p$ 矛盾。因此存在无穷多个满足所需性质的不同正整数 $n$ 。 $\blacksquare$