鄧從政

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

0 引言

素?cái)?shù)是數(shù)論中被研究最廣泛的一類數(shù)，除在同余理論、整除理論、不定方程理論及指數(shù)和原根這些基礎(chǔ)問(wèn)題經(jīng)常用到之外，在密碼學(xué)和編碼學(xué)上也有廣泛地應(yīng)用，如橢圓曲線密碼、RSA 密碼、圓錐曲線密碼三大公鑰密碼體制的加密和解密都依賴于大素?cái)?shù)［1］.長(zhǎng)期以來(lái)找出一個(gè)大整數(shù)范圍內(nèi)的所有素?cái)?shù)是數(shù)論中被研究最廣泛的一個(gè)課題，其中素?cái)?shù)的數(shù)量、素?cái)?shù)的分布、素?cái)?shù)表的構(gòu)造都依賴于現(xiàn)存找到的素?cái)?shù)，古典篩法可以找出不超出給定的一個(gè)正整數(shù)范圍內(nèi)的所有素?cái)?shù)，而且十分有效，它是構(gòu)造素?cái)?shù)表的一個(gè)實(shí)用方法［2］.本文通過(guò)Mobius函數(shù)及其獨(dú)特性質(zhì)從理論上證明古典篩法的有效性，為尋找素?cái)?shù)提供一個(gè)簡(jiǎn)潔而實(shí)用的算法.

1 古典篩法原理

1.1 算術(shù)基本定理

一個(gè)不等于1 的正整數(shù)不是合數(shù)就是素?cái)?shù)，素?cái)?shù)只有1 和它本身兩個(gè)素因數(shù)，而合數(shù)除了這兩個(gè)因數(shù)之外還有其他的真因數(shù)，那么怎樣把任意一個(gè)整數(shù)進(jìn)行因數(shù)分解呢?對(duì)此我們有下面的唯一分解定理即算術(shù)基本定理［3］.

定理1（算術(shù)基本定理）設(shè)整數(shù)a≥2，那么a一定可表為若干素?cái)?shù)的乘積，即a=p1p2...ps，其中pj(1 ≤j≤s)是素?cái)?shù)，且在不計(jì)次序的意義下上述表法是唯一的.

推理1設(shè)整數(shù)a≥2，那么a一定可表為若干素?cái)?shù)的乘積，即其中pj(1 ≤j≤s)是素?cái)?shù)，且在不計(jì)次序的意義下上述表法是唯一的.

根據(jù)上述算術(shù)基本定理，我們可以得到一個(gè)尋找素?cái)?shù)的算法，即古典篩法，也叫Eratosthenes篩法.再由最小自然數(shù)原理取p=min{p1,p2,···,ps}，則，這就是一切篩法的原理.

推理2設(shè)整數(shù)a≥2，那么a一定可表為若干素?cái)?shù)的乘積，即a=p1p2...ps，其中pj(1 ≤j≤s)是素?cái)?shù)，則必有素?cái)?shù)p|a且滿足

特別地，我們?nèi)=2，這就是古典篩法的原理.

推理3設(shè)整數(shù)a≥2，則必有素?cái)?shù)p|a且滿足

1.2 古典篩法的算法與應(yīng)用

根據(jù)篩法原理，理論上我們可以找出任意大整數(shù)范圍內(nèi)的所有素?cái)?shù)，從而找出所有的素?cái)?shù)，古典篩法就是把大整數(shù)分段去倍來(lái)尋找素?cái)?shù)的，比如我們要找出[1,n]范圍內(nèi)的素?cái)?shù)，其算法如下：

（3）刪除1和[1,n]范圍內(nèi)所有p的倍數(shù)ps≤n；

（4）刪除以上倍數(shù)后剩余的數(shù)即為所求的素?cái)?shù).

案例用古典篩法找出不超過(guò)300的所有素?cái)?shù).

（2）找出[1,17]范圍內(nèi)的所有素?cái)?shù)：2，3，5，7，11，13，17；

