Mobius 函數在古典篩法上的應用

鄧從政

（凱里學院，貴州凱里 556011）

0 引言

素數是數論中被研究最廣泛的一類數，除在同余理論、整除理論、不定方程理論及指數和原根這些基礎問題經常用到之外，在密碼學和編碼學上也有廣泛地應用，如橢圓曲線密碼、RSA 密碼、圓錐曲線密碼三大公鑰密碼體制的加密和解密都依賴于大素數［1］.長期以來找出一個大整數范圍內的所有素數是數論中被研究最廣泛的一個課題，其中素數的數量、素數的分布、素數表的構造都依賴于現存找到的素數，古典篩法可以找出不超出給定的一個正整數范圍內的所有素數，而且十分有效，它是構造素數表的一個實用方法［2］.本文通過Mobius函數及其獨特性質從理論上證明古典篩法的有效性，為尋找素數提供一個簡潔而實用的算法.

1 古典篩法原理

1.1 算術基本定理

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

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

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

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

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

特別地，我們取s=2，這就是古典篩法的原理.

推理3設整數a≥2，則必有素數p|a且滿足

1.2 古典篩法的算法與應用

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

（3）刪除1和[1,n]范圍內所有p的倍數ps≤n；

（4）刪除以上倍數后剩余的數即為所求的素數.

案例用古典篩法找出不超過300的所有素數.

（2）找出[1,17]范圍內的所有素數：2，3，5，7，11，13，17；

（3）刪除1和[1,300]范圍內所有2，3，5，7，11，13，17的倍數；

（4）刪除以上倍數后剩余的數為：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.

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

2 Mobius函數及其獨特性質

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

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

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

由此可得：

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

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

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

特別地，如果A是由1,2,···,[x]組成的序列，K=p1p2...ps,p1,p2,...,ps是不超過的全部素數，這時有

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

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

下面介紹Mobius函數一個最基本最重要最漂亮的性質［3，5］.

定理4設n是正整數，我們有，當n=1 時結論顯然成立.設n=，由定理4可知

3 Mobius函數在古典篩法上的應用

根據Mobius函數的基本性質，我們可以很容易很簡潔的證明古典篩法及廣義篩法的正確性，下面我們來看看其在篩法上的妙用.

定理5（篩法原理）

證明

下面我們利用Mobius 函數的基本性質來給出π(x)的一個漂亮的上界估計，對此先證明如下一個引理.

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

定理6（上界定理）設x≥10.pn表示第n個素數，則一定存在正常數c使得

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

現取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 結束語

Mobius函數是一個重要的數論函數，它有許多極其獨特的性質，可以給出歐拉函數的簡潔證明，還給容斥原理提出了一個邏輯上清晰易懂的推理和闡述.本文應用其性質從理論上證明了廣義篩法及古典篩法的正確性和有效性，為尋找素數和構造素數表提供一個簡潔而實用的算法［7］，并給出了一個較精確的漂亮的上界估計，在理論上和實踐中都具有極其重要的價值.