# 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}$