# Another version of the primality test using a theorem of Lucas

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.

___________________________________________________________________

The theorems

In the previous post, we discuss and prove the following theorem.

Theorem 1 (Lucas)
Let $n$ be a positive integer. Then $n$ is prime if and only if there exists some integer $a$ such that

• $\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for all prime factor $r$ of $n-1$.

The value of $a$ in the statement of the theorem is a primitive root modulo $n$. 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.

Theorem 2
Let $n$ be a positive integer. Then $n$ is prime if and only if for each prime factor $r$ of $n-1$, there exists some integer $a$ such that

• $\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$.

The existential quantifier and the universal quantifier are switched in the statements of the two theorems. In Theorem 1, one value of $a$ works for all prime factors of $n-1$. In Theorem 2, each prime factor of $n-1$ has one value of $a$ that satisfies some conditions. More importantly, the value of $a$ 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.

Lemma 3
Suppose $g=b_1 \cdot b_2 \cdots b_k$ such that $\text{GCD}(b_i,b_j)=1$ for $i \ne j$. Then if $b_i$ divides $h$ for each $i$, then $g$ divides $h$.

Proof of Lemma 3
Suppose that $b_i$ divides $h$ for each $i$. Assume that $g \le h$. By the division algorithm, we can write $h=g \cdot q+r$ where $q$ and $r$ are integers and $0 \le r. We claim that $r=0$. Once the claim is proved, the lemma will follow.

Suppose that $0. it follows from $h=g \cdot q+r$ that $b_i$ divides $r$ for each $i$. It follows that for some integers $u_i$, the number $r$ can be expressed as follows:

$r=b_1 \cdot u_1=b_2 \cdot u_2=\cdots=b_k \cdot u_k$

Because the numbers $b_i$ are mutually relatively prime, each $b_i$ with $i \ne j$ is a factor of $u_j$. Thus $r=b_1 \cdot b_2 \cdots b_k \cdot w=g \cdot w$ for some integer $w$. We have $0, leading to $0. This is a contradiction since $w$ is an integer.

In the above argument, we make the assumption that $g \le h$. Suppose $h < g$. Using the division algorithm, we have $g=h \cdot q+r$ for some integers $q$ and $r$ with $0 \le r. As before, all the $b_i$ divides $r$. The same argument shows that $r=g \cdot w$ for some positive integer $w$. Now $0 \le g \cdot w , contradicting $h < g$. So the assumption of $g \le h$ is valid. $\blacksquare$

Proof of Theorem 2
The direction $\Longrightarrow$ is clear (see the proof of the same direction in Theorem 1). Now suppose that the number $n-1$ has the following prime factorization

$n-1=p_1^{w_1} \cdot p_2^{w_2} \cdot p_3^{w_3} \cdots p_t^{w_t}$

where each $p_j$ is prime and each $w_j \ge 1$. Suppose that for each prime factor $p_j$, there exists an $a_j$ such that

• $\displaystyle a_j^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a_j^{\frac{n-1}{p_j}} \not \equiv 1 \ (\text{mod} \ n)$.
• .

For each $j$, let $k_j$ be the least positive integer such that $\displaystyle a_j^{k_j} \equiv 1 \ (\text{mod} \ n)$. In other words, $k_j$ is the order of $a_j$ modulo $n$. It follows that $k_j$ divides $n-1$. On the other hand, $k_j$ does not divide $\frac{n-1}{p_j}$. If it did, we would have $\displaystyle a_j^{\frac{n-1}{p_j}} \equiv 1 \ (\text{mod} \ n)$.

For each $j$, let $n-1=k_j \cdot m_j$ for some integer $m_j$. Note that $p_j$ cannot divide $m_j$. Otherwise $k_j$ would divide $\frac{n-1}{p_j}$. Since none of the prime factors of $m_j$ can be $p_j$, it follows that $p_j^{w_j}$ must divide $k_j$.

