坎特伯雷难题集中全一数R19是素数的证明

Proof That Repunit R19 in the Canterbury Problem Set Is a Prime Number

摘要: 一个正整数的素性判别是数论中一个有意义和有兴趣的问题，全一数R19是否是一个素数的问题虽在文献中提到已被用n−1法解决，但国内一直未见有证明方法的介绍，本文借助于数学软件Mathematica12.0用个人计算机证明了坎特伯雷难题集中全一数R19是一个素数。这对证明其他整数的素性判定提供了一个参考。

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 then−1method 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.

1. 引言

关于一个正整数是否是一个素数的问题或者称素性判定问题是数学上一个非常古老的问题，随着近年来计算机技术和算法数论飞速的发展，这一问题近年来取得了丰富的成果。在所有数目中，存在一些特殊形式的数，例如Mersenne数、Ferma数等等，针对这些特殊形式的数，有一些特殊的判据，例如Pipin判据。

在本文中，主要应用几个适用于任何形式的数的被称为 $n-\text{1}$ 方法的初等判据，这些判据都要求知道 $n-\text{1}$ 的所有因子或部分因子的信息。

在这一节中，我们首先回顾素性判定的几个初等结果，150多年来，Lucas首先证明了一个初等的素数判定定理：

定理1 (Lucas, 1876) (见 [1] [2] [3] )设n是一个正整数，如果存在正整数a，使得对于小于 $n-\text{1}$ 的所有素因子q成立

$a^{n-1}\equiv 1\left(\mathrm{mod}n\right)$

$a^q\cancel{\equiv }1\left(\mathrm{mod}n\right)$ ,

则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使得

$a^{n-1}\equiv 1\left(\text{mod}n\right)$ ,

$a^{\frac{n-1}{\cancel{p}}}\cancel{\equiv }1\left(\text{mod}n\right)$

则n必是一个素数。

上面这个定理要求对 $n-\text{1}$ 的所有的素因子都存在一个统一的具有上述性质的a，这对有些问题是不方便的，针对这一缺陷，1975年J. Brillhart，D. H. Lehmer，L. Selfridge对此做出了实质性的一个改进，提出了下面的：

定理3 (J. Brillhart, D. H. Lehmer, L. Selfridge, 1975) (见 [5] [6] )设n是一个正整数

$n-1=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$

如果对每一个 $p_i$ 都存在一个整数 $a_i$ 使得

$a_i^{n-1}\equiv 1\left(\mathrm{mod}n\right)$

$a_i^{\frac{n-1}{p_i}}\cancel{\equiv }1\left(\mathrm{mod}n\right)$

则n必是一个素数。

上面几个定理都要求知道n−1的所有的因子的信息，这是一个很强的要求和限制。上面的1975 的论文指出如果能对n−1的部分分解，得出一个足够大的素因子，那么就会有一个对定理3的减小计算量的改进，这就是下面的Proth定理。

定理4 (Prorh [7] )设n是一个奇数， $n-\text{1}=mp$ ，其中p是一个奇素数且满足 $2p+1>\sqrt{n}$ ，同时又存在正整数a使得

$a^{n-1}\equiv 1\left(\mathrm{mod}n\right)$

$a^m\cancel{\equiv }1\left(\mathrm{mod}n\right)$

则n必是一个素数。

上面这个定理要求p必须是一个素数。这仍然在p不大的情况下，并不能有效的减小计算量，结合Pocklington在1914年提出的一个定理，可以解除这一限制，从而可以得出以下的定理。

定理5 (Proth, Pocklington) ( [7] [8] )设 $n-\text{1}=PR$ ，其中F是 $n-\text{1}$ 的已经分解出来的部分(即已知的素因子及其幂次)，R是 $n-\text{1}$ 的未分解部分(即 $R=\frac{n-1}{F}$ ，我们不知道它是素数还是合数，或者即使知道它是一个合数但并不能知道它的素因子分解式。)并且 $F>\sqrt{n}$ ，若(F,R) = 1，且对F的每个素因子 $p_i$ ，都存在一个正整数 $a_i$ 使得

$a_i^{n-1}\equiv 1\left(\mathrm{mod}n\right)$ ,

$\left(a_i^{\frac{n-1}{p_i}}-1,n\right)=1$ ,

则n必是一个素数。

2. 两个应用例子

