容斥原理在素數(shù)分布上的應(yīng)用

（凱里學(xué)院，貴州 凱里 556011）

0 引言

素數(shù)是數(shù)論中被研究最廣泛的一類數(shù)，除了在整除理論、同余理論、不定方程理論這些基礎(chǔ)問題經(jīng)常用到之外，在橢圓曲線密碼、圓錐曲線密碼、RSA密碼三大公鑰密碼體制中亦有重要的應(yīng)用，這三大公鑰密碼體制的加密和解密都依賴于大素數(shù).就素數(shù)本身而言，其數(shù)量分布、素性判定及其獨特性質(zhì)如孿生素數(shù)與梅森素數(shù)等問題也是重要的研究熱點.素數(shù)的數(shù)量分布問題，看似簡單但時至今日仍是難以解決的數(shù)學(xué)難題.本文通過容斥原理介紹素數(shù)分布的幾個重要性質(zhì)，對素數(shù)分布的上界和下界給出幾個比較精確的估計.

1 容斥原理

我們已經(jīng)知道素數(shù)的個數(shù)是無窮的，但是在給定的一個數(shù)以內(nèi)分布著多少個素數(shù)，怎么找到這個范圍內(nèi)的所有素數(shù)是一個有趣的問題，下面我們通過容斥原理來探討這個問題.以符號π(x)表示不超過實數(shù)x的素數(shù)個數(shù)，則有

幾百年來，許多愛好素數(shù)的人士都在給π(x)尋找一個簡單的表達式，試圖用公式來表達素數(shù)分布的規(guī)律，其中最著名的有以下3 個，一般稱為素數(shù)的漸近表達式［1］：

第三式就是著名的素數(shù)定理，本文給出的一個算法來探討素數(shù)分布的一些分布結(jié)果，并介紹著名的Chebyshev不等式，它將給出π(x)的上界與下界估計.

定理1（容斥原理）設(shè)A 是一個有限集，P1,P2,P3,...,Pm是和集合A 有關(guān)的性質(zhì)，對于任意性質(zhì)Pj(1 ≤j≤m)，A 中的任意元素a 要么有性質(zhì)Pj成立，要么有性質(zhì)Pj不成立.再設(shè)A 中有性質(zhì)Pj成立的所有元素組成的子集記為Aj(1 ≤j≤m)，那么A 中性質(zhì)P1,P2,P3,...,Pm都不成立的所有元素組成的子集B的元素個數(shù)為［2］:

下面來計算F(a)的值 .若a∈B,則i2＜...＜ik≤m,1 ≤k≤m，從而F(A)=f(a)=1.若a?B,a∈A-B,則a至少有一個性質(zhì)成立，則可對元素按照P1,P2,P3,...,Pm中有多少個性質(zhì)成立來分類：有且恰有其中一個性質(zhì)成立的元素組成的子集記作C1；有且恰有其中兩個性質(zhì)成立的元素組成的子集記作C2；…；有且恰有其中m 個性質(zhì)成立的元素組成的子集記作Cm.顯然這些子集兩兩不相交且有:

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

推論1特別的，記Ai關(guān)于A的補集為也就是那么上述容斥原理可表為B=

推論2一般的A 中至少有一個性質(zhì)成立的元素個數(shù)為

2 素數(shù)分布的幾個重要性質(zhì)

定理2（素數(shù)分布的上下界定理）設(shè)全體素數(shù)按大小順序排成的序列是：p1=2,p2=3,p3=5,???,pn,???.則有

證明：易知pn≤p1p2???pn-1+1 (n＞1)，下面用數(shù)學(xué)歸納法來證明上面兩式.

當(dāng)n=1 時，顯然成立.假設(shè)n≤k時式子成立，則當(dāng)n=k+1時，由歸納假設(shè)可得這就證明了對任意的n≥1，都有對x≥2，必有唯一的正整數(shù)n，使得從而有故可得

定理3（Chebyshev不等式）設(shè)實數(shù)x≥2，pn是第n個素數(shù)，則有［3］

當(dāng)x≥6時，取顯然有2m≤x≤3m，因而可得直接驗算可知上式當(dāng)2 ≤x＜6 時也成立，這就證明了式子的左邊.

當(dāng)m=2k時，由上式可得2k+1，由此及估計可推出

對上式從k=0 到s-1 求和，得到對任意x≥2，必有唯一的整數(shù)t≥1，使得x≤2t，因而有這就證明了不等式的右邊.在上式中取x=pn，利用pn＞n就得到這就證明了第二式的左半邊.設(shè)n＞1，取2m=pn+1，得到，進而有

當(dāng)實數(shù)s＞-1 時，熟知有不等式取即得由上式即得由此推出:當(dāng)n≥3 時右半不等式成立，當(dāng)n＜3 時直接驗證（2）式右半不等式成立.

由上我們還可以直接得到

這就是著名的素數(shù)定理.無論是定理1、2、3，還是素數(shù)定理都沒有給出π(x)的確切的值，但是我們通過上下界分布定理可以大概知道在一個自然數(shù)的算術(shù)數(shù)列中的素數(shù)分布規(guī)律，對于一定范圍或特殊范圍內(nèi)的素數(shù)分布，由上還可以得到一個極弱的素數(shù)分布上下界命題.

推論5設(shè)m≥5，則有

3 結(jié)束語

對于任意給定的整數(shù)，其間分布了多少個素數(shù)，這是一個極其的復(fù)雜的問題，因為素性判定本身就是一件十分困難的事情，雖然古今中外熱愛數(shù)論的學(xué)者在這一方面做了大量有益的工作，但是至今還沒有一個有效的通行的算法對任意給定的整數(shù)進行素性判定［4-5］.素數(shù)的個數(shù)分布是數(shù)論中研究素數(shù)性質(zhì)的一個重要課題，研究素數(shù)分布規(guī)律，一直是數(shù)論中最有吸引力的熱點和難點之一.另一方面，在網(wǎng)絡(luò)和通信迅猛發(fā)展的時代，常用三大公鑰密碼體制經(jīng)常要用到大素數(shù)［6］.本文通過容斥原理用初等的方法簡要的總結(jié)了素數(shù)分布的幾個性質(zhì)，探索素數(shù)在自然數(shù)中的特殊分布，為尋找大素數(shù)提供了一個有益的理論指導(dǎo)和幫助.