On the other hand, $k_j$ divides $\phi(n)$. So $p_j^{w_j}$ divides $\phi(n)$. By Lemma 3, $n-1$ divides $\phi(n)$, giving $n-1 \le \phi(n)$. It is always that case that $\phi(n) \le n-1$. We have shown that $\phi(n)=n-1$. By Lemma 2 in this previous post, $n$ is prime. $\blacksquare$

___________________________________________________________________

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 $n-1$ must be known if $n$ 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 [1].

___________________________________________________________________

Examples

In the previous post, we show how to apply Theorem 1. We now work some examples illustrating the use of Theorem 2.

Example 1
Consider the number $n=$ 38709183810571. The following is the prime factorization of $n-1$.

$n-1=2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 43 \cdot 53 \cdot 6221671$

The last factor can easily be verified as prime by checking all prime numbers below $\sqrt{6221671}=2495$. Use $a=2$ as a starting point.

$\displaystyle 2^{n-1} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{2}} \equiv -1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{3}} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{5}} \equiv 8709312260007 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{7}} \equiv 10281040998090 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{13}} \equiv 19655805387808 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{43}} \equiv 2160876971677 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{53}} \equiv 9896596763553 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{6221671}} \equiv 787783558192 \not \equiv 1 \ (\text{mod} \ n)$

Note that the number $a=2$ works for all prime factors of $n-1$ except for 3. Now use $a=3$.

$\displaystyle 3^{\frac{n-1}{3}} \equiv 38709177588900 \not \equiv 1 \ (\text{mod} \ n)$

In conclusion, for all prime factors of $n-1$ except 3, the value $a=2$ satisfies the conditions in Theorem 2. For the prime factor 3 of $n-1$, use $a=3$. By Theorem 2, the number $n=$ 38709183810571 is proved to be prime.

Example 2
Use Theorem 2 to perform primality testing on the following number

$n=$ 3825123056546413183.

This is Example 2 in this previous post. The factorization of $n-1$ is

$2 \cdot 3 \cdot 11 \cdot 17 \cdot 211 \cdot 16157348744821$.

The last factor $m=$ 16157348744821 is a prime number (see the previous post). We start with $a=2$.

$\displaystyle 2^{n-1} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{2}} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{3}} \equiv 289450338018998060 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{11}} \equiv 1901835040937234167 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{17}} \equiv 914194133070825051 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{211}} \equiv 762829414677449095 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{\frac{n-1}{16157348744821}} \equiv 3383930647831278184 \not \equiv 1 \ (\text{mod} \ n)$

With $a=2$, the above calculation works for all prime factors of $n-1$, except 2. Now try $a=3$.

$\displaystyle 3^{\frac{n-1}{2}} \equiv -1 \ (\text{mod} \ n)$

By Theorem 2, the number $n=$ 3825123056546413183 is proved prime.

___________________________________________________________________

Exercises

Prove the compositeness or primality of each of the following numbers. In proving primality, use Lucas’ theorem according to Theorem 2.

204482919124364689
3825123056546413093
3825123056546413133
3825123056546413211
3825123056546413213

___________________________________________________________________

Reference

1. Brillhart J., Lehmer D. H., Selfridge J.L., New primality criteria and factorizations of $2^m \pm 1$, Math. Comp., 29, no. 130, 620-647, 1975.
2. Lehmer D. H., Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc., 33, 327-340 1927.

___________________________________________________________________
$\copyright \ \ 2014 \ \text{Dan Ma}$

# A primality proving algorithm using a theorem of Lucas

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 [1]. The primality test using the theorem is a limited one since the test requires that $n-1$ must be completely factored if $n$ is the number being tested. Though a limited test, this is a useful test in situations where $n-1$ has small prime factors or the factorization of $n-1$ is known in advance (e.g. factorial primes and primorial primes).

___________________________________________________________________

The theorem

Theorem 1 (Lucas)
Let $n$ be a positive integer. Then $n$ is prime if and only if there exists some integer $a$ such that

