Kiểm tra Proth
một bài kiểm tra nguyên tố cho số Proth From Wikipedia, the free encyclopedia
Remove ads
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 k2n + 1 với k lẻ và k < 2n, khi đó nếu có số nguyên a nào đó sao cho
thì p là số nguyên tố
Remove ads
Ví dụ
Bảy số nguyên Proth đầu tiên là
- P0 = 21 + 1 = 3
- P1 = 22 + 1 = 5
- P2 = 23 + 1 = 9
- P3 = 3 × 22 + 1 = 13
- P4 = 24 + 1 = 17
- P5 = 3 × 23 + 1 = 25
- P6 = 25 + 1 = 33
Ta có:
- với p = 3,lấy a = 2 ta có 21 = 2 , nên 3 là số nguyên tố.
- với p = 5,lấy a = 3 ta có 32 = 9 , nên 5 là số nguyên tố.
- với p = 13,lấy a = 5 ta có 56 = 15626 , nên 13 là số nguyên tố.
- với p = 9, không có số a nào cho ta a4 , nên 9 không là số nguyên tố.
Remove ads
Lịch sử
François Proth (1852 - 1879) tìm ra định lý này khoảng vào năm 1878.
Xem thêm
- Kiểm tra tính nguyên tố
- Số Sierpinski
Tham khảo
Liên kết ngoài
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads