形如4k-1、4k+1、6k-1和6k+1(k∈Z+)的素數(shù)都有無窮多個

陳 川,宓 玲

1.齊魯工業(yè)大學(xué)(山東省科學(xué)院) 山東省計算中心(國家超級計算濟南中心) 算力互聯(lián)網(wǎng)與信息安全教育部重點實驗室,山東 濟南 250353; 2.山東省計算機網(wǎng)絡(luò)重點實驗室 山東省基礎(chǔ)科學(xué)研究中心(計算機科學(xué)),山東 濟南 250014; 3.齊魯工業(yè)大學(xué)(山東省科學(xué)院) 數(shù)學(xué)與統(tǒng)計學(xué)院,山東 濟南 250353

許多密碼算法都建立在大素數(shù)的基礎(chǔ)上,比如RSA公鑰密碼算法、ElGamal公鑰密碼算法、Rabin公鑰密碼算法、Diffie-Hellman密鑰交換協(xié)議、Shamir門限密鑰共享方案等[1]。特別地,在RSA、ElGamal和Rabin等公鑰密碼算法中,大素數(shù)或者是公鑰的一部分,或者可用于生成公鑰,每個用戶擁有的大素數(shù)應(yīng)各不相同,還需要定期更換。因此,密碼學(xué)中對素數(shù)的需求量是非常大的。考慮到密碼學(xué)的應(yīng)用范圍越來越廣泛,因此有必要對素數(shù)個數(shù)和素數(shù)分布進(jìn)行深入研究。

已知素數(shù)有無窮多個。若使用反證法,不難證明這個結(jié)論。另一方面,素數(shù)有非常多的分類方式。比如說,素數(shù)可以分為3種類型:2,形如4k+1的素數(shù)(5、13、17等),形如4k-1的素數(shù)(3、7、11等),其中k∈Z+。那么,形如4k-1和4k+1的素數(shù)是否分別有無窮多個?對該問題的研究具有現(xiàn)實意義:在Rabin公鑰密碼算法中,為保證順利解密,只能使用形如4k-1的素數(shù);在RSA公鑰密碼算法中,所使用的大素數(shù)一般都應(yīng)是安全素數(shù),大的安全素數(shù)也屬于形如4k-1的素數(shù)。再比如說,素數(shù)還可以分為4種類型:2,3,形如6k+1的素數(shù)(7、17、19等),形如6k-1的素數(shù)(5、11、17等),其中k∈Z+。那么,形如6k-1和6k+1的素數(shù)是否分別有無窮多個?

“形如4k-1的素數(shù)有無窮多個”,該結(jié)論曾作為例題出現(xiàn)在教材中[2],然而例題的證明邏輯性不強,說服力不夠。“形如4k+1的素數(shù)有無窮多個”和“形如6k-1的素數(shù)有無窮多個”,這兩個結(jié)論曾作為課后習(xí)題出現(xiàn)在教材中[2-4],截至目前,筆者尚未見到這兩個結(jié)論的證明?！靶稳?k+1的素數(shù)有無窮多個”,該結(jié)論的證明難度要更大一些,在證明該結(jié)論之前,本文先給出了一個有用的引理。

1 預(yù)備知識

定義1[5]已知p為素數(shù),若(a,p)=1且同余式x2≡a(modp)有解,則稱a為模p的平方剩余,否則稱a為模p的平方非剩余。

定義2[5]設(shè)m>1是整數(shù),a為正整數(shù)且(a,m)=1,則使得ax≡1(modm)成立的最小正整數(shù)x叫做a模m的階,記為ordm(a)。

引理1(Euler判定法則)[5]設(shè)p是奇素數(shù),(a,p)=1,則

引理2[5]設(shè)m>1是整數(shù),a為整數(shù)且(a,m)=1,若整數(shù)d使得ad≡1(modm),則有ordm(a)|d。

引理3(Euler定理)[5]設(shè)m>1是整數(shù),a為整數(shù)且(a,m)=1,則aφ(m)≡1(modm),其中φ(m)表示m的Euler函數(shù)。

2 主要結(jié)果

定理1 形如4k-1(k∈Z+)的素數(shù)有無窮多個。

證明：(反證法)假設(shè)形如4k-1的素數(shù)僅有有限多個,不妨設(shè)有n個,分別為:p1,p2,…,pn,其中n為某個正整數(shù)。

構(gòu)造一個新的整數(shù):M=4p1p2…pn-1。

