容斥原理在素数分布上的应用

（凯里学院，贵州 凯里 556011）

0 引言

素数是数论中被研究最广泛的一类数，除了在整除理论、同余理论、不定方程理论这些基础问题经常用到之外，在椭圆曲线密码、圆锥曲线密码、RSA密码三大公钥密码体制中亦有重要的应用，这三大公钥密码体制的加密和解密都依赖于大素数.就素数本身而言，其数量分布、素性判定及其独特性质如孪生素数与梅森素数等问题也是重要的研究热点.素数的数量分布问题，看似简单但时至今日仍是难以解决的数学难题.本文通过容斥原理介绍素数分布的几个重要性质，对素数分布的上界和下界给出几个比较精确的估计.

1 容斥原理

我们已经知道素数的个数是无穷的，但是在给定的一个数以内分布着多少个素数，怎么找到这个范围内的所有素数是一个有趣的问题，下面我们通过容斥原理来探讨这个问题.以符号π(x)表示不超过实数x的素数个数，则有

几百年来，许多爱好素数的人士都在给π(x)寻找一个简单的表达式，试图用公式来表达素数分布的规律，其中最著名的有以下3 个，一般称为素数的渐近表达式［1］：

第三式就是著名的素数定理，本文给出的一个算法来探讨素数分布的一些分布结果，并介绍著名的Chebyshev不等式，它将给出π(x)的上界与下界估计.

定理1（容斥原理）设A 是一个有限集，P1,P2,P3,...,Pm是和集合A 有关的性质，对于任意性质Pj(1 ≤j≤m)，A 中的任意元素a 要么有性质Pj成立，要么有性质Pj不成立.再设A 中有性质Pj成立的所有元素组成的子集记为Aj(1 ≤j≤m)，那么A 中性质P1,P2,P3,...,Pm都不成立的所有元素组成的子集B的元素个数为［2］:

下面来计算F(a)的值 .若a∈B,则i2＜...＜ik≤m,1 ≤k≤m，从而F(A)=f(a)=1.若a∉B,a∈A-B,则a至少有一个性质成立，则可对元素按照P1,P2,P3,...,Pm中有多少个性质成立来分类：有且恰有其中一个性质成立的元素组成的子集记作C1；有且恰有其中两个性质成立的元素组成的子集记作C2；…；有且恰有其中m 个性质成立的元素组成的子集记作Cm.显然这些子集两两不相交且有:

若a∈Ch(1 ≤h≤m)，则有

推论1特别的，记Ai关于A的补集为也就是那么上述容斥原理可表为B=

推论2一般的A 中至少有一个性质成立的元素个数为

2 素数分布的几个重要性质

定理2（素数分布的上下界定理）设全体素数按大小顺序排成的序列是：p1=2,p2=3,p3=5,⋅⋅⋅,pn,⋅⋅⋅.则有

证明：易知pn≤p1p2⋅⋅⋅pn-1+1 (n＞1)，下面用数学归纳法来证明上面两式.

当n=1 时，显然成立.假设n≤k时式子成立，则当n=k+1时，由归纳假设可得这就证明了对任意的n≥1，都有对x≥2，必有唯一的正整数n，使得从而有故可得

定理3（Chebyshev不等式）设实数x≥2，pn是第n个素数，则有［3］

当x≥6时，取显然有2m≤x≤3m，因而可得直接验算可知上式当2 ≤x＜6 时也成立，这就证明了式子的左边.

当m=2k时，由上式可得2k+1，由此及估计可推出

对上式从k=0 到s-1 求和，得到对任意x≥2，必有唯一的整数t≥1，使得x≤2t，因而有这就证明了不等式的右边.在上式中取x=pn，利用pn＞n就得到这就证明了第二式的左半边.设n＞1，取2m=pn+1，得到，进而有

当实数s＞-1 时，熟知有不等式取即得由上式即得由此推出:当n≥3 时右半不等式成立，当n＜3 时直接验证（2）式右半不等式成立.

由上我们还可以直接得到

这就是著名的素数定理.无论是定理1、2、3，还是素数定理都没有给出π(x)的确切的值，但是我们通过上下界分布定理可以大概知道在一个自然数的算术数列中的素数分布规律，对于一定范围或特殊范围内的素数分布，由上还可以得到一个极弱的素数分布上下界命题.

推论5设m≥5，则有

3 结束语

对于任意给定的整数，其间分布了多少个素数，这是一个极其的复杂的问题，因为素性判定本身就是一件十分困难的事情，虽然古今中外热爱数论的学者在这一方面做了大量有益的工作，但是至今还没有一个有效的通行的算法对任意给定的整数进行素性判定［4-5］.素数的个数分布是数论中研究素数性质的一个重要课题，研究素数分布规律，一直是数论中最有吸引力的热点和难点之一.另一方面，在网络和通信迅猛发展的时代，常用三大公钥密码体制经常要用到大素数［6］.本文通过容斥原理用初等的方法简要的总结了素数分布的几个性质，探索素数在自然数中的特殊分布，为寻找大素数提供了一个有益的理论指导和帮助.