Advances in Applied Mathematics
Vol.
13
No.
05
(
2024
), Article ID:
87570
,
7
pages
10.12677/aam.2024.135193
坎特伯雷难题集中全一数R19是素数的证明
冯贝叶
中国科学院数学与系统科学研究院应用数学所,北京
收稿日期:2024年4月23日;录用日期:2024年5月17日;发布日期:2024年5月28日
![](http://html.hanspub.org/file/14-2623889x1_hanspub.png?20240529082440485)
摘要
一个正整数的素性判别是数论中一个有意义和有兴趣的问题,全一数R19是否是一个素数的问题虽在文献中提到已被用 法解决,但国内一直未见有证明方法的介绍,本文借助于数学软件Mathematica12.0用个人计算机证明了坎特伯雷难题集中全一数R19是一个素数。这对证明其他整数的素性判定提供了一个参考。
关键词
全一数R19,素数,Mathematica12.0,个人计算机
![](http://html.hanspub.org/file/14-2623889x3_hanspub.png?20240529082440485)
Proof That Repunit R19 in the Canterbury Problem Set Is a Prime Number
Beiye Feng
Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing
Received: Apr. 23rd, 2024; accepted: May 17th, 2024; published: May 28th, 2024
![](http://html.hanspub.org/file/14-2623889x4_hanspub.png?20240529082440485)
ABSTRACT
The primality criterion of a positive integer is a meaningful and interesting problem in number theory. Although the question of whether Repunit R19 is a prime has been solved by the method in literature, there is no introduction to a proven method in China. This article uses the mathematical software Mathematical12.0 to prove on a personal computer that the Repunit R19 in the Canterbury problem set is a prime number. This provides a reference for proving the primality of other integers.
Keywords:Repunit R19, Prime Number, Mathematica12.0, Personal Computer
Copyright © 2024 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
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的增大,难度将越来越大。因此对大整数的素性判定是否能继续应用这种方法需要继续探讨。
文章引用
冯贝叶. 坎特伯雷难题集中全一数R19是素数的证明
Proof That Repunit R19 in the Canterbury Problem Set Is a Prime Number[J]. 应用数学进展, 2024, 13(05): 2062-2068. https://doi.org/10.12677/aam.2024.135193
参考文献
- 1. Lucas, E. (1876) Sur la recherche des grands nombres premiers. Association Française pour l'Avancement des Sciences, 5, 61-68.
- 2. Décaillot, A.M. and Lucas, L.É. (1998) Théorie Instrumentation. Revue d'Histoire des Mathématiques, No. 2, 191-236.
- 3. Lehmer, D.H. (1927) Test for Primality by Converse of Fermat’s Theorem. Bulletin of the American Mathematical Society, 33, 327-340.
- 4. Derrick Henry Lehmer (1905-1991) Biography, MacTutor History of Mathematics Archive. https://mathshistory.st-andrews.ac.uk/Biographies/Lehmer_Derrick/
- 5. Brillhart, J., Lehmer, D.H. and Selfridge, J.L. (1975) New Primality Criteria and Factorization of 2^m±1. Mathematics of Computation, 29, 620-647. https://doi.org/10.2307/2005583
- 6. Pocklington, H.C. (1914) The Determination of the Prime or Composite Nature of Large Numbers by Fermat’s Theorem.
- 7. 孙琦, 旷京华. 素数判定与大数分解[M]. 哈尔滨: 哈尔滨工业大学出版社, 2014.
- 8. 刘醉白. 素数证明: 在满足费马小定理的部分条件下, 结合图中条件, 请问如何证明n是一个素数? [EB/OL]. https://www.zhihu.com/answer/574767625, 2024-04-25.
- 9. (英)亨利∙杜德尼. 坎特伯雷趣题[M]. 陈以鸿, 译. 上海: 上海科技教育出版社, 2007.
- 10. Wells, D. (2005) Prime Numbers, the Most Mysterious Figures in Math. Wiley, Hoboken.
- 11. Ribenboim, P. (2006) The Little Book of Bigger Primes. Springer-Verlag, New York.
- 12. 颜松远. 计算数论[M]. 第二版. 杨思熳, 刘巍, 齐璐璐, 陶红伟, 译. 北京: 清华大学出版社, 2008.
- 13. Yates, S. (1982) Repunits and Repetends. Star Publishing Co. Inc., Boynton Beach.