（3）刪除1和[1,300]范圍內(nèi)所有2，3，5，7，11，13，17的倍數(shù)；

（4）刪除以上倍數(shù)后剩余的數(shù)為：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113，127，131，137，139，149，151，157，163，167，173，179，181，191，193，197，199，211，223227，229，233，239，241，251，257，263，269，271，277，281，283，293.

剩余的數(shù)即是[1,300]范圍內(nèi)所有素?cái)?shù)，并可由此出發(fā)，可以篩出[1,3002]，[1,(3002)2]，…，[1,3002k]，更進(jìn)一步可以利用這種篩法構(gòu)造出素?cái)?shù)表.那么當(dāng)整數(shù)充分大時(shí)這張素?cái)?shù)表上的素?cái)?shù)有多少個(gè)，其分布是否有一定的規(guī)律呢?下面介紹一個(gè)著名的數(shù)論函數(shù)在古典篩法上的應(yīng)用，并從理論上證明古典篩法的有效性和實(shí)用性.

2 Mobius函數(shù)及其獨(dú)特性質(zhì)

以符號(hào)π(x)表示不超過(guò)實(shí)數(shù)x的素?cái)?shù)個(gè)數(shù)，以2=p1＜p2＜···＜ps表示所有不超過(guò)的素?cái)?shù)，則有根據(jù)上述篩法我們可以把1 ≤n≤x的所有整數(shù)n中能被任一pi(1 ≤i≤s)整除的數(shù)除掉后，剩下的就是滿足條件的全部素?cái)?shù)p和1，所以剩下的數(shù)的個(gè)數(shù)為下面我們探討能否用一個(gè)公式來(lái)表達(dá)這個(gè)式子.

在[1,x]上的正整數(shù)n能被d整除的數(shù)的個(gè)數(shù)為這樣能被取定的素?cái)?shù)pi(1 ≤i≤s)整除的數(shù)的個(gè)數(shù)是被2個(gè)取定的不同的整除的數(shù)的個(gè)數(shù)是被r個(gè)兩兩不同的整除的數(shù)的個(gè)數(shù)是如果設(shè)則顯然有G≤T.

上式右邊表示依次把區(qū)間[1,x]上的[x]個(gè)正整數(shù)中能被p1整除的個(gè)整數(shù)去掉，被p2整除的個(gè)整數(shù)去掉，一直到把被ps整除的個(gè)整數(shù)去掉后剩下的整數(shù)個(gè)數(shù)，顯然那些在[1,x]上恰好只能被一個(gè)整除的整數(shù)也就是形式的數(shù)，在這個(gè)過(guò)程中無(wú)重復(fù)的每一個(gè)數(shù)被去掉了一次，而對(duì)那些在[1,x]上的恰好只能被r(2 ≤r≤s)個(gè)兩兩不同的整除的整數(shù)，即形如的數(shù)在這個(gè)過(guò)程中恰好每個(gè)數(shù)被重復(fù)的去掉了r次，所以上式成立.那么這個(gè)差值是什么呢?對(duì)給定的r，考察量它是表示對(duì)滿足以下條件的在[1,x]上的正整數(shù)n的個(gè)數(shù)的某種有重復(fù)的計(jì)數(shù)：恰好被r個(gè)兩兩不同的整除的n恰好被計(jì)算了一次，恰好被t(r＜t≤)個(gè)兩兩不同的整除的n恰好被重復(fù)地計(jì)算了次.如果為了彌補(bǔ)G去掉了過(guò)多而加上V2，則需要考慮量

由此可得：

上述證明從略，詳見(jiàn)文獻(xiàn)［1］，若記Tr=[x]-Ur,1 ≤r≤s，則綜上可得如下系列結(jié)論.

