第3题

证明存在无穷多个正整数

n

，使得

n^2+1

有一个大于

2n+\sqrt{2n}

的素因数。

第 2/6 步：在剩余系上半部分中选取满足 x^2 = -1 (mod p) 的 x

上一步下一步

p\equiv1\pmod4 \implies \exists\, x\in(\tfrac p2,p),\ x^2\equiv-1\pmod p; \quad x=\tfrac{p+1}2+t,\ t\ge0

详细分析

由 $p\equiv1\pmod8$ 可得 $p\equiv1\pmod4$ ，故 $-1$ 是模 $p$ 的平方剩余，即存在整数其平方等于 $-1\pmod p$ ；在模 $p$ 的两个平方根（其和为 $p$ ）中，取满足 $\frac p2<x<p$ 的那个记为 $x$ 。用整数 $t\ge0$ 写作 $x=\frac{p+1}2+t$ 。