形如 6k±1 的素数

设  是一个包含有限个素数的集合，令

则  ， ，所以  必有一个素因子不在集合  中，故  不可能包含所有的素数，也就是说，素数一定有无穷多个．

应用类似的方法，可以证明形如  的素数也有无穷多个：

设  是一个包含有限个形如  的素数的集合，令

则 ，。但素数一定有  的形式，而形如  的数的乘积还是  的形式，不可能得到  的形式，故  必有一个形如  的素因子，且这个素因子不在  中，故  不可能包含所有形如  的素数，也就是说，形如  的素数有无穷多个．

不过，用同样的方法无法证明形如  的素数有无穷多个，我们需要另辟蹊径．

下面给出两个证明，这两个证明实际上都依赖与  的循环群结构：

证明一[1]：

设  是一个包含有限个形如  的素数的集合，令

考虑  的素因子 ，因为 ，所以 ，即 ，所以 ．

考虑  对模  的指数 。则必有 ，故  只能是 ，， 或者 ．由  知，  不可能是  或 ．

如果  的话，则有 ，且 ，故 ，可得

而这是不可能的．

所以  只能等于 ．

而  ，即 ，故  为  形式的素数，且

所以  不可能包含所有形如  的素数，也就是说，形如  的素数有无穷多个．

证明二：

实际上，我们只需要证明形如  的素数有无穷多个就可以了．

设  是一个包含有限个形如  的素数的集合，令

设 ，则 ．

考虑  的一个素因子 ，则 ，且 ，所以 ．

如果 ，则

而这是不可能的．所以 ．

而  ，即 ，故  为  形式的素数，且 ．

所以  不可能包含所有形如  的素数，也就是说，形如  的素数有无穷多个．

上面的第二个证明实际上依赖于下面这个结论[2]：

设  是一个质数，则

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

设 、 为整数，且 ，则有无穷多个形如  的素数．

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