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

陳 川,宓 玲

1.齊魯工業大學(山東省科學院) 山東省計算中心(國家超級計算濟南中心) 算力互聯網與信息安全教育部重點實驗室,山東 濟南 250353; 2.山東省計算機網絡重點實驗室 山東省基礎科學研究中心(計算機科學),山東 濟南 250014; 3.齊魯工業大學(山東省科學院) 數學與統計學院,山東 濟南 250353

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

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

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

1 預備知識

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

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

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

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

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

2 主要結果

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

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

構造一個新的整數:M=4p1p2…pn-1。

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

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

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

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

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

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

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

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

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

設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。然而根據假設,形如4k+1的素數僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

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

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

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

構造一個新的整數:M=(p1p2…pn)2-2。

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

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

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

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

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

引理5設素數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)。然而,根據已知條件x2-x+1≡0(modp)。矛盾。

(1)證明ordp(x)≠1。若ordp(x)=1,則x1≡1(modp),所以x2-x+1≡1-1+1≡1(modp)。然而,根據已知條件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)。然而,根據已知條件x2-x+1≡0(modp)。矛盾。

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

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

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

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

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

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

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