本节中的两个例子和下面第3节中的R19是素数的证明， [7] 都已讨论过，但由于 [7] 中的有关计算都是错误的，因此并不有效。为了减小篇幅，本文就不一一加以对比，具体指出 [7] 中的错误在哪里，读者只要自行对照本文和 [7] 便可知道。

例1. 证明4093是素数

本题用手算 + 一个手持科学计算器解决。

证明 设n = 4093，则 $n-1=4092=31\times 11\times 3\times 2^2$ 。

$p_1=31$ ， $p_2=11$ ， $p_3=3$ ， $p_4=2$ 。

取 $a=2$ ，则 $m_1=2^{\frac{n-1}{p_1}}=2^{132}$ ， $m_2=2^{\frac{n-1}{p_2}}=2^{372}$ ， $m_3=2^{\frac{n-1}{p_3}}=2^{1364}$ ， $m_4=2^{\frac{n-1}{p_4}}=2^{2046}$ 。

对模4093，有

$2^{10}\equiv 1024$ ， $2^{20}\equiv {1024}^2\equiv 768$ ， $2^{40}\equiv {768}^2\equiv 432$ ， $2^{60}\equiv {768}^3\equiv 243$ ，

$2^{100}\equiv 432\times 243\equiv 2651$ ， $2^{30}\equiv 1024\times 768\equiv 576$ ， $2^{32}\equiv 576\times 4\equiv 2304$

$2^{132}\equiv 2651\times 2304\equiv 1148\cancel{\equiv }1\left(\mathrm{mod}4093\right)$ (1)

$2^{200}\equiv {2651}^2\equiv 120$ ， $2^{200}\equiv {2651}^2\equiv 120$ ， $2^{30}\equiv 2^{10\times 3}\equiv {1024}^3\equiv 576$ ，

$2^{31}\equiv 576\times 2\equiv 1152$ ， $2^{93}\equiv {1152}^3\equiv 2355$ ， $2^{186}\equiv {2355}^2\equiv 10$ ，

$2^{372}\equiv {10}^2\equiv 100\cancel{\equiv }1\left(\mathrm{mod}4093\right)$ (2)

$2^{400}\equiv {120}^2\equiv 2121$ ， $2^{800}\equiv {2121}^2\equiv 434$ ， $2^{1000}\equiv 120\times 434\equiv 2964$ ，

$2^{120}\equiv {243}^2\equiv 1747$ ， $2^{240}\equiv {1747}^2\equiv 2724$ ， $2^{248}\equiv 2724\times 256\equiv 1534$

$2^{1116}\equiv 2^{372\times 3}\equiv {100}^3\equiv 1308$

$2^{1364}\equiv 2^{268}\times 2^{1116}\equiv 1534\times 1308\equiv 902\cancel{\equiv }1\left(\mathrm{mod}4093\right)$ (3)

$2^{2000}\equiv {2964}^2\equiv 1718$ ， $2^{46}\equiv 432\times 64\equiv 3090$

$2^{2046}\equiv 1718\times 3090\equiv 4092\equiv -1\left(\mathrm{mod}4093\right)$ (4)

$2^{4092}\equiv 1\left(\mathrm{mod}4093\right)$ (5)

由(1)~(5)和定理2即得4093是一个素数。

例2. 证明823,001是一个素数

本例用手算 + Matheatica12.0完成。

证明 设n = 823,001，则 $n-1=823000=1000\times 823=mp$ 其中m = 1000，p = 823是一个素数。

$2p+1=1847>908>\sqrt{823001}=\sqrt{n}$ 。 (6)

对模823,001，取a = 2，则

$2^{10}\equiv 1024$ ， $2^{20}\equiv {1024}^2\equiv 225575$ ， $2^{23}\equiv 225575\times 8\equiv 158598$ ，

$2^{25}\equiv 225575\times 32\equiv 634392$ ， $2^{50}\equiv {634392}^2\equiv 782658$ ， $2^{100}\equiv {782658}^2\equiv 484672$ ，

$2^{200}\equiv {484672}^2\equiv 241157$ ， $2^{400}\equiv {241157}^2\equiv 155985$ ， $2^{800}\equiv {155985}^2\equiv 118661$ ，

$2^m\equiv 2^{1000}\equiv 118661\times 241157\equiv 186007\cancel{\equiv }1\left(\mathrm{mod}823001\right)$ (7)

$2^{823}\equiv 118661\times 158598\equiv 656412$ ， $2^{1646}\equiv {656412}^2\equiv 301201$ ，

