The Lucas primality test can prove that an integer n is prime when the factorization of n − 1 is known and a suitable base can be found. It strengthens the familiar Fermat congruence by checking that the chosen base has the largest possible multiplicative order modulo n.
That distinction matters. Passing a Fermat test can make a number look prime even when it is composite. Passing the full Lucas criterion gives a primality proof.
Lucas criterion
Let n > 2 and write n − 1 as a product of primes. If there is an integer a such that:
an−1 ≡ 1 (mod n)
and, for every distinct prime divisor q of n − 1,
a(n−1)/q ≢ 1 (mod n),
then n is prime.
Why the Test Uses n − 1
The Lucas test is really a test of multiplicative order. For a number a that is coprime to n, the order of a modulo n is the smallest positive exponent r for which:
ar ≡ 1 (mod n).
The first Lucas condition says that the order divides n − 1. The extra checks rule out every way that the order could be a proper divisor of n − 1. If all of them pass, the order must equal n − 1.
Example structure for n = 29
29 − 1 = 28 = 22 × 7. The distinct prime divisors are 2 and 7, so the Lucas checks use the exponents 28/2 = 14 and 28/7 = 4.
Repeated prime factors do not create repeated tests. If n − 1 = 23 × 32 × 5, the relevant values of q are simply 2, 3, and 5.
Lucas Primality Test Method
1. Handle simple cases
The number 2 is prime. Any integer below 2 is not prime, and any even integer greater than 2 is composite. These cases do not need the Lucas calculation.
2. Factor n − 1
Write n − 1 as a product of primes and keep the set of distinct prime divisors. The classical Lucas criterion needs the full prime factorization of n − 1.
3. Choose a base a
Choose an integer a with 1 < a < n. Checking gcd(a, n) first is useful. If that greatest common divisor is greater than 1, it exposes a nontrivial factor and proves that n is composite.
4. Check the Fermat congruence
Compute:
an−1 mod n.
If the result is not 1, n is composite. A prime number cannot fail this condition when a is not divisible by n.
5. Check every distinct prime divisor q
For each distinct prime q dividing n − 1, compute:
a(n−1)/q mod n.
Every one of these residues must be different from 1. When that happens, the selected base is a Lucas witness and proves that n is prime.
| Result | Meaning |
|---|---|
| an−1 ≢ 1 (mod n) | Composite |
| Main condition passes, but a q-check equals 1 | This base is inconclusive; it does not prove that the number is composite |
| Main condition passes and every q-check is non-1 | Prime; a Lucas certificate has been found |
Example: Proving That 29 Is Prime
Take n = 29. First factor n − 1:
28 = 22 × 7.
The distinct prime divisors are 2 and 7. Choose a = 2.
The main congruence gives:
228 ≡ 1 (mod 29).
Now test the two required reduced exponents:
| Check | Exponent | Residue mod 29 | Status |
|---|---|---|---|
| Main condition | 28 | 1 | Pass |
| q = 2 | 14 | 28 | Pass |
| q = 7 | 4 | 16 | Pass |
Neither reduced-exponent check gives 1. Therefore the order of 2 modulo 29 is 28, exactly n − 1.
Result: 29 is prime.
A Failed Base Does Not Always Mean Composite
This is one of the easiest parts of the Lucas test to misread. If the main Fermat condition passes but one reduced-exponent test returns 1, the selected base has failed to certify primality. The number itself may still be prime.
Consider n = 71:
70 = 2 × 5 × 7.
With base a = 17:
1770 ≡ 1 (mod 71),
but the check for q = 7 gives:
1710 ≡ 1 (mod 71).
Base 17 therefore does not provide a Lucas certificate. It would be wrong to label 71 composite from this result.
Try a = 11 instead:
| Expression | Residue mod 71 |
|---|---|
| 1170 | 1 |
| 1135 | 70 |
| 1114 | 54 |
| 1110 | 32 |
The main condition is 1, while all three reduced-exponent residues are non-1. Base 11 proves that 71 is prime.
Why Fermat Alone Is Not Enough
Fermat’s little theorem says that if p is prime and gcd(a, p) = 1, then:
ap−1 ≡ 1 (mod p).
The converse is false. Some composite numbers also satisfy this congruence for a chosen base. Carmichael numbers go further and satisfy it for every base coprime to the number.
Take 561, where:
561 = 3 × 11 × 17
and:
2560 ≡ 1 (mod 561).
A Fermat test to base 2 passes, even though 561 is composite. The Lucas-style reduced-exponent check exposes that base 2 does not have order 560:
2280 ≡ 1 (mod 561).
Important distinction: the residue 1 in that reduced-exponent check shows that base 2 is not a Lucas witness. The known factorization 561 = 3 × 11 × 17 is what directly proves that 561 is composite.
Why the Lucas Conditions Prove Primality
Suppose all Lucas conditions hold for a base a. Let ordn(a) denote the multiplicative order of a modulo n.
Because:
an−1 ≡ 1 (mod n),
the order divides n − 1. If the order were a smaller divisor, then at least one prime q dividing n − 1 would make the order divide (n − 1)/q. That would force:
a(n−1)/q ≡ 1 (mod n),
contradicting the Lucas condition. Therefore:
ordn(a) = n − 1.
The order of any invertible residue modulo n divides Euler’s totient φ(n). So φ(n) must be at least n − 1. But φ(n) can never exceed n − 1, and equality occurs exactly when n is prime. Hence n must be prime.
Lucas Test, Lucas Probable Prime, and Lucas–Lehmer
The name “Lucas test” can refer to different ideas. They should not be treated as interchangeable.
| Method | Input type | Main idea | Typical result |
|---|---|---|---|
| Lucas primality test | General integer n | Factor n − 1 and prove order n − 1 | Prime certificate |
| Lucas probable-prime test | General odd integers | Lucas sequences | Probable prime or composite evidence |
| Lucas–Lehmer test | Mersenne candidates 2p − 1 | Special recurrence modulo the Mersenne number | Deterministic primality result for that form |
The classical Lucas criterion on this page is the first method in the table. It does not use the Lucas sequence recurrence from a Lucas probable-prime test, and it is not the Lucas–Lehmer test for Mersenne numbers.
How Lucas Compares with Other Primality Tests
| Test | Needs full factorization of n − 1? | Can prove prime? | Best fit |
|---|---|---|---|
| Fermat | No | No, by itself | Simple composite screening |
| Lucas | Yes, in the classical form | Yes | Primality proof when n − 1 is factored |
| Miller–Rabin | No | Usually used probabilistically; deterministic over proven bounded ranges | Fast testing of many candidates |
| Pocklington | Not always | Yes | Proofs using a sufficiently large known factored part of n − 1 |
| Lucas–Lehmer | No general n − 1 factorization | Yes | Mersenne numbers |
The main practical cost of the classical Lucas method is often not modular exponentiation. It is obtaining and verifying the full prime factorization of n − 1. If that factorization is already known or easy to obtain, Lucas becomes much more attractive.
Modular Exponentiation Keeps the Arithmetic Manageable
A Lucas implementation should not construct a huge integer such as an−1 and reduce it afterward. It computes powers modulo n throughout the process.
For example, 214 mod 29 can be built from repeated squaring:
- 22 = 4
- 24 = 16
- 28 ≡ 24 (mod 29)
- 214 = 28 × 24 × 22 ≡ 28 (mod 29)
This binary-exponentiation approach keeps intermediate values small and is the standard way to evaluate the powers used by the test.
Lucas Primality Test Pseudocode
LucasTest(n):
if n == 2:
return PRIME
if n < 2 or n is even:
return COMPOSITE
factor n - 1 completely
Q = distinct prime divisors of n - 1
for candidate base a in the selected base set:
if gcd(a, n) > 1:
return COMPOSITE
if powmod(a, n - 1, n) != 1:
return COMPOSITE
witness = true
for q in Q:
if powmod(a, (n - 1) / q, n) == 1:
witness = false
break
if witness:
return PRIME
return NO_CERTIFICATE_FOUNDThe last return value matters. Exhausting a chosen set of bases without finding a Lucas witness is not the same as proving compositeness.
What If n − 1 Is Not Fully Factored?
The classical Lucas criterion cannot produce its usual certificate until the prime divisors needed for the order checks are known. An incomplete factorization therefore means the proof is incomplete, not that the candidate failed a primality test.
Pocklington-style tests address this situation. They can prove primality from a sufficiently large verified factored part of n − 1, so they are often a better fit when full factorization is difficult.
Practical rule: if n − 1 is already fully factored, the Lucas criterion is clean and direct. If only part of n − 1 is factored, a Pocklington-type certificate may avoid unnecessary factoring work.
Lucas Witnesses and Primitive Roots
For prime n, a successful Lucas base has multiplicative order n − 1. In group language, that base is a generator of the nonzero residue classes modulo n, also called a primitive root modulo n.
This explains why merely passing Fermat is weaker. Fermat only shows that the order divides n − 1. Lucas checks whether the order actually reaches n − 1.
From Lucas Witnesses to Primality Certificates
The Lucas idea also leads naturally to recursively verifiable primality certificates. A certificate for a prime p can record the factorization of p − 1, a Lucas witness for p, and certificates showing that the prime factors of p − 1 are themselves prime.
Repeating that process eventually reaches small primes that can be checked directly. This is the basic idea behind Pratt certificates: primality is represented as a short chain of verifiable modular facts rather than only as the output of a black-box test.
Common Lucas Test Errors
- Treating the Fermat congruence as the whole test. The reduced-exponent checks are what turn the condition into a primality certificate.
- Calling every failed base a composite result. A base can fail to certify a number that is still prime, as the 71 example shows.
- Using unverified factors of n − 1. The proof depends on the claimed divisors q actually being prime divisors of n − 1.
- Checking repeated prime factors more than once. Only the distinct prime divisors of n − 1 are needed.
- Confusing Lucas with Lucas–Lehmer. Lucas–Lehmer is a specialized test for Mersenne candidates.
- Confusing a Lucas primality certificate with a Lucas probable-prime test. The latter uses Lucas sequences and has a different role.
- Computing enormous powers directly. Modular exponentiation evaluates the same congruences much more efficiently.
- Using “probably prime” after all Lucas conditions pass. When the hypotheses have been fully verified, the conclusion is prime, not merely probable prime.
When the Lucas Test Is a Good Fit
Lucas is especially useful when n − 1 already has a known prime factorization and the goal is a result that can be independently checked. It is less convenient when factoring n − 1 is harder than the primality question that started the calculation.
For a direct check of an integer without manually building a Lucas certificate, the Prime Number Checker provides a faster route. The Lucas method is most valuable when the proof itself matters: it explains why the candidate is prime by exhibiting an element with multiplicative order exactly n − 1.