In 1876, Edouard Lucas showed that if an integer b exists such that b~(n-1) ≡ 1 (mod n) and b~((n-1)/p) ≠ 1 (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 to determine the primality of n. In this paper we optimize Pocklington's primality test for integers of the form ap~k + 1 where p is prime, a < p, k ≥ 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.
展开▼