$2^{3292}\equiv {301201}^2\equiv 173168$ ， $2^{4115}\equiv 173168\times 656412\equiv 770101$ ，

$2^{8230}\equiv {770101}^2\equiv 206600$ ， $2^{16460}\equiv {206600}^2\equiv 259137$ ，

$2^{20575}\equiv 143927\times 770101\equiv 380357$ ， $2^{41150}\equiv {380357}^2\equiv 216664$ ，

$2^{82300}\equiv {216664}^2\equiv 134857$ ， $2^{102875}\equiv 134857\times 380357\equiv 266624$ ，

$2^{205750}\equiv {266624}^2\equiv -1$ ， $2^{411500}\equiv {\left(-1\right)}^2\equiv 1$ ，

$2^{n-1}\equiv 2^{823000}\equiv 2^{411500\times 2}\equiv 1^2\equiv 1$ (8)

由(6) (7) (8)和定理4即得833,001是一个素数。

3. 全一数R19是素数的证明

全一数(Repunits)是指各位数字都是1的数字，一般用Rn表示，其中n指全一数中1的个数( [7] [8] [9] [10] )。在1904年出版的坎特伯雷难题集中(见 [9] )，有一个问题是问 $\text{11}\cdots \text{1}$ (19个1)是否是一个素数，这问题一直没有解决，直到1978年以后，文献中才提到有人用n−1方法解决了此问题，但并没有见到具体的解法(见 [7] - [13] )。在文献 [7] 中给出了一个证明，不过由于这个证明一开始就出现了一个明显的计算错误而无效(在 [8] 中设 $n=11\cdots 1$ (19个1)，并说 $n-\text{1}=F_1{R}_1$ ，其中 $F_1=3333330=2\times 3^2\times 5\times 11$ $\times 31\times 37\times 91$，由于显然 $F_1$ 的因子必须是 $n-\text{1}$ 的因子，而 $n-\text{1}$ 并没有91这个因子，因此这一分解显然是错误的，而以下的计算也就无效了)。

以下完全借助于Mathematica12.0完成计算。

下面我们证明R19是一个素数。

设n = 1111111111111111111，则 $n-1=1111111111111111110=FR$

其中 $F=1062200958=52579\times 37\times 13\times 7\times 3\times 2$ ， $R=\frac{n-1}{F}$ 。

由于 ${1062200958}^2-1111111111111111111>0$ ，所以

$F=1062200958>\sqrt{1111111111111111111}=\sqrt{n}$ (9)

$F=p_1{p}_2{p}_3{p}_4{p}_5{p}_6$

其中 $p_1=52579$ ， $p_2=37$ ， $p_3=13$ ， $p_4=7$ ， $p_5=3$ ， $p_6=2$ 。

对模n = 1111111111111111111有

$m_1=\frac{n-1}{p_1}=333667\times 37\times 19\times 13\times 11\times 7\times 5\times 3^2\times 2$

对 $p_1,p_2,p_3,p_4$ ，取a = 2，则

$2^{333667}\equiv \text{686033429761844421}=r_1$ ，

$r_1^{52579}\equiv {\text{686033429761844421}}^{52579}\equiv \text{10833065941756886}=r_2$ ，

$r_2^{37}\equiv {\text{10833065941756886}}^{37}\equiv \text{25038712834380145}=r_3$ ，

$r_3^{19}\equiv {\text{25038712834380145}}^{19}\equiv \text{659804149831953774}=r_4$ ，

$r_4^{13}\equiv 659{\text{804149831953774}}^{13}\equiv \text{219095598444019794}=r_5$ ，

$r_5^{11}\equiv {\text{219095598444019794}}^{11}\equiv \text{314626805515060544}=r_6$ ，

$r_6^{35}\equiv {\text{314626805515060544}}^{35}\equiv \text{933000903779960656}=r_7$ ，

$2^{n-1}\equiv r_7^{18}\left(\mathrm{mod}n\right)\equiv r_7^{18}\left(\mathrm{mod}1111111111111111111\right)\equiv 1$ (10)

$m_1=\frac{n-1}{p_1}=21132222201090=333667\times 37\times 19\times 13\times 11\times 7\times 5\times 3^2\times 2$ ，

$2^{333667}\equiv 686033429761844421=r_{11}$ ，

$2^{37\times 333667}\equiv r_{11}^{37}\equiv 980823581211748537=r_{12}$ ，

