A Sequence of Natural Numbers Containing No Pseudoprimes

A Sequence of Natural Numbers Containing No Fermat Pseudoprimes Larry Cornell December 25, 2015

1

Fermat’s Little Theorem and Pseudoprimes

Theorem 1 (Euler’s Theorem) Given a natural number n if gcd(a, n) = 1 then aφ(n) ≡ 1 modn. Proof Since on the reduced residue system of n, with 0 ≤ i ≤  φ (n),if j is another Q Q Q Q φ(n) index such that 0 ≤ j ≤ φ (n) then aj = aai = a ai , and aj = Q Q ai for some bijection j = µ (i), and the inverse of aj exists, it must be that aφ(n) ≡ 1 modn. Theorem 2 (Fermat’s Little Theorem) If p is prime and p does not divide a then ap−1 ≡ 1 modp. Proof Since φ (p) = p − 1 anything in the cosets of pZ is relatively prime to p and by Euler’s Theorem ap−1 ≡ 1 modp. Definition 3 (Fermat Pseudoprime) A composite natural number n such that gcd(n, a) = 1 and an−1 ≡ 1 modn for some a < n, passes the Fermat Primality Test though it is composite. Such numbers n have come to be called fermat pseudoprimes or simply pseudoprimes. It is known that for a = 2 the smallest fermat pseudoprime is 341. But the existence of even one pseudoprime in a sequence means that the fermat primality test can be only at best probabilistic. A sufficient condition however for a natural number to be a fermat pseudoprime is given in the following theorem. Theorem 4 (Pseudoprime Property) An odd composite natural number n can be a fermat pseudoprime if and only if the reduced residue system modulo n has a subgroup of order k dividing n − 1, which is equivalent to saying k divides the gcd(n − 1, φ (n)).

1

Proof By Euler’s Theorem if gcd(a, n) = 1 then aφ(n) ≡ 1 modn. If n is prime it is always true that φ (n) = n − 1 and so all the (reduced) residues a of n will have the property that an−1 ≡ 1 modn. If however n is composite then φ (n) < n − 1 and there can be no reduced residues a of n such that an−1 ≡ 1 modn unless the order of a in the reduced residue system divides n − 1. The only orders possible for a then are those dividing the gcd(n − 1, φ (n)). q.e.d. With this result in hand it becomes possible to consider constructing a sequence of natural numbers in which there are no pseudoprimes. The value of finding such a sequence should be obvious. The fermat primality test becomes a one stop destination for testing the primality of numbers in the sequence and no more than one value of a is needed.

2

Sophie Germaine’s Last Laugh

Toward the end of her correspondence with Gauss it was common for Sophie Germaine’s letters to remain unremarked upon by the bellweather genius of the nineteenth century. It was Sophie Germaine who posited a connection between primes of the form 2p+1 and Fermat’s Last Theorem. This little piece of history is interesting and we mention it not to slight Gauss or elevate Germaine, but simply because of its novelty and the fact that we are about to use an obvious extension of Sophie Germaine primes to create a sequence of natural numbers containing no psuedoprimes. Theorem 5 (The Sequence 6p+1) For prime p > 7, the sequence 6p+1 contains no pseudoprimes to base 2. Proof The proof works by showing that no composite number in the sequence 6p + 1 for p > 7 has the pseudoprime property (Theorem 4). Suppose n = 6p + 1, p > 7. Then if n is prime, fermat’s little theorem becomes 26p ≡ 1 mod6p + 1 where the totient of 6p + 1 is 6p, and the greatest common divisor of n − 1 and φ (n) is obviously 6p. This is just as expected. If n is composite, fermat’s little theorem again gives the condition 26p ≡ 1 mod6p + 1 only now we must seek to calculate both the order of 2 in the reduced residue system and gcd(6p, φ (6p + 1)). Starting with the latter we note that gcd (6p, φ (6p + 1)) has transparent properties. Namely gcd (6p, φ (6p + 1)) ∈ {2, 3, 6, p, 2p, 3p, 6p}. We are concerned with eliminating all multiples of p as candidates and can do so by looking at the general formula for the totient. Recall that for all pk |n φ (n) = n

Y pk − 1 pk

=

Y pik −1 Y k

pk

(pk − 1)

So then one way that p may divide the totient of 6p + 1 is if pi also divides 6p + 1 for some i > 1. But whenever p > 5, 6p + 1 < p2 , making it impossible that p2 should divide 6p + 1. The other way that p might divide φ (6p + 1) is

2

that p divides p ∗ −1 for some p∗ dividing 6p + 1. But in this case we have a prime p∗ larger than 2p dividing 6p + 1. The multiplicity of p∗ must be precisely one or else we can also argue that p∗2 > 6p ∗ +1 when p∗ > 5. Thus we arrive at the condition 2pt < p∗ t = 6p + 1 and p > (2pt − 1) /6. This inequality holds whenever t < 4 because p > (2pt − 1) /6 → t < 3 + 1/2p < 4. This leaves us with the following possibilities. Either p∗ = 6p + 1 which is no threat to us, or 2p∗ = 6p + 1 which is obviously false, or 3p∗ = 6p + 1, but again this cannot happen because 6p + 1 is coprime to 3. Thus gcd (6p, φ (6p + 1)) ∈ {2, 3, 6}. Now for estimating the order of two in the reduced residue system modulo 6p + 1. Since the gcd (6p, φ (6p + 1)) ≤ 6 the order of two in the reduced residue system of 6p + 1 cannot divide 6p unless it is less than or equal to 6. But notice that σ (2) > blog2 (6p + 1)c. It is clear to see that whenever p > 7, log2 (6p + 1) > 6 because blog2 67c = 6. Thus when p > 7 the sequence 6p + 1 contains no pseudoprimes. q.e.d. Corollary 6 ( Theorem 5 - Fermat Primality Test on the Sequence 6p + 1) It is only required to test whether 26p ≡ 1 mod6p + 1 in order to determine whether 6p + 1 is prime or composite when p > 7. Proof By Theorem 5 if σ (2) > 6 then it cannot divide the gcd (6p, φ (6p + 1)) thus the number cannot be pseudoprime. So 2 is a witness when 6p + 1 is composite. If 26p ≡ 1 mod6p + 1, since there are no liars in the sequence, 6p + 1 is prime.

3

Conclusions and Further Research

Theorem 5 is not an obvious result, and we could forgive Gauss if he did not have the proper respect for the power of a woman’s intuition. And it clearly opens the door to the possibility of finding other similar sequences having the same property. From here we would seem to be able to push the level of the largest known prime to the very limit of our ability to calculate 26p mod (6p + 1). It remains though to try to better understand the distribution of primes in the sequence 6p + 1. In fact it might be possible for the world’s fastest computers to run RSA type encryptions so far beyond the reach of average computers that the owners of these supercomputers could enjoy complete and total security among themselves. But this was already the case was it not? Finally, we would like to say that in yet another example of the value of primorials and the knowledge of smaller primes, we obtain other primes. A follow up paper will examine the prime density of 6p + 1 and look for ways to extend these results over reduced residues systems of the primorials.

3