• $\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n)$,
• $\displaystyle a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for all prime factor $r$ of $n-1$.

The function $\phi$ is Euler’s phi function. If $n$ is a prime number, $\phi(n)=n-1$. The following lemma shows that the converse is true. The lemma is used in proving Theorem 1.

Lemma 2
If $\phi(n)=n-1$, then $n$ is prime.

Proof of Lemma 2
By definition $\phi(n)$ is the number of integers $t$ where $1 such that $\text{GCD}(t,n)=1$, i.e., $t$ and $n$ are relatively prime. First of all, $\phi(n) \le n-1$. Suppose $n$ is composite. Then there is some $t$ where $1 such that $t$ is a divisor of $n$. Clearly $\text{GCD}(t,n)>1$. It follows that $\phi(n). Therefore if If $\phi(n)=n-1$, then $n$ must be prime. $\blacksquare$

Proof of Theorem 1
It is well known that for any prime number $n$, there exists a primitive root modulo $n$ (see here). A primitive root modulo $n$ is a number $a$ such that $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$ but $a^{j} \not \equiv 1 \ (\text{mod} \ n)$ for all $1. In other words, $\phi(n)$ is the least exponent such that $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$. Let $n$ be a prime number. Then $\phi(n)=n-1$. By the point that is just stated, there exists an $a$ that is a primitive root modulo $n$. This primitive root $a$ would satisfy $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for any prime divisor $r$ of $n-1$.

Now suppose that there exists an $a$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for any prime divisor $r$ of $n-1$. Let $k$ be the least positive integer such that $a^{k} \equiv 1 \ (\text{mod} \ n)$. The number $k$ is said to be the order of $a$ modulo $n$.

We claim that $k=n-1$. From the assumption that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$, we have $k \lvert (n-1)$. Thus $k \le n-1$. Suppose that $k. Then $\frac{n-1}{k}$ is an integer that is greater than 1. Let $r$ be a prime factor of $\frac{n-1}{k}$. Set $\frac{n-1}{k}=r \cdot t$ for some integer $t$. Then $a^{\frac{n-1}{r}} \equiv a^{kt} \equiv (a^k)^t \equiv 1 \ (\text{mod} \ n)$, contradicting the assumption stated above. Thus $k=n-1$.

On the other hand, $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$ always holds (see here). Since $k$ is least, we have $k=n-1 \le \phi(n)$. It is always the case that $\phi(n) \le n-1$. Thus we have established that $\phi(n)=n-1$. By Lemma 2, $n$ is prime. $\blacksquare$

Remark
The above proof shows that $n$ is prime from the existence of $a$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^{\frac{n-1}{r}} \not \equiv 1 \ (\text{mod} \ n)$ for any prime divisor $r$ of $n-1$. The proof also shows that $\phi(n)$ is the least number such that $a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$. That is, the number $a$ is a primitive root modulo $n$. Whenever $n$ is proved prime by finding such an $a$, 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 $n$ is prime is that $n-1$ 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 $n$.

• All prime factors of $n-1$ are small.
• For each prime factor of $n-1$, 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 $n-1$, 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 $a=2$ and work the way up to a value of $a$ that works. But this may be a lengthy process. A faster option is to use randomly chosen values of $a$.

To use Theorem 1 to prove that $n$ is prime, it is a matter of finding a value of $a$ with $1 that satisfies the two conditions in the theorem. If such an $a$ is not found after a reason number of iterations, then $n$ is probably composite. In this case, it makes sense to subject $n$ 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 $a$ cannot be found in a reasonable number of iterations. Additional remark is given at the end of Example 1.

___________________________________________________________________

Examples

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.

Example 1

Consider the number $n=$ 3825123056546413057. As a preliminary check, we find that it is a strong probable prime to base 2. The following is the prime factorization of $n-1$.

