Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Lucas primality test"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(Adding to new subcategory)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
The '''Lucas primality test''' invented in 1891 by [[Edouard Lucas]], determines whether a number N is prime or not, using the complete factorization of N-1.
+
The '''Lucas primality test''' invented in 1891 by [[Édouard Lucas]], determines whether a number N is prime or not, using the complete factorization of N-1.
  
 
If, for some integer b, the quantity b<sup>N-1</sup> is congruent to 1 modulo N, and if b<sup>(N-1)/q</sup> is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime.
 
If, for some integer b, the quantity b<sup>N-1</sup> is congruent to 1 modulo N, and if b<sup>(N-1)/q</sup> is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime.
Line 20: Line 20:
  
 
==External links==
 
==External links==
*[https://en.wikipedia.org/wiki/Lucas_primality_test Wikipedia]
+
*[[wikipedia:Lucas primality test|Wikipedia]]
[[Category:Primality tests]]
+
 
 +
[[Category:Deterministic primality tests]]

Latest revision as of 01:13, 11 August 2024

The Lucas primality test invented in 1891 by Édouard Lucas, determines whether a number N is prime or not, using the complete factorization of N-1.

If, for some integer b, the quantity bN-1 is congruent to 1 modulo N, and if b(N-1)/q is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime.

Example

Prove that N = 811 is prime knowing that N-1 = 2 × 34 × 5

Let's start with b = 3.

[math]\displaystyle{ 3^{810/2}\,= \,3^{405}\,\equiv \, 810\,\pmod{811} }[/math]
[math]\displaystyle{ 3^{810/3}\,= \,3^{270}\,\equiv \, 680\,\pmod{811} }[/math]
[math]\displaystyle{ 3^{810/5}\,= \,3^{162}\,\equiv \, 212\,\pmod{811} }[/math]
[math]\displaystyle{ 3^{810}\,\equiv \, 1\,\pmod{811} }[/math]

All conditions of the test hold so 811 is prime.

The fourth computation is not needed: compute b(N-1)/2 as done in the example, if it is congruent to 1, the value b must be changed, if it is congruent to N-1, the first condition of the test holds, otherwise N is composite.

Notice the b = 7 is a bad choice because:

[math]\displaystyle{ 7^{810/2}\,= \,7^{405}\,\equiv \, 1\,\pmod{811} }[/math]

External links