问题及解答

存在无穷多个形如 $4n-1$ 和 $4n+1$ 的素数.

这是关于形如 $4n\pm 1$ 的素数的 Dirichlet 定理.

References:

Tom M. Apostol, Introduction to Analytic Number Theory.  《解析数论导引》第七章 Theorem 7.1. 世界图书出版公司.

先证存在无穷多个形如 $4n-1$ 的素数.

(反证法) 假设不然, 形如 $4n-1$ 的素数仅有有限多个. 设 $p$ 是其中最大的. 

令 $N=2^2\cdot 3\cdot 5\cdots p-1$, 于是 $N$ 也是 $4n-1$ 的数, 但它不是素数, 因为 $N > p$.

另一方面, 所有小于等于 $p$ 的素数都不整除 $N$. 因此 $N$ 的素因子一定都大于 $p$. 于是 $N$ 的所有素因子都形如 $4n+1$. 但是两个形如 $4n+1$ 的数仍是 $4n+1$ 形式, 这与 $N$ 为 $4n-1$ 形式矛盾.

故形如 $4n-1$ 形式的素数有无穷多个.

任取正整数 $N > 1$. 我们将证明存在一个比 $N$ 大的形如 $4n+1$ 的素数 $p$. 

如此即说明存在无穷多个 $4n+1$ 形式的素数.

令 

\[
m=(N!)^2+1.
\]

显然 $m$ 是奇数. 令 $p$ 是 $m$ 的最小素因子. 注意到 $2,3,4,5,\ldots,N$ 均无法整除 $m$, 故 $p > N$. 因此, 我们有

\[
(N!)^2\equiv -1{\pmod p}.
\]

两边升幂到 $p-1$ 次方, 即同时作幂 $\frac{p-1}{2}$, 我们有

\[
(N!)^{p-1}\equiv (-1)^{\frac{p-1}{2}}{\pmod p}.
\]

但是根据 Euler-Fermat 定理, 由于 $p$ 和 $N!$ 互素, 故 $(N!)^{p-1}\equiv 1\pmod p$. 于是

\[
(-1)^{\frac{p-1}{2}}\equiv 1{\pmod p}.
\]

现在 $(-1)^{\frac{p-1}{2}}$ 与 $1$ 的差要么是 $0$, 要么是 $-2$. 但后者是不可能的, 因为要被 $p$ 整除. 因此差只能是 $0$. 这就意味着 $\frac{p-1}{2}$ 是偶数, 也即 $p\equiv 1\pmod 4$.  证毕.