第3题

证明存在无穷多个正整数

n

，使得

n^2+1

有一个大于

2n+\sqrt{2n}

的素因数。

第 1/6 步：策略：先固定素数 p，再在其下寻找合适的 n

上一步下一步

通俗地说

不去寻找 $n$ 再指望 $n^2+1$ 有大素因数，而是反过来：先选素数 $p$ ，再构造 $n$ 使 $p$ 整除 $n^2+1$ ，且 $n$ 足够小以致 $p$ 已经超过 $2n+\sqrt{2n}$ 。

p \equiv 1 \pmod 8,\quad h=\lceil\sqrt p\rceil,\quad n\le\tfrac12(p-h),\ p\mid n^2+1 \implies p\ge 2n+\sqrt{2n}

详细分析

固定任意满足 $p\ge2013$ 的素数 $p\equiv1\pmod8$ ，设 $h=\lceil\sqrt p\rceil$ 。我们希望找到正整数 $n\le\frac12(p-h)$ 使 $p\mid n^2+1$ 。若能做到，则 $p\ge 2n+h\ge 2n+\sqrt p$ ；由 $n\le\frac12(p-h)<\frac p2$ 得 $2n<p$ ，从而 $\sqrt{2n}<\sqrt p\le h$ ，于是 $p\ge2n+h>2n+\sqrt{2n}$ 。故 $p$ 本身就是 $n^2+1$ 的一个超过 $2n+\sqrt{2n}$ 的素因数，恰为所求。