1. 引言
关于一个正整数是否是一个素数的问题或者称素性判定问题是数学上一个非常古老的问题,随着近年来计算机技术和算法数论飞速的发展,这一问题近年来取得了丰富的成果。在所有数目中,存在一些特殊形式的数,例如Mersenne数、Ferma数等等,针对这些特殊形式的数,有一些特殊的判据,例如Pipin判据。
在本文中,主要应用几个适用于任何形式的数的被称为
方法的初等判据,这些判据都要求知道
的所有因子或部分因子的信息。
在这一节中,我们首先回顾素性判定的几个初等结果,150多年来,Lucas首先证明了一个初等的素数判定定理:
定理1 (Lucas, 1876) (见 [1] [2] [3] )设n是一个正整数,如果存在正整数a,使得对于小于
的所有素因子q成立
,
则n必是一个素数。
上面这个结果,经常会被称为Lucas判据,但已有文献指出,它实际上并不是由法国数学家Luucas提出的(其中 [1] 是在法国期刊上发表的一篇关于Lucas的传记),而是由美国数学家D. H. Lehmer [3] 提出的(当时他还是个学生,发表论文当年,他从伯克利毕业,获得物理学学士。后前往芝加哥大学师从L. E. Dikson攻读数学博士学位 [4] 。 [2] 指出D. H. Lehmer是Lucas的主要继承人,他还完善了与Mersenne数有关的素数判据)。
1927年D. H. Lehmer建立了下面的基本结果。
定理2 (D. H. Lehmer, 1927) [3] 设n是一个正整数,并且对n−1的所有素因子p,存在一个整数a使得
,
则n必是一个素数。
上面这个定理要求对
的所有的素因子都存在一个统一的具有上述性质的a,这对有些问题是不方便的,针对这一缺陷,1975年J. Brillhart,D. H. Lehmer,L. Selfridge对此做出了实质性的一个改进,提出了下面的:
定理3 (J. Brillhart, D. H. Lehmer, L. Selfridge, 1975) (见 [5] [6] )设n是一个正整数
如果对每一个
都存在一个整数
使得
则n必是一个素数。
上面几个定理都要求知道n−1的所有的因子的信息,这是一个很强的要求和限制。上面的1975 的论文指出如果能对n−1的部分分解,得出一个足够大的素因子,那么就会有一个对定理3的减小计算量的改进,这就是下面的Proth定理。
定理4 (Prorh [7] )设n是一个奇数,
,其中p是一个奇素数且满足
,同时又存在正整数a使得
则n必是一个素数。
上面这个定理要求p必须是一个素数。这仍然在p不大的情况下,并不能有效的减小计算量,结合Pocklington在1914年提出的一个定理,可以解除这一限制,从而可以得出以下的定理。
定理5 (Proth, Pocklington) ( [7] [8] )设
,其中F是
的已经分解出来的部分(即已知的素因子及其幂次),R是
的未分解部分(即
,我们不知道它是素数还是合数,或者即使知道它是一个合数但并不能知道它的素因子分解式。)并且
,若(F,R) = 1,且对F的每个素因子
,都存在一个正整数
使得
,
,
则n必是一个素数。
2. 两个应用例子
本节中的两个例子和下面第3节中的R19是素数的证明, [7] 都已讨论过,但由于 [7] 中的有关计算都是错误的,因此并不有效。为了减小篇幅,本文就不一一加以对比,具体指出 [7] 中的错误在哪里,读者只要自行对照本文和 [7] 便可知道。
例1. 证明4093是素数
本题用手算 + 一个手持科学计算器解决。
证明 设n = 4093,则
。
,
,
,
。
取
,则
,
,
,
。
对模4093,有
,
,
,
,
,
,
(1)
,
,
,
,
,
,
(2)
,
,
,
,
,
(3)
,
(4)
(5)
由(1)~(5)和定理2即得4093是一个素数。
例2. 证明823,001是一个素数
本例用手算 + Matheatica12.0完成。
证明 设n = 823,001,则
其中m = 1000,p = 823是一个素数。
。 (6)
对模823,001,取a = 2,则
,
,
,
,
,
,
,
,
,
(7)
,
,
,
,
,
,
,
,
,
,
,
,
(8)
由(6) (7) (8)和定理4即得833,001是一个素数。
3. 全一数R19是素数的证明
全一数(Repunits)是指各位数字都是1的数字,一般用Rn表示,其中n指全一数中1的个数( [7] [8] [9] [10] )。在1904年出版的坎特伯雷难题集中(见 [9] ),有一个问题是问
(19个1)是否是一个素数,这问题一直没有解决,直到1978年以后,文献中才提到有人用n−1方法解决了此问题,但并没有见到具体的解法(见 [7] - [13] )。在文献 [7] 中给出了一个证明,不过由于这个证明一开始就出现了一个明显的计算错误而无效(在 [8] 中设
(19个1),并说
,其中
,由于显然
的因子必须是
的因子,而
并没有91这个因子,因此这一分解显然是错误的,而以下的计算也就无效了)。
以下完全借助于Mathematica12.0完成计算。
下面我们证明R19是一个素数。
设n = 1111111111111111111,则
其中
,
。
由于
,所以
(9)
其中
,
,
,
,
,
。
对模n = 1111111111111111111有
对
,取a = 2,则
,
,
,
,
,
,
,
(10)
,
,
,
,
,
,
,
,
(11)
,
,
,
,
(12)
,
,
,
,
(13)
,
,
,
,
(14)
对
,取a = 3,
,
,
(15)
,
,
(16)
由(9)~(16)和定理5即得R19是一个素数。
讨论:本文的例子及第3节的方法提供了素性判定的一种初等方法及其具体的集散过程,具体的应用成果就是解决了R19的素性判定。这可对类似问题给出一种参考方法,从本文的方法看出这种方法随着n的增大,难度将越来越大。因此对大整数的素性判定是否能继续应用这种方法需要继续探讨。