• 汇集公众科学智慧交流科学思想见解
  • 点燃科学智慧火花构建互动交流平台
科学智慧火花
发表评论  11                

素数的判定定理及其证明

投稿时间:2017-07-12 18:07 投稿人:倪晓勇 【字号: 访问量:

1、引言

数论中一个最基本、最古老而当前仍然受到人们重视的问题就是素数的判定。在历史上,这个问题曾经吸引包括费马、欧拉、勒让德、高斯在内的大批数学家,他们花费了大量的时间和精力去研究这个问题。1801年高斯在《算术探究》中写到:把素数和合数区分开来是算术中最重要和有益的问题之一,科学本身的自尊要求人们采用一切可能的手段来探索去解决这个如此精美和著名的问题。

素数的判定这个问题具有很大的理论价值。因为素数在数论中占有特殊的地位,鉴别它们则成为最基本的问题。对素数判定的研究必然会丰富人们的精神财富。更为重要的是,素数判定具有很大的应用价值。在编码中,需要讨论某类有限域及其上的多项式,这类有限域就是由素数p所作成的Z/pZ,这就要求我们去寻找素数、判别素数。

素数的判定这个问题主要研究方法如下:1、Eratosthenes筛法;2、依赖于同余式的一些定理(特别是费马小定理、Wilson定理和欧拉对费马小定理的推广);3、利用黎曼猜想。关于具体详细内容可参考文献[1,2]。目前关于素数的判定定理很多,但它们有一个共同的缺点:对于一个很大很大的数,计算量很大。本文的素数判定定理很好的解决了这一问题。本文的核心思想是欧拉定理(欧拉对费马小定理的推广)的基础上引进雅可比符号便得到了素数的判定定理。由于任意一个偶数很容易识别不是素数,所以,我们只讨论奇数情况。

2、定理的证明

定理:若a为自然数,n为奇数,当(a,n)=1时,有an-1)/2≡(a/n)(mod n),则n为奇素数,这里(a/n)是雅可比符号。

证明:假设n为奇合数。(1)若n含有因子pb,其中,p为奇素数,b>1。由于an-1)/2≡(a/n)(mod n)推出an—1≡1(mod n),即an—1≡1(mod pb),即φ(pb)∣n-1,即得pb—1(p-1)∣n-1。由于pb—1∣n,故这不可能,因此,n不可能含有因子pb

(2)若n=p1p2pt,t2,其中,p1,p2,pt为互不相同的奇素数。由中国剩余定理,可取a1,使得(a1/p1)= -1而(a1/pi)= 1i=2,t。所以,(a1,n)=1且(a1/n= -1。对每个满足(an)=1a都有a(n-1)/2(a/n)(mod n),则有an11mod n),取a p2为p2的原根,即得a p2n11mod n),所以,(p2-1)∣(n-1),即(n-1)/ (p2-1)是个整数。现对a1,由欧拉定理可以得到a 1(p2-1)/2(a1/p2)(mod p2),我们有-1=a1/na (n-1)/2=(a 1(p2-1)/2(n-1)/ (p2-1)(a1/p2(n-1)/ (p2-1)=1(n-1)/ (p2-1)=1mod p2),即2=0mod p2),但p2是奇素数,这是不可能的。所以,n=p1p2pt不可能。

综上所述可以得出n是奇素数。所以,定理得证。

参考文献:

[1]孙琦,旷京华,素数判定与大数分解,[M],沈阳:辽宁教育出版社,1987。 

[2]P.里本伯姆,博大精深的素数,[M],北京:科学出版社,2007。

[3]潘承洞,潘承彪,初等数论,[M],北京:北京大学出版社,2003。