证明：存在无穷多个正整数 $n$，使得 $n^{2}+1$ 有一个大于 $2n+\sqrt{2n}$ 的质因子．（立陶宛）
【难度】
【出处】
2008年第49届IMO试题
【标注】
【答案】
略
【解析】
证法一
设 $m(\geqslant 20)$ 是一个整数，$p$ 是 $(m!)^2+1$ 的一个质因子，则 $p>m\geqslant 20$．令整数 $n$ 满足 $0<n<\dfrac{p}{2}$，且 $n\equiv \pm m!\pmod{p}$．于是 $0<n<p-n<p$，且
$n^2\equiv -1\pmod{p}$ ①
故 $(p-2n)^2=p^2-4pn+4n^2\equiv -4\pmod{p}$
所以
$(p-2n)^2\geqslant p-4\\
p\geqslant 2n+\sqrt{p-4}\geqslant 2n+\sqrt{2n+\sqrt{p-4}-4}>2n+\sqrt{2}n ② $
由 ①② 便知，命题成立．
证法二
首先，若素数 $p\equiv\pmod{4}$，则 $\left(\dfrac{-1}{p}\right)=1$．即存在 $n\in\{1,2,\cdots,p-1\}$，使得 $n^2\equiv -1\pmod{p}$．显然对于上述的 $n,(p-n)^2\equiv n^2\equiv -1\pmod{p}$，且 $\min\{n,p-n\}\leqslant \dfrac{p-1}{2}$，所以，存在整数 $f(p)\in\left\{1,2,\cdots,\dfrac{p-1}{2}\right\}$，使得 $f^2(p)\equiv -1\pmod{p}$．
下证：当 $p$ 足够大 $(p\geqslant 29)$ 时，$n=f(p)$ 满足
$2n+\sqrt{2}n<p$ ③
若对某个 $p\geqslant 29$，上述结论不成立，则
$\begin{aligned}
2n+\sqrt{n}\geqslant p&\Leftrightarrow (1+2\sqrt{2n})^2\geqslant 4p+1\\
&\Leftrightarrow n\geqslant \dfrac{p-1}{2}-\dfrac{\sqrt{4p+1}-3}{4}
\end{aligned}$
设 $t=\dfrac{p-1}{2}-n\in\mathbb{Z}$，则 $0\leqslant t\leqslant \dfrac{\sqrt{4p+1}-3}{4}$，而
$\begin{aligned}
0&\equiv n^2+1\equiv \left(\dfrac{p-1}{2}-t\right)^2+1\\
&=\dfrac{p^2-2p+1}{4}+t^2-(p-1)t+1\\
&\equiv \dfrac{3p+5}{4}+t^2+t\pmod{p}
\end{aligned}$
因为 $4|p-5$，所以 $\dfrac{p^2-2p+1}{4}-\dfrac{3p+1}{4}=p\cdot \dfrac{p-5}{4}\equiv 0\pmod{p}$
所以 $p\bigg|t^2+t+\dfrac{3p+5}{4}$
而由 $0\leqslant t\leqslant \dfrac{\sqrt{4p+1}-3}{4}$ 知，
$
0<t^2+t+\dfrac{3p+5}{4}\leqslant \left(\dfrac{\sqrt{4p+1}-3}{4}\right)^2+\dfrac{\sqrt{4p+1}-3}{4}+\dfrac{3p+5}{4}=\dfrac{8p+9-\sqrt{4p+1}}{8}<p$
矛盾!
所以，结论 ③ 对足够大的同余 $1$ 模 $4$ 的素数 $p$ 均成立．
下面只需说明 $f(p)$ 的取值有无限多个即可．事实上，$p|f^2(p)+1\Rightarrow f(p)>\sqrt{p-1}$，当 $p\rightarrow \infty$，所以 $f(p)$ 的取值有无限多个．在原命题中，取 $n=f(p)$，$p$ 为相应的素因子即可．
设 $m(\geqslant 20)$ 是一个整数，$p$ 是 $(m!)^2+1$ 的一个质因子，则 $p>m\geqslant 20$．令整数 $n$ 满足 $0<n<\dfrac{p}{2}$，且 $n\equiv \pm m!\pmod{p}$．于是 $0<n<p-n<p$，且
$n^2\equiv -1\pmod{p}$ ①
故 $(p-2n)^2=p^2-4pn+4n^2\equiv -4\pmod{p}$
所以
$(p-2n)^2\geqslant p-4\\
p\geqslant 2n+\sqrt{p-4}\geqslant 2n+\sqrt{2n+\sqrt{p-4}-4}>2n+\sqrt{2}n ② $
由 ①② 便知，命题成立．
证法二
首先，若素数 $p\equiv\pmod{4}$，则 $\left(\dfrac{-1}{p}\right)=1$．即存在 $n\in\{1,2,\cdots,p-1\}$，使得 $n^2\equiv -1\pmod{p}$．显然对于上述的 $n,(p-n)^2\equiv n^2\equiv -1\pmod{p}$，且 $\min\{n,p-n\}\leqslant \dfrac{p-1}{2}$，所以，存在整数 $f(p)\in\left\{1,2,\cdots,\dfrac{p-1}{2}\right\}$，使得 $f^2(p)\equiv -1\pmod{p}$．
下证：当 $p$ 足够大 $(p\geqslant 29)$ 时，$n=f(p)$ 满足
$2n+\sqrt{2}n<p$ ③
若对某个 $p\geqslant 29$，上述结论不成立，则
$\begin{aligned}
2n+\sqrt{n}\geqslant p&\Leftrightarrow (1+2\sqrt{2n})^2\geqslant 4p+1\\
&\Leftrightarrow n\geqslant \dfrac{p-1}{2}-\dfrac{\sqrt{4p+1}-3}{4}
\end{aligned}$
设 $t=\dfrac{p-1}{2}-n\in\mathbb{Z}$，则 $0\leqslant t\leqslant \dfrac{\sqrt{4p+1}-3}{4}$，而
$\begin{aligned}
0&\equiv n^2+1\equiv \left(\dfrac{p-1}{2}-t\right)^2+1\\
&=\dfrac{p^2-2p+1}{4}+t^2-(p-1)t+1\\
&\equiv \dfrac{3p+5}{4}+t^2+t\pmod{p}
\end{aligned}$
因为 $4|p-5$，所以 $\dfrac{p^2-2p+1}{4}-\dfrac{3p+1}{4}=p\cdot \dfrac{p-5}{4}\equiv 0\pmod{p}$
所以 $p\bigg|t^2+t+\dfrac{3p+5}{4}$
而由 $0\leqslant t\leqslant \dfrac{\sqrt{4p+1}-3}{4}$ 知，
$
0<t^2+t+\dfrac{3p+5}{4}\leqslant \left(\dfrac{\sqrt{4p+1}-3}{4}\right)^2+\dfrac{\sqrt{4p+1}-3}{4}+\dfrac{3p+5}{4}=\dfrac{8p+9-\sqrt{4p+1}}{8}<p$
矛盾!
所以，结论 ③ 对足够大的同余 $1$ 模 $4$ 的素数 $p$ 均成立．
下面只需说明 $f(p)$ 的取值有无限多个即可．事实上，$p|f^2(p)+1\Rightarrow f(p)>\sqrt{p-1}$，当 $p\rightarrow \infty$，所以 $f(p)$ 的取值有无限多个．在原命题中，取 $n=f(p)$，$p$ 为相应的素因子即可．
答案
解析
备注
