Kiểm tra Lucas–Lehmer

Bài này nói về kiểm tra Lucas–Lehmer tính nguyên tố cho trường hợp tổng quát. Còn có Kiểm tra Lucas-Lehmer cho số Mersenne.

Trong số học cho máy tính (hay số học thuật toán), kiểm tra Lucas–Lehmer là phép kiểm tra tính nguyên tố đối với số tự nhiên n; nó đòi hỏi rằng có một thừa số nguyên tố của n − 1 là đã biết.

Nếu tồn tại số a nhỏ hơn n và lớn hơn 1 là số thoả mãn

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

và

${\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}}$

với mọi ước nguyên tố qcủa n − 1, thì n là số nguyên tố. Nếu không tìm thấy số a như vậy thì n là hợp số.

Chẳng hạn, với n = 71, n − 1 = 70 = (2)*(5)*(7). Lấy a = 11 trước hết:

${\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}}$

Điều này cho thấy bậc của 11 mod 71 là 70 vì ước của 70 chỉ có thể như trên. Nhưng kiểm tra với các ước của 70 ta có:

${\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}}$

Do đó bậc của 11 mod 71 là 70, và như vậy 71 là số nguyên tố.

Xem thêm

• Kiểm tra tính nguyên tố

Tham khảo