In the previous post, we prove a theorem that is attributed to Lucas and give examples on how to use it to prove primality. The task of using this theorem to prove primality is essentially the task of finding a primitive root. So this primality test could be a little tricky to use since there is no simple formula for finding primitive root. In this post, we discuss a variation (but an equivalence) of Lucas’ theorem that does not require using primitive root but still proves primality.
In the previous post, we discuss and prove the following theorem.
Theorem 1 (Lucas)
Let be a positive integer. Then is prime if and only if there exists some integer such that
- for all prime factor of .
The value of in the statement of the theorem is a primitive root modulo . Though the theorem is fairly easy to prove, the theorem is important and has far reaching consequences. The basic idea in this theorem is the foundation of many other deterministic primality tests. So it is a good idea to examine this theorem in great details. One way to do that is to examine variations of it. In this post, we examine the following theorem.
Let be a positive integer. Then is prime if and only if for each prime factor of , there exists some integer such that
The existential quantifier and the universal quantifier are switched in the statements of the two theorems. In Theorem 1, one value of works for all prime factors of . In Theorem 2, each prime factor of has one value of that satisfies some conditions. More importantly, the value of in Theorem 2 cannot be expected to be a primitive root. Computationally speaking Theorem 2 should be a little easier to use. The proof of Theorem of 2 uses the following basic lemma.
Suppose such that for . Then if divides for each , then divides .
Proof of Lemma 3
Suppose that divides for each . Assume that . By the division algorithm, we can write where and are integers and . We claim that . Once the claim is proved, the lemma will follow.
Suppose that . it follows from that divides for each . It follows that for some integers , the number can be expressed as follows:
Because the numbers are mutually relatively prime, each with is a factor of . Thus for some integer . We have , leading to . This is a contradiction since is an integer.
In the above argument, we make the assumption that . Suppose . Using the division algorithm, we have for some integers and with . As before, all the divides . The same argument shows that for some positive integer . Now , contradicting . So the assumption of is valid.
Proof of Theorem 2
The direction is clear (see the proof of the same direction in Theorem 1). Now suppose that the number has the following prime factorization
where each is prime and each . Suppose that for each prime factor , there exists an such that
For each , let be the least positive integer such that . In other words, is the order of modulo . It follows that divides . On the other hand, does not divide . If it did, we would have .
For each , let for some integer . Note that cannot divide . Otherwise would divide . Since none of the prime factors of can be , it follows that must divide .
On the other hand, divides . So divides . By Lemma 3, divides , giving . It is always that case that . We have shown that . By Lemma 2 in this previous post, is prime.
The primality test from the theorems
The above theorems are equivalent. So both theorems give essentially the same primality test. It is just that the implementation based on Theorem 2 is somewhat easier and in some cases much faster. No matter which theorem is used, it is always a good idea to apply the strong probable prime test (the Miller-Rabin test) first, just in case the compositeness can be easily detected.
Of course, the limitation for the primality discussed here is that the factorization of must be known if is the number being tested. If Lucas’ theorem is not applicable and if probabilistic primality testing is not 100% satisfactory, other primality proving theorems may be explored. See .
In the previous post, we show how to apply Theorem 1. We now work some examples illustrating the use of Theorem 2.
Consider the number 38709183810571. The following is the prime factorization of .
The last factor can easily be verified as prime by checking all prime numbers below . Use as a starting point.
Note that the number works for all prime factors of except for 3. Now use .
In conclusion, for all prime factors of except 3, the value satisfies the conditions in Theorem 2. For the prime factor 3 of , use . By Theorem 2, the number 38709183810571 is proved to be prime.
Use Theorem 2 to perform primality testing on the following number
This is Example 2 in this previous post. The factorization of is
The last factor 16157348744821 is a prime number (see the previous post). We start with .
With , the above calculation works for all prime factors of , except 2. Now try .
By Theorem 2, the number 3825123056546413183 is proved prime.
Prove the compositeness or primality of each of the following numbers. In proving primality, use Lucas’ theorem according to Theorem 2.
- Brillhart J., Lehmer D. H., Selfridge J.L., New primality criteria and factorizations of , Math. Comp., 29, no. 130, 620-647, 1975.
- Lehmer D. H., Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc., 33, 327-340 1927.