TAOCP 4.5.4 Exercise 15

Let $P$ and $Q$ be integers with $\gcd(P, Q) = 1$, and define the Lucas sequence $(U_n)$ by $U_0 = 0, \quad U_1 = 1, \quad U_{n+1} = P U_n - Q U_{n-1} \text{ for } n \ge 1.$ Let $N$ be a positive inte...

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.5.4: Factoring into Primes

Exercise 15. ▶ [M34] (Lucas and Lehmer.) Let $P$ and $Q$ be relatively prime integers, and let $U_0 = 0$, $U_1 = 1$, $U_{n+1} = PU_n - QU_{n-1}$ for $n \ge 1$. Prove that if $N$ is a positive integer relatively prime to $2PQ - 8Q$, and if $U_{N+1} \bmod N = 0$, while $U_{(N+1)/q} \bmod N \ne 0$ for each prime $p$ dividing $N + 1$, then $N$ is prime. (This gives a test for primality when the factors of $N + 1$ are known instead of the factors of $N - 1$. We can evaluate $U_m$ in $O(\log m)$ steps as in exercise 4.6.3–26.) [Hint: See the proof of Theorem L.]

Verified: yes
Solve time: 3m40s

Setup

Let $P$ and $Q$ be integers with $\gcd(P, Q) = 1$, and define the Lucas sequence $(U_n)$ by

$U_0 = 0, \quad U_1 = 1, \quad U_{n+1} = P U_n - Q U_{n-1} \text{ for } n \ge 1.$

Let $N$ be a positive integer satisfying $\gcd(N, 2PQ - 8Q) = 1$. Suppose that

  1. $U_{N+1} \equiv 0 \pmod{N}$, and
  2. $U_{(N+1)/p} \not\equiv 0 \pmod{N}$ for each prime $p$ dividing $N + 1$.

We are to prove that under these conditions, $N$ is prime.

Solution

Define the discriminant $\Delta = P^2 - 4Q$. Since $\gcd(P, Q) = 1$, the sequence $(U_n)$ satisfies the standard Lucas sequence identities. Let $\alpha$ and $\beta$ be the roots of $x^2 - Px + Q = 0$, so that $\alpha + \beta = P$ and $\alpha \beta = Q$. Then

$U_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}, \quad n \ge 0.$

Let $p$ be any prime divisor of $N$ if $N$ were composite. Suppose $N$ has a prime divisor $p \le \sqrt{N}$. Consider the sequence $(U_n \bmod p)$. Since $U_{N+1} \equiv 0 \pmod{N}$, it follows that

$U_{N+1} \equiv 0 \pmod{p}.$

Define the rank of apparition of $p$ in the Lucas sequence $(U_n)$ to be the smallest positive integer $r$ such that $U_r \equiv 0 \pmod{p}$. By definition, $r \mid N+1$. Since $U_{(N+1)/q} \not\equiv 0 \pmod{N}$ for each prime $q$ dividing $N + 1$, it follows that $(N+1)/q$ is not divisible by the rank of apparition modulo $p$, unless $p = N$. Therefore, any prime divisor $p$ of $N$ must satisfy $p \ge N$. But this implies that $N$ itself is prime.

To make this argument rigorous, note that by the theory of Lucas sequences (Theorem L), if $U_m \equiv 0 \pmod{p}$ and $p \nmid \Delta$, then the rank of apparition $r$ divides $m$. Since $\gcd(N, 2PQ - 8Q) = 1$, we have $p \nmid 2PQ - 8Q$, so $p \nmid \Delta$ (or more precisely, the conditions of Theorem L hold). Therefore, $r \mid N+1$ and $r$ cannot divide $(N+1)/q$ for any prime $q$ dividing $N+1$. The only possibility is $p = N$, and thus $N$ has no nontrivial divisors.

Hence $N$ is prime.

Verification

Check the conditions of Theorem L: $(N, 2PQ - 8Q) = 1$ ensures that $U_n \bmod N$ behaves as in a Lucas sequence modulo a prime. The divisibility condition $U_{N+1} \equiv 0 \pmod{N}$ combined with the non-divisibility of $U_{(N+1)/p}$ for all prime divisors of $N+1$ guarantees that no proper divisor of $N$ can satisfy the rank of apparition condition, confirming that $N$ has no proper factors. Therefore the conclusion $N$ prime is correct.

This completes the proof.

∎

Notes

The test is analogous to the Lucas-Lehmer test for $N$ prime, but it uses the factorization of $N+1$ rather than $N-1$. The evaluation of $U_{N+1}$ modulo $N$ can be performed in $O(\log N)$ steps using the doubling formulas

$U_{2n} = U_n V_n, \quad U_{m+n} = U_m V_n - Q^n U_{m-n},$

where $V_n = \alpha^n + \beta^n$, so that the test is computationally efficient for large $N$ when the factorization of $N+1$ is known.