In this post we discuss a theorem that can be used as a primality test that actually proves primality rather than just giving strong evidence for primality. The theorem is originally due to Lucas in 1891. The version we discuss here is proved by Lehmer . The primality test using the theorem is a limited one since the test requires that must be completely factored if is the number being tested. Though a limited test, this is a useful test in situations where has small prime factors or the factorization of is known in advance (e.g. factorial primes and primorial primes).
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 function is Euler’s phi function. If is a prime number, . The following lemma shows that the converse is true. The lemma is used in proving Theorem 1.
If , then is prime.
Proof of Lemma 2
By definition is the number of integers where such that , i.e., and are relatively prime. First of all, . Suppose is composite. Then there is some where such that is a divisor of . Clearly . It follows that . Therefore if If , then must be prime.
Proof of Theorem 1
It is well known that for any prime number , there exists a primitive root modulo (see here). A primitive root modulo is a number such that but for all . In other words, is the least exponent such that . Let be a prime number. Then . By the point that is just stated, there exists an that is a primitive root modulo . This primitive root would satisfy and for any prime divisor of .
Now suppose that there exists an such that and for any prime divisor of . Let be the least positive integer such that . The number is said to be the order of modulo .
We claim that . From the assumption that , we have . Thus . Suppose that . Then is an integer that is greater than 1. Let be a prime factor of . Set for some integer . Then , contradicting the assumption stated above. Thus .
On the other hand, always holds (see here). Since is least, we have . It is always the case that . Thus we have established that . By Lemma 2, is prime.
The above proof shows that is prime from the existence of such that and for any prime divisor of . The proof also shows that is the least number such that . That is, the number is a primitive root modulo . Whenever is proved prime by finding such an , keep in mind that the task of primality proving using this theorem is essentially the task of finding a primitive root.
The primality test from the theorem
Theorem 1 can be fashioned into a primality test, or rather a primality proving algorithm. The key requirement to proving is prime is that must be completely factored. Because of this obstacle, the primality test is a limited one. The following are some of the cases for which Lucas’s theorem is suitable as a proof for the primality of .
- All prime factors of are small.
- For each prime factor of , either it is small or its primality can be established using Lucas’s theorem.
The second case points to the fact that sometimes Lucas’ theorem can be used recursively to establish the primality of a number. Specifically, in factoring , we may come across a factor that is a probable prime. We then can use Lucas’ theorem to prove its primality. In doing so, we may come across another number that is a probable prime. We can then use Lucas’ theorem again and prove its primality and so on.
As mentioned at the end of the previous section, the task of primality proving here is essentially the task of finding a primitive root. There is no easy formula for finding primitive roots. One can always start with and work the way up to a value of that works. But this may be a lengthy process. A faster option is to use randomly chosen values of .
To use Theorem 1 to prove that is prime, it is a matter of finding a value of with that satisfies the two conditions in the theorem. If such an is not found after a reason number of iterations, then is probably composite. In this case, it makes sense to subject to a probabilistic primality test such as the Miller-Rabin test to check for compositeness.
In light of the comment made in the preceding paragraph, before using Theorem 1, we should apply a probabilistic primality test on the number being tested. If the number is shown to be composite by the Miller-Rabin test, then there is no need to use Theorem 1. If the number is a strong probable prime to base 2 for example, then we can proceed to use Theorem 1. Even when Theorem 1 is applicable, there may still be a need to switch back to a probabilistic primality test if a suitable value of cannot be found in a reasonable number of iterations. Additional remark is given at the end of Example 1.
The examples demonstrated here are small enough to be realistically proved as prime by factoring (by computer). However, they are large enough to be excellent demonstrations of the method using the theorem of Lucas.
Consider the number 3825123056546413057. As a preliminary check, we find that it is a strong probable prime to base 2. The following is the prime factorization of .
Choose a random number in the interval . Then calculate the following 8 congruences.
If the first one is a 1 and the other 7 congruences are not 1, then we have a proof that 3825123056546413057 is prime. Using the random number 986534828637101811, we have the following results.
The first congruence is a 1 and the remaining 7 congruences are not 1. Thus by Lucas’ theorem, the number 3825123056546413057 is prime.
Upon choosing a value of (random or otherwise), if the first congruence is not a 1, then is composite by Fermat’s little theorem, and we are done. Suppose the first congruence is a 1. If the second congruence is not , then is composite. This is because if is prime, then the square root of 1 modulo must be . Since Lucas’ theorem requires that , the only legitimate value of the second congruence is -1. This is something we should look for. If the second congruence is not a -1, then choose another value of and start over. In fact, the second congruence should be the one to do first. If it is not a -1, then use another value of .
Using Lucas’ theorem, perform primality testing on the following number
As a preliminary check, it is a strong probable prime to base 2. Next, factor as far as possible.
The last factor 16157348744821 of is an 14-digit number. It is a probable prime to base 2, meaning that . So we have a good reason to believe that might be a prime. To test whether it is prime, we can use the same method to test. So now we focus our attention on the number 16157348744821. Factor as far as possible.
The last factor 58300313 is a prime number. The square root of is 7635.46. None of the prime numbers below 7635 is a factor of . So the above factorization is the prime factorization of . We calculation the following:
We use as a starting point. We have the following results.
We are lucky that the first we try works. Now we have proof that the number is a prime. As a result, the prime factorization of for the original number 3825123056546413183 is complete. To prove the primality of , we calculate the following.
We try and then , both not working, with and . Next we try , with the following results.
The above calculation for base shows that the number 3825123056546413183 is prime.
Consider the number 219944603708904241. The following is the factorization of .
The last factor 1199465273 is a probable prime to base 2, meaning that . We have good evidence that is prime. To confirm, we apply Lucas’ theorem on this number. The following is the prime factorization of , where each factor is small and is easy to be determined as prime.
To prove the primality of , we calculate the following.
We try two random choices for and do not have the desired results. The next random choice is 526979896. The following calculation proves that is prime.
With the prime factorization of being complete, we turn our attention to the following calculations.
We generate the following 8 random choices of
and find that for all these 8 values of . This is highly unusual if the number is prime. We then realize that we forget to check for strong probable primality of . With where 13746537731806515, we calculate the following:
The above calculation shows that the number 219944603708904241 is composite; it is a strong pseudoprime to base 2. This goes to show that before applying Lucas’ theorem, it makes sense to do some strong probable prime test to rule out numbers that happen to be composite.
The number in Example 3 is a Carmichael number. It is the product of the prime factors , and where 55365.
Prove the compositeness or primality of each of the following numbers. In proving primality, use Lucas’ theorem as shown in the above examples.
- Lehmer D. H., Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc., 33, 327-340 1927.