素數(shù)和孿生素數(shù)判定方法①

周忠奇, 周師潔

(1.湖北煤炭地質(zhì)局,湖北 武漢 430070;2.北京新東方集團武漢學校，湖北 武漢 430070)

0 引 言

1 引 理

2 定 理

定理1: 奇數(shù)m為素數(shù)當且僅當

證: 必要條件:若m為素數(shù)，則

根據(jù)引理有

定理2: 設p≡1(mod 4),則p,p+2均為素數(shù)的充分必要條件是

證: 必要條件:若p,p+2皆為素數(shù)且p≡1(mod 4),根據(jù)定理1,有

又因p≡-2(modp+2),p2≡4(modp+2)和-5p≡10(modp+2)所以

根據(jù)定理1和p+2≡-1(mod 4)

由(1)和(2)得

必要條件成立.

因(p,8)=1,由(3)可得

根據(jù)定理1可知p為素數(shù).再由(4)可得

因(p+2,2)=1,p+2≡-1(mod 4)所以

或

根據(jù)定理1知p+2為素數(shù).充分條件成立.

定理3:設p≡-1(mod 4),則p,p+2均為素數(shù)的充分必要條件是

證: 必要條件:若p,p+2皆為素數(shù)，p≡-1(mod 4),根據(jù)定理1有

又因p≡-2(modp+2),p2≡4(modp+2)和5p≡-10(modp+2)所以

根據(jù)定理1和p+2≡1(mod 4)

由(5)和(6)得

必要條件成立.

因(p,8)=1,由(7)可得

根據(jù)定理1可知p為素數(shù).再由(8)可得

因(p+2,2)=1,p+2≡1(mod 4),所以

根據(jù)定理1知p+2為素數(shù).充分條件成立.

3 結(jié) 語

以上素數(shù)和孿生素數(shù)的判定方法，只是對素數(shù)和孿生素數(shù)的一種刻畫.由于這種判定方法都要計算所有不大于奇數(shù)m的連乘積的平方模m或模m(m+2),所以，這種判定方法在實際計算中不是高效率的.對于孿生素數(shù)，目前尚未發(fā)現(xiàn)有用一個式子且能在多項式時間內(nèi)完成檢測的方法.