论文标题
表单的数字$ ap^{k}+1 $
Primality of numbers of the form $ap^{k}+1$
论文作者
论文摘要
1876年，爱德华·卢卡斯（Edouard Lucas）表明，如果存在一个整数$ b $，以至于$ b^{n-1} \ equiv 1（\ mathrm {mathrm {mod} \ n）$和$ b^{（n-1）/p} \ not \ equiv equiv equiv 1（\ equiv 1（\ equiv 1）卢卡斯与费玛特的小定理的匡威。亨利·波克林顿（Henry Pocklington）在1914年表明，没有必要了解$ n-1 $的所有主要因素，以确定$ n $是否是主要因素，这使这一结果大大改善了。在本文中，我们优化了Pocklington的原始测试，用于$ ap^{k}+1 $的整数，其中$ p $是Prime，$ a <p $，$ k \ ge 1 $。给出了卢卡斯的Fermat小定理的匡威。我们还证明了一项新的通用原始测试，该测试要求仅找到一个$ n-1 $的单个奇数prime除法，以实现该测试。与众所周知的结果相反：任何基本$ b $都有无限的Fermat Pseudaprime；在本文中，我们证明了某些形式的整数在Fermat Pseudaprime的局限性。
In 1876, Edouard Lucas showed that if an integer $b$ exists such that $b^{n-1} \equiv 1 (\mathrm{mod} \ n)$ and $b^{(n-1)/p} \not\equiv 1( \mathrm{mod} \ n)$ for all prime divisors $p$ of $n-1$ , then $n$ is prime, a result known as Lucas's converse of Fermat's little theorem. This result was considerably improved by Henry Pocklington in 1914 when he showed that it's not necessary to know all the prime factors of $n-1$ in order to determine if $n$ is prime. In this paper we optimize Pocklington's primality test for integers of the form $ap^{k}+1$ where $p$ is prime, $a<p$, $k\ge 1$. An extension of Lucas's converse of Fermat's little theorem is given. We also prove a new general-purpose primality test that requires that only a single odd prime divisor of $n-1$ be found for the test to be implemented. Contrary to the well-known result: There are infinitely many Fermat pseudoprimes to any base $b$; In this paper we prove the finitude of Fermat pseudoprimes in some forms of integers.