$n-1=2^9 \cdot 3 \cdot 53 \cdot 647 \cdot 2689 \cdot 2927 \cdot 9227$

Choose a random number $a$ in the interval $1. Then calculate the following 8 congruences.

$\displaystyle a^{n-1} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{3}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{53}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{647}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2689}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2927}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{9227}} \ (\text{mod} \ n)$

If the first one is a 1 and the other 7 congruences are not 1, then we have a proof that $n=$ 3825123056546413057 is prime. Using the random number $a=$ 986534828637101811, we have the following results.

$\displaystyle a^{n-1} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2}} \equiv -1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{3}} \equiv 452981711193023997 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{53}} \equiv 3170926069526963063 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{647}} \equiv 1877702458518081231 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2689}} \equiv 2711620409082022280 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2927}} \equiv 2162838710620876676 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{9227}} \equiv 178583766553568086 \not \equiv 1 \ (\text{mod} \ n)$

The first congruence is a 1 and the remaining 7 congruences are not 1. Thus by Lucas’ theorem, the number $n=$ 3825123056546413057 is prime.

Remarks
Upon choosing a value of $a$ (random or otherwise), if the first congruence $\displaystyle a^{n-1} \ (\text{mod} \ n)$ is not a 1, then $n$ is composite by Fermat’s little theorem, and we are done. Suppose the first congruence is a 1. If the second congruence $\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$ is not $\pm 1$, then $n$ is composite. This is because if $n$ is prime, then the square root of 1 modulo $n$ must be $\pm 1$. Since Lucas’ theorem requires that $\displaystyle a^{\frac{n-1}{2}} \not \equiv 1 \ (\text{mod} \ n)$, the only legitimate value of the second congruence is -1. This is something we should look for. If the second congruence $\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$ is not a -1, then choose another value of $a$ 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 $a$.

Example 2

Using Lucas’ theorem, perform primality testing on the following number

$n=$ 3825123056546413183.

As a preliminary check, it is a strong probable prime to base 2. Next, factor $n-1$ as far as possible.

$n-1=2 \cdot 3 \cdot 11 \cdot 17 \cdot 211 \cdot 16157348744821$

The last factor $m=$ 16157348744821 of $n-1$ is an 14-digit number. It is a probable prime to base 2, meaning that $2^{m-1} \equiv 1 \ (\text{mod} \ m)$. So we have a good reason to believe that $m$ 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 $m=$ 16157348744821. Factor $m-1$ as far as possible.

$m-1=2^2 \cdot 3 \cdot 5 \cdot 31 \cdot 149 \cdot 58300313$

The last factor $T=$ 58300313 is a prime number. The square root of $T$ is 7635.46. None of the prime numbers below 7635 is a factor of $T$. So the above factorization is the prime factorization of $m-1$. We calculation the following:

$\displaystyle a^{m-1} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{2}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{3}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{5}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{31}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{149}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{58300313}} \ (\text{mod} \ m)$

We use $a=2$ as a starting point. We have the following results.

$\displaystyle 2^{m-1} \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{2}} \equiv -1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{3}} \equiv 10783747104377 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{5}} \equiv 6880981597483 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{31}} \equiv 8907135419651 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{149}} \equiv 4770370795536 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle 2^{\frac{m-1}{58300313}} \equiv 13899477097778 \not \equiv 1 \ (\text{mod} \ m)$

We are lucky that the first $a$ we try works. Now we have proof that the number $m$ is a prime. As a result, the prime factorization of $n-1$ for the original number $n=$ 3825123056546413183 is complete. To prove the primality of $n$, we calculate the following.

$\displaystyle a^{n-1} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{3}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{11}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{17}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{211}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{m}} \ (\text{mod} \ n)$

We try $a=2$ and then $a=3$, both not working, with $\displaystyle 2^{\frac{n-1}{2}} \equiv 1 \ (\text{mod} \ n)$ and $\displaystyle 3^{\frac{n-1}{3}} \equiv 1 \ (\text{mod} \ n)$. Next we try $a=5$, with the following results.

