✨Kiểm tra Proth

Trong toán học, định lý Proth là một phương pháp kiểm tra tính nguyên tố dùng cho các số Proth.

Cho p là một số Proth, dạng _k_2ⁿ + 1 với k lẻ và k < 2ⁿ, khi đó nếu có số nguyên a nào đó sao cho :$a^\{(p-1)/2\}\backslash equiv\; -1\; \backslash pmod\{p\}\backslash ,!$ thì p là số nguyên tố

Ví dụ

Bảy số nguyên Proth đầu tiên là

:P₀ = 2¹ + 1 = 3 :P₁ = 2² + 1 = 5 :P₂ = 2³ + 1 = 9 :P₃ = 3 × 2² + 1 = 13 :P₄ = 2⁴ + 1 = 17 :P₅ = 3 × 2³ + 1 = 25 :P₆ = 2⁵ + 1 = 33

Ta có:

• với p = 3,lấy a = 2 ta có 2¹ = 2 $\backslash equiv\; -1\; \backslash pmod\{3\}\backslash ,!$, nên 3 là số nguyên tố.
• với p = 5,lấy a = 3 ta có 3² = 9 $\backslash equiv\; -1\; \backslash pmod\{5\}\backslash ,!$, nên 5 là số nguyên tố.
• với p = 13,lấy a = 5 ta có 5⁶ = 15626 $\backslash equiv\; -1\; \backslash pmod\{13\}\backslash ,!$, nên 13 là số nguyên tố.
• với p = 9, không có số a nào cho ta a⁴ $\backslash equiv\; -1\; \backslash pmod\{9\}\backslash ,!$, nên 9 không là số nguyên tố.

Lịch sử

François Proth (1852 - 1879) tìm ra định lý này khoảng vào năm 1878.