首先證明M不是素數(shù)。已知素數(shù)僅有3種類型:2,形如4k+1的素數(shù),形如4k-1的素數(shù),其中k∈Z+。(1)由于M是一個外在形式如4k-1的數(shù),所以它不可能是2、形如4k+1的素數(shù)。(2)根據(jù)假設(shè),形如4k-1的素數(shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個形如4k-1的素數(shù)。綜上,M不是素數(shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。M的素因子只可能屬于3種類型:2,形如4k+1的素數(shù),形如4k-1的素數(shù),其中k∈Z+。顯然,2M。另一方面,已假設(shè)形如4k-1的素數(shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。由此可得,合數(shù)M的所有素因子不包括2,也不包括形如4k-1的素數(shù),即M的所有素因子都是形如4k+1的素數(shù)。因此,M所有素因子的乘積與1模4同余。然而,M是與-1模4同余。矛盾。

所以,形如4k-1的素數(shù)有無窮多個。

引理4已知素數(shù)p>2,若-1是模p的平方剩余,則p≡1(mod 4)。

定理2形如4k+1(k∈Z+)的素數(shù)有無窮多個。

證明：(反證法)假設(shè)形如4k+1的素數(shù)僅有有限多個,不妨設(shè)有n個,分別為:p1,p2,…,pn,其中n為某個正整數(shù)。

構(gòu)造一個新的整數(shù):M=4(p1p2…pn)2+1。

首先證明M不是素數(shù)。已知素數(shù)僅有3種類型:2,形如4k+1的素數(shù),形如4k-1的素數(shù),其中k∈Z+。(1)由于M是一個外在形式如4k+1的數(shù),所以它不可能是2、形如4k-1的素數(shù)。(2)根據(jù)假設(shè),形如4k+1的素數(shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個形如4k+1的素數(shù)。綜上,M不是素數(shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。由于2M,可知M肯定存在大于2的素因子。

設(shè)q>2是M的一個素因子,則有M≡4(p1p2…pn)2+1≡0(modq),可得(2p1p2…pn)2≡-1(modq)。所以存在x≡2p1p2…pn(modq)且x∈{1,2,…,q-1},使得x2≡-1(modq),即-1是模q的平方剩余。由引理4可知,q≡1(mod 4)。這意味著M存在形如4k+1的素因子q。然而根據(jù)假設(shè),形如4k+1的素數(shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

所以,形如4k+1的素數(shù)有無窮多個。

定理3形如6k-1(k∈Z+)的素數(shù)有無窮多個。

證明：(反證法)假設(shè)形如6k-1的素數(shù)僅有有限多個,不妨設(shè)有n個,分別為:p1,p2,…,pn,其中n為某個正整數(shù)。

構(gòu)造一個新的整數(shù):M=(p1p2…pn)2-2。

首先證明M不是素數(shù)。已知素數(shù)包括4種類型:2,3,形如6k+1的素數(shù),形如6k-1的素數(shù),其中k∈Z+。(1)由于M是一個外在形式如6k-1的數(shù),所以它不可能是2、3、形如6k+1的素數(shù)。(2)根據(jù)假設(shè),形如6k-1的素數(shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個形如6k-1的素數(shù)。綜上可知,M不是素數(shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。由于M是一個外在形式如6k-1的數(shù),因此2M且3M,可知M肯定存在大于3的素因子。設(shè)q>3是M的一個素因子,則q是形如6k+1或6k-1的素數(shù)。所以,M的素因子或者形如6k+1,或者形如6k-1。

接下來證明:M的素因子不可能全都形如6k+1。若M的素因子全都形如6k+1,則M所有素因子的乘積與1模6同余,而M是與-1模6同余,矛盾。

綜上可得,M至少存在一個形如6k-1的素因子。然而根據(jù)假設(shè),形如6k-1的素數(shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

所以,形如6k-1的素數(shù)有無窮多個。

引理5設(shè)素數(shù)p>3是x2-x+1(x∈Z)的因子,則p≡1(mod 6)。

證明：首先證明(x,p)=1。若(x,p)≠1,則p|x,因此x≡0(modp),所以x2-x+1≡0-0+1≡1(modp)。然而,根據(jù)已知條件x2-x+1≡0(modp)。矛盾。

(1)證明ordp(x)≠1。若ordp(x)=1,則x1≡1(modp),所以x2-x+1≡1-1+1≡1(modp)。然而,根據(jù)已知條件x2-x+1≡0(modp)。矛盾。

(2)證明ordp(x)≠2。若ordp(x)=2,則x1?1(modp)且x2≡1(modp)。由x2≡1(modp)可知,x≡±1(modp),又因x?1(modp),可得x≡-1(modp),因此x2-x+1≡1+1+1≡3(modp)。然而,根據(jù)已知條件x2-x+1≡0(modp)。矛盾。

綜上可知,ordp(x)=6。

因為(x,p)=1,由引理3可知xφ(p)≡xp-1≡1(modp)。根據(jù)引理2,ordp(x)|p-1,即6|p-1。因此,p≡1(mod 6)。

定理4形如6k+1(k∈Z+)的素數(shù)有無窮多個。

證明：(反證法)假設(shè)形如6k+1的素數(shù)僅有有限多個,不妨設(shè)有n個,分別為:p1,p2,…,pn,其中n為某個正整數(shù)。

由p1≡1(mod 6),p2≡1(mod 6),…,pn≡1(mod 6)可知,p1p2…pn≡1(mod 6),所以M≡1-1+1≡1(mod 6)。

首先證明M不是素數(shù)。已知素數(shù)包括4種類型:2,3,形如6k+1的素數(shù),形如6k-1的素數(shù),其中k∈Z+。(1)由于M是一個外在形式如6k+1的數(shù),所以它不可能是2、3、形如6k-1的素數(shù)。(2)根據(jù)假設(shè),形如6k+1的素數(shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個形如6k+1的素數(shù)。綜上可知,M不是素數(shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。由于M是一個外在形式如6k+1的數(shù),因此2M且3M,可知M肯定存在大于3的素因子。設(shè)q>3是M的一個素因子。根據(jù)引理5,q≡1(mod 6),即M存在一個形如6k+1的素因子q。然而根據(jù)假設(shè),形如6k+1的素數(shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

所以,形如6k+1的素數(shù)有無窮多個。