$\displaystyle 5^{n-1} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 5^{\frac{n-1}{2}} \equiv -1 \ (\text{mod} \ n)$

$\displaystyle 5^{\frac{n-1}{3}} \equiv 289450338018998060 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 5^{\frac{n-1}{11}} \equiv 2294646644277354980 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 5^{\frac{n-1}{17}} \equiv 660679882646053403 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 5^{\frac{n-1}{211}} \equiv 3566794465656534455 \not \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 5^{\frac{n-1}{m}} \equiv 985813616806446564 \not \equiv 1 \ (\text{mod} \ n)$

The above calculation for base $a=5$ shows that the number $n=$ 3825123056546413183 is prime.

Example 3

Consider the number $n=$ 219944603708904241. The following is the factorization of $n-1$.

$n-1=2^4 \cdot 3^3 \cdot 5 \cdot 23 \cdot 3691 \cdot 1199465273$

The last factor $m=$ 1199465273 is a probable prime to base 2, meaning that $2^{m-1} \equiv 1 \ (\text{mod} \ m)$. We have good evidence that $m$ is prime. To confirm, we apply Lucas’ theorem on this number. The following is the prime factorization of $m-1$, where each factor is small and is easy to be determined as prime.

$m-1=2^3 \cdot 23 \cdot 677 \cdot 9629$

To prove the primality of $m$, we calculate the following.

$\displaystyle a^{m-1} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{2}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{23}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{677}} \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{9629}} \ (\text{mod} \ m)$

We try two random choices for $a$ and do not have the desired results. The next random choice is $a=$ 526979896. The following calculation proves that $m$ is prime.

$\displaystyle a^{m-1} \equiv 1 \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{2}} \equiv -1 \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{23}} \equiv 820189482 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{677}} \equiv 695226481 \not \equiv 1 \ (\text{mod} \ m)$

$\displaystyle a^{\frac{m-1}{9629}} \equiv 554335065 \not \equiv 1 \ (\text{mod} \ m)$

With the prime factorization of $n-1$ being complete, we turn our attention to the following calculations.

$\displaystyle a^{n-1} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{2}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{3}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{5}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{23}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{3691}} \ (\text{mod} \ n)$

$\displaystyle a^{\frac{n-1}{m}} \ (\text{mod} \ n)$

We generate the following 8 random choices of $a$

013397886753078290
193080712858269996
012695419760523254
096180046746919966
134541150430885987
212892893489065625
209448807773524821
141141720485036352

and find that $\displaystyle a^{\frac{n-1}{2}} \equiv 1 \ (\text{mod} \ n)$ for all these 8 values of $a$. This is highly unusual if the number $n$ is prime. We then realize that we forget to check for strong probable primality of $n$. With $n-1=2^4 \cdot Q$ where $Q=$ 13746537731806515, we calculate the following:

$\displaystyle 2^{Q} \equiv 123276781822261547 \ (\text{mod} \ n)$

$\displaystyle 2^{2Q} \equiv 2648415336489 \not \equiv -1 \ (\text{mod} \ n)$

$\displaystyle 2^{4Q} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{8Q} \equiv 1 \ (\text{mod} \ n)$

$\displaystyle 2^{16Q} \equiv 1 \ (\text{mod} \ n)$

The above calculation shows that the number $n=$ 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 $6m+1$, $12m+1$ and $18m+1$ where $m=$ 55365.

___________________________________________________________________

Exercises

Prove the compositeness or primality of each of the following numbers. In proving primality, use Lucas’ theorem as shown in the above examples.

204482919124364689
3825123056546413093
3825123056546413133
3825123056546413211
3825123056546413213

___________________________________________________________________

Reference

1. Lehmer D. H., Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc., 33, 327-340 1927.

___________________________________________________________________
$\copyright \ \ 2014 \ \text{Dan Ma}$