# Lucas test (mathematics)

The Lucas test is a further development of Fermat's primality test by the mathematician Édouard Lucas . The test was improved in the 1950s by Derrick Henry Lehmer and later again by John Brillhart and John L. Selfridge . It should not be confused with the Lucas-Lehmer test for Mersenne numbers .

## Fermatscher primality test

A natural number is given , for which one would like to check whether it is prime. According to the Fermat's primality test is not a prime number if the following condition for too relatively prime number with true: ${\ displaystyle n> 1}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle 1

${\ displaystyle a ^ {n-1} \ not \ equiv 1 {\ pmod {n}}}$

The Fermat test never provides the statement that a number is prime, but can only rule out being prime. The Fermat test does not provide any information about the Carmichael numbers .

## Lucas test

In 1876, Édouard Lucas succeeded in reversing Fermat's little sentence:

(Forerunner of the Lucas test) A natural number is a prime number if and only if there is a with for that ${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle 1

${\ displaystyle a ^ {n-1} \ equiv 1 {\ pmod {n}}}$

such as

${\ displaystyle a ^ {m} \ not \ equiv 1 {\ pmod {n}}}$

holds for all natural numbers . ${\ displaystyle m

This finding is difficult to apply because there are so many to test. In 1891 Lucas corrected the sentence and received the prime number test named after him: ${\ displaystyle m}$

(Lucas test) A natural number is a prime number if and only if there is a with for that ${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle 1

${\ displaystyle a ^ {n-1} \ equiv 1 {\ pmod {n}}}$

such as

${\ displaystyle a ^ {m} \ not \ equiv 1 {\ pmod {n}}}$

holds for all real divisors of . ${\ displaystyle m ${\ displaystyle n-1}$

Since only the divisors of have to be tested here, considerably fewer calculation steps are necessary. A disadvantage, however, is that you have to know the prime factorization of . must therefore be factored . However, this method is very efficient for numbers with a special structure, for example numbers of the form . ${\ displaystyle n-1}$${\ displaystyle n-1}$${\ displaystyle n-1}$${\ displaystyle 2 ^ {k} +1}$

If the condition of the Lucas test for a basis is not fulfilled, it does not follow that the number is composed. For that you would have to check all bases . ${\ displaystyle a}$${\ displaystyle n}$${\ displaystyle 1

Example:

The following applies to the number . The real dividers of are and . Further applies and . It follows that is a prime number. ${\ displaystyle n = 59}$${\ displaystyle 2 ^ {58} \ equiv 1 \ mod \ 59}$${\ displaystyle n-1 = 58}$${\ displaystyle 1,2}$${\ displaystyle 29}$${\ displaystyle 2 ^ {1} \ equiv 2 \ mod \ 59.2 ^ {2} \ equiv 4 \ mod \ 59}$${\ displaystyle 2 ^ {29} \ equiv -1 \ mod \ 59}$${\ displaystyle 59}$

## Extensions by Lehmer, Brillhart and Selfridge

Derrick Henry Lehmer found the improved Lucas test in 1953 . In 1967 another version ( flexible Lucas test ) was discovered by John Brillhart and John L. Selfridge .

### Improved Lucas test

The improved Lucas test is based on the following property: is a prime number if and only if there is a natural number with for which
${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle 1

${\ displaystyle a ^ {n-1} \ equiv 1 {\ pmod {n}}}$

such as

${\ displaystyle a ^ {\ frac {n-1} {q_ {i}}} \ not \ equiv 1 {\ pmod {n}}}$

for all prime factors of . ${\ displaystyle q_ {i}}$${\ displaystyle n-1}$

The application of this test to Fermat numbers is called the Pépin test .

### Flexible Lucas test

The flexible Lucas test is based on the following property:
The prime factorization of the natural number is given by ${\ displaystyle n}$${\ displaystyle n-1}$

${\ displaystyle n-1 = q_ {1} ^ {e_ {1}} \ cdot \ ldots \ cdot q_ {r} ^ {e_ {r}}}$.

Then the following applies: is a prime number if and only if there is a natural number with for every prime factor for which ${\ displaystyle n}$${\ displaystyle q_ {i}}$${\ displaystyle a_ {i}}$${\ displaystyle 1

${\ displaystyle a_ {i} ^ {n-1} \ equiv 1 {\ pmod {n}}}$

such as

${\ displaystyle a_ {i} ^ {\ frac {n-1} {q_ {i}}} \ not \ equiv 1 {\ pmod {n}}}$

applies.

#### example

We consider the prime number . The previous number has the prime divisors and . The following table shows suitable and how the conditions are met: ${\ displaystyle n = 911}$${\ displaystyle n-1 = 910}$${\ displaystyle q = 2,5,7}$${\ displaystyle 13}$${\ displaystyle a}$

q a a n-1 ≡ 1 (mod n) a (n-1) / q ≢ 1 (mod n)
2 7th 7 910 ≡ 1 (mod 911) 7 910/2 ≡ -1 (mod 911)
5 3 3 910 ≡ 1 (mod 911) 3 910/5 ≡ 482 (mod 911)
7th 2 2 910 ≡ 1 (mod 911) 2 910/7 ≡ 568 (mod 911)
13 2 2 910 ≡ 1 (mod 911) 2 910/13 ≡ 577 (mod 911)

## Pratt prime number test

The Pratt test is an iterated Lucas test. In turn, it is checked for all prime factors of whether these are prime numbers. ${\ displaystyle n-1}$

### Fermat couple

${\ displaystyle (a, b)}$is a Fermat pair if ${\ displaystyle (a, b) = (1,2) \ lor (a \ geq 2 \ land a ^ {n-1} \ not \ equiv 1 \ mod n)}$

### Pratt sequence

${\ displaystyle (a_ {1}, b_ {1}) \ dots (a_ {k}, b_ {k})}$is a Pratt sequence if for each Fermat pair from the sequence it is true that for each prime factor of a Fermat pair is contained in the Pratt sequence and the following applies:${\ displaystyle (a, b)}$${\ displaystyle p}$${\ displaystyle b}$${\ displaystyle (a ', p)}$${\ displaystyle a ^ {\ frac {n-1} {p}} \ not \ equiv 1}$

For every prime number there is a Pratt sequence the length of the representation of the prime number, which is why . ${\ displaystyle Prime \ in NP}$

### example

For the following is a possible Pratt sequence ${\ displaystyle 797}$

${\ displaystyle (5,797), (1,2), (6,199), (5.3), (3.11)}$

to check is now even whether , and on whether the prime divisors of true${\ displaystyle a ^ {b-1} \ equiv 1}$${\ displaystyle p}$${\ displaystyle b-1}$${\ displaystyle a ^ {\ frac {b-1} {2}} \ not \ equiv}$

${\ displaystyle (5,797)}$

${\ displaystyle 5 ^ {797-1} \ mod 797 \ equiv 5 ^ {796} \ mod 797 \ equiv 1}$

${\ displaystyle 5 ^ {\ frac {796} {2}} \ mod 797 \ equiv 5 ^ {398} \ mod 797 \ equiv 796 \ not \ equiv 1}$

${\ displaystyle 5 ^ {\ frac {796} {199}} \ mod 797 \ equiv 5 ^ {4} \ mod 797 \ equiv 625 \ not \ equiv 1}$

${\ displaystyle (6,199)}$

${\ displaystyle 6 ^ {199-1} \ mod 199 \ equiv 6 ^ {198} \ mod 199 \ equiv 1}$

${\ displaystyle 6 ^ {\ frac {198} {2}} \ mod 199 \ equiv 6 ^ {99} \ mod 199 \ equiv 198 \ not \ equiv 1}$

${\ displaystyle 6 ^ {\ frac {198} {3}} \ mod 199 \ equiv 6 ^ {66} \ mod 199 \ equiv 192 \ not \ equiv 1}$

${\ displaystyle 6 ^ {\ frac {198} {11}} \ mod 199 \ equiv 6 ^ {18} \ mod 199 \ equiv 63 \ not \ equiv 1}$

${\ displaystyle (5.3)}$

${\ displaystyle 5 ^ {3-1} \ mod 3 \ equiv 5 ^ {2} \ mod 3 \ equiv 1}$

${\ displaystyle 5 ^ {\ frac {2} {2}} \ mod 3 \ equiv 5 ^ {1} \ mod 3 \ equiv 2 \ not \ equiv 1}$

${\ displaystyle (2.5)}$

${\ displaystyle 2 ^ {5-1} \ mod 5 \ equiv 2 ^ {4} \ mod 5 \ equiv 1}$

${\ displaystyle 2 ^ {\ frac {2} {2}} \ mod 5 \ equiv 2 ^ {1} \ mod 5 \ equiv 2 \ not \ equiv 1}$

## Individual evidence

1. Proof of this: see Ribenboim, Die Welt der Prime Numbers , page 40.
2. To prove this and the previous theorem, see Ribenboim, Die Welt der Prime Numbers , page 42.
3. ^ Daniela Steidl: Pratt certificate of prime numbers. April 17, 2008, accessed May 7, 2020 .
4. apl. Prof. Dr. Klaus Reinhardt: Pratt prime number test. Retrieved on May 7, 2020 (German, English).