$2^{19\times 37\times 333667}\equiv r_{12}^{19}\equiv \text{1077616254044116588}=r_{13}$ ，

$2^{13\times 19\times 37\times 333667}\equiv r_{13}^{13}\equiv 62778917655367695=r_{14}$ ，

$2^{11\times 13\times 19\times 37\times 333667}\equiv r_{14}^{11}\equiv \text{191685422932804908}=r_{15}$ ，

$2^{5\times 7\times 11\times 13\times 19\times 37\times 333667}\equiv r_{15}^{35}\equiv \text{648182400500105952}=r_{16}$ ，

$2^{m_1}\equiv 2^{2\times 3^2\times 5\times 7\times 11\times 13\times 19\times 37\times 333667}\equiv r_{16}^{18}\equiv 390068371006902754$ ，

$\left(2^{m_1}-1,n\right)=1$ (11)

$m_2=\frac{n-1}{p_2}=333667\times 52579\times 19\times 13\times 11\times 7\times 5\times 3^2\times 2$ ，

$2^{19\times 13\times 11\times 7\times 5\times 3^2\times 2}\equiv 828428136044625569=r_{21}$ ，

$2^{333667\times 19\times 13\times 11\times 7\times 5\times 3^2\times 2}\equiv r_{21}^{333667}\equiv 564791157091879790=r_{22}$ ，

$2^{m_2}\equiv r_{22}^{52579}\equiv \text{207863854007559622}$ ，

$\left(2^{m_2}-1,n\right)=1$ (12)

$m_3=\frac{n-1}{p_3}=333667\times 52579\times 37\times 7\times 3^2\times 2$ ，

$2^{37\times 7\times 3^2\times 2}\equiv \text{716086219179556333}=r_{31}$ ，

$2^{333667\times 37\times 7\times 3^2\times 2}\equiv r_{31}^{333667}\equiv 572163650030706066=r_{32}$ ，

$2^{m_3}\equiv r_{32}^{52579}\equiv \text{786092545290328404}$ ，

$\left(2^{m_3}-1,n\right)=1$ (13)

$m_4\equiv \frac{n-1}{p_4}=333667\times 52579\times 37\times 19\times 13\times 11\times 5\times 3^2\times 2$ ，

$2^{2\times 3^2\times 5\times 11\times 13\times 13\times 19\times 37}\equiv \text{454564979521137587}=r_{41}$ ，

$2^{2\times 3^2\times 5\times 11\times 13\times 13\times 19\times 37\times 333667}\equiv r_{41}^{333667}\equiv \text{291103097675451058}=r_{42}$ ，

$2^{m_4}\equiv r_{42}^{52579}\equiv \text{624671632919673247}$ ，

$\left(2^{m_4}-1,n\right)=1$ (14)

对 $p_5,p_6$ ，取a = 3，

$3^{2\times 3\times 5\times 7\times 11\times 13\times 19\times 37}\equiv 413091562820750497=r_{51}$

$3^{2\times 3\times 5\times 7\times 11\times 13\times 19\times 37\times 333667}\equiv r_{51}^{333667}\equiv 719013698222911823=r_{52}$ ,

$3^{m_5}\equiv r_{52}^{52579}\equiv \text{933000903779960656}$ ,

$\left(3^{m_5}-1,n\right)=1$ (15)

$m_6=\frac{n-1}{p_6}=3^2\times 5\times 7\times 11\times 13\times 19\times 37\times 52579\times 333667$ ，

$3^{3^2\times 5\times 7\times 11\times 13\times 19\times 37}\equiv \text{439165546220198935}=r_{61}$

$3^{3^2\times 5\times 7\times 11\times 13\times 19\times 37\times 333667}\equiv {\text{439165546220198935}}^{333667}\equiv \text{125757480451062679}=r_{62}$ ，

$3^{m_6}\equiv r_{62}^{52579}\equiv {\text{125757480451062679}}^{52579}\equiv -1$

$\left(3^{m_6}-1,n\right)=1$ (16)

由(9)~(16)和定理5即得R19是一个素数。

讨论：本文的例子及第3节的方法提供了素性判定的一种初等方法及其具体的集散过程，具体的应用成果就是解决了R19的素性判定。这可对类似问题给出一种参考方法，从本文的方法看出这种方法随着n的增大，难度将越来越大。因此对大整数的素性判定是否能继续应用这种方法需要继续探讨。