定理2在上述條件和符號(hào)下，我們有［3-4］：（i）Us是區(qū)間[1,x]上與p1p2...ps不既約的整數(shù)n的個(gè)數(shù)，即滿足1 ≤n≤x,(n,p1p2...ps)＞1 的n的個(gè)數(shù)；（ii）Ts是區(qū)間[1,x]上與p1p2...ps既約的整數(shù)n的 個(gè) 數(shù)，即 滿 足1 ≤n≤x,(n,p1p2...ps)=1 的n的 個(gè) 數(shù)；（iii），或事實(shí)上，這就是容斥原理對(duì)這個(gè)問(wèn)題的精確闡述，同時(shí)更一般地推廣了古典篩法，也就是廣義篩法，即對(duì)給定的序列A及整數(shù)K，如何求出序列A中所有與K既約的整數(shù)個(gè)數(shù)，對(duì)此有如下結(jié)論［4］.

定理3設(shè)A是一個(gè)給定的有限整數(shù)序列，K是給定的正整數(shù)，設(shè)Ad表示A中被正整數(shù)d整除的所有整數(shù)組成的子序列，p1,p2,...,ps是K的所有的不同的素因數(shù)，以及表示序列Ad中的整數(shù)個(gè)數(shù)，那么序列A中所有與K既約的數(shù)的個(gè)數(shù)為

特別地，如果A是由1,2,···,[x]組成的序列，K=p1p2...ps,p1,p2,...,ps是不超過(guò)的全部素?cái)?shù)，這時(shí)有

這個(gè)表達(dá)式要利用K的全部素因數(shù)，式子有些繁瑣，下面我們引入Mobius 函數(shù)，它可以簡(jiǎn)化上面的公式，并且可以直接簡(jiǎn)單的證明上述廣義篩法原理.

定義（Mobiu函數(shù)）設(shè)變數(shù)d取正整數(shù)，p1,p2,...,pr是兩兩不同的素?cái)?shù)，μ(d)定義為

下面介紹Mobius函數(shù)一個(gè)最基本最重要最漂亮的性質(zhì)［3，5］.

定理4設(shè)n是正整數(shù)，我們有，當(dāng)n=1 時(shí)結(jié)論顯然成立.設(shè)n=，由定理4可知

3 Mobius函數(shù)在古典篩法上的應(yīng)用

根據(jù)Mobius函數(shù)的基本性質(zhì)，我們可以很容易很簡(jiǎn)潔的證明古典篩法及廣義篩法的正確性，下面我們來(lái)看看其在篩法上的妙用.

定理5（篩法原理）

證明

下面我們利用Mobius 函數(shù)的基本性質(zhì)來(lái)給出π(x)的一個(gè)漂亮的上界估計(jì)，對(duì)此先證明如下一個(gè)引理.

引理6設(shè)x≥y≥2,φ(x,y)表示不超過(guò)x且其素因數(shù)都大于y的所有正整數(shù)的個(gè)數(shù)，那么有

定理6（上界定理）設(shè)x≥10.pn表示第n個(gè)素?cái)?shù)，則一定存在正常數(shù)c使得

證明由定理6 可知，π(x)-π(y)=φ(x,y),2 ≤x≤y，從而有

現(xiàn)取y=lnx,則可得π(x)≤x(lnlnx)-1+lnx+2lnx≤x(lnlnx)-1+x0.7+lnx≤cx(lnlnx)-1.特別的，如果取x=pn,由上知道π(pn)=n,pn＞n，故可得出pn≥cnlnlnn,n≥5.

4 結(jié)束語(yǔ)

Mobius函數(shù)是一個(gè)重要的數(shù)論函數(shù)，它有許多極其獨(dú)特的性質(zhì)，可以給出歐拉函數(shù)的簡(jiǎn)潔證明，還給容斥原理提出了一個(gè)邏輯上清晰易懂的推理和闡述.本文應(yīng)用其性質(zhì)從理論上證明了廣義篩法及古典篩法的正確性和有效性，為尋找素?cái)?shù)和構(gòu)造素?cái)?shù)表提供一個(gè)簡(jiǎn)潔而實(shí)用的算法［7］，并給出了一個(gè)較精確的漂亮的上界估計(jì)，在理論上和實(shí)踐中都具有極其重要的價(jià)值.