0%

形如 6k±1 的素数

欧几里得曾经给出过一个素数有无穷多个的证明:

PP 是一个包含有限个素数的集合,令

N=pPp+1N=\prod_{p \in P} p + 1

pP\forall p \in PpNp \nmid N ,所以 NN 必有一个素因子不在集合 PP 中,故 PP 不可能包含所有的素数,也就是说,素数一定有无穷多个.

应用类似的方法,可以证明形如 6k16k - 1 的素数也有无穷多个:

PP 是一个包含有限个形如 6k16k - 1 的素数的集合,令

N=6pPp1N=6 \cdot \prod_{p \in P} p - 1

pP\forall p \in PpNp \nmid N。但素数一定有 6k±16k \pm 1 的形式,而形如 6k+16k+1 的数的乘积还是 6k+16k+1 的形式,不可能得到 6k16k-1 的形式,故 NN 必有一个形如 6k16k-1 的素因子,且这个素因子不在 PP 中,故 PP 不可能包含所有形如 6k16k - 1 的素数,也就是说,形如 6k16k - 1 的素数有无穷多个.

不过,用同样的方法无法证明形如 6k+16k+1 的素数有无穷多个,我们需要另辟蹊径.

下面给出两个证明,这两个证明实际上都依赖与 (Z/pZ)(\mathbb{Z}/p\mathbb{Z})^* 的循环群结构:

证明一:

PP 是一个包含有限个形如 6k+16k + 1 的素数的集合,令

N=6pPpN = 6 \cdot \prod_{p \in P} p

考虑 N2N+1N^2-N+1 的素因子 pp,因为 N3+1=(N+1)(N2N+1)N^3+1=(N+1) \cdot (N^2-N+1),所以 pN3+1p \mid N^3+1,即 N31(modp)N^3 \equiv -1 \pmod p,所以 N61(modp)N^6 \equiv 1 \pmod p

考虑 NN 对模 pp 的指数 δp(N)\delta_p (N)。则必有 δp(N)6\delta_p (N) \mid 6,故 δp(N)\delta_p (N) 只能是 112233 或者 66.由 N31(modp)N^3 \equiv -1 \pmod p 知, δp(N)\delta_p (N) 不可能是 1133

如果 δp(N)=2\delta_p (N) = 2 的话,则有 N21(modp)N^2 \equiv 1 \pmod p,且 N1(modp)N \equiv -1 \pmod p,故 pN+1p \mid N+1,可得

p(N+1,N2N+1)=(N+1,3)=1p \mid (N+1, N^2-N+1) = (N+1, 3) =1

而这是不可能的.

所以 δp(N)\delta_p (N) 只能等于 66

δp(N)φ(p)=p1\delta_p (N) \mid \varphi(p) = p-1,即 6p16 \mid p-1,故 pp6k+16k+1 形式的素数,且 pPp \notin P

所以 PP 不可能包含所有形如 6k+16k + 1 的素数,也就是说,形如 6k+16k + 1 的素数有无穷多个.

证明二:

实际上,我们只需要证明形如 3k+13k+1 的素数有无穷多个就可以了.

PP 是一个包含有限个形如 3k+13k + 1 的素数的集合,令

N=(pPp)2+3N = \left(\prod_{p \in P} p\right)^2+3

pPp=2c+1\displaystyle \prod_{p \in P} p=2c+1,则 N=4(c2+c+1)N=4(c^2+c+1)

考虑 NN 的一个素因子 pp,则 p3p \ne 3,且 pc2+c+1c31p \mid c^2+c+1 \mid c^3-1,所以 c31(modp)c^3 \equiv 1 \pmod p

如果 c1(modp)c \equiv 1 \pmod p,则

0c2+c+13(modp)0 \equiv c^2+c+1 \equiv 3 \pmod p

而这是不可能的.所以 δp(c)=3\delta_p(c)=3

δp(c)φ(p)=p1\delta_p (c) \mid \varphi(p) = p-1,即 3p13\mid p-1,故 pp3k+13k+1 形式的素数,且 pPp \notin P

所以 PP 不可能包含所有形如 3k+13k + 1 的素数,也就是说,形如 3k+13k + 1 的素数有无穷多个.

上面的第二个证明实际上依赖于下面这个结论:

pp 是一个质数,则

(3p)=1    p1(mod3)\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \pmod 3

事实上,我们有更一般的结论,即狄利克雷定理

aabb 为整数,且 (a,b)=1(a,b)=1,则有无穷多个形如 ax+bax+b 的素数.

不过,这个定理的证明依赖于解析数论的技术,我们在这里就不讨论了.

参考:

  • https://mathblag.wordpress.com/2013/08/30/primes-of-the-form-6k1/
  • https://math.stackexchange.com/questions/671820/proving-an-infinite-number-of-primes-of-the-form-6n1
  • Elementary Number Theory: Primes, Congruences, and Secrets by William Stein