Phỏng đoán Mersenne

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong toán học phỏng đoán Mersenne là công cụ có liên quan tới một loại số nguyên tố đặc biệt gọi là số nguyên tố Mersenne (là chìa khoá tìm ra số hoàn thiện.

Phỏng đoán này được tìm ra bởi nhà toán học người Pháp Marin Mersenne trong cuốn Cogitata Physica-Mathematica vào năm 1644 rằng những con số có dạng: 2^n - 1 là số nguyên tố khi n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 và 257. Và là hợp số cho tất cả các số nguyên tố dương khác khi n < 257. Vì số chữ số của một vài số trong số đó quá lớn nên Mersenne không thể kiểm tra tất cả trong số chúng. Tuy nhiên sau này người ta đã tìm ra công nghệ mới để kiểm tra các số này mà tiêu biểu là Kiểm tra Lucas-Lehmer cho số Mersenne thì phát hiện ra Mersenne có 5 lỗi sai. Có 2 số phỏng đoán Mersenne là hợp số khi (n = 67, 257). Trong khi đó lại bỏ qua 3 số nguyên tố khi (n = 61, 89, 107). Bản danh sách đúng của 12 số nguyên tố Mersenne đầu tiên là: 2^n - 1 với n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 và 127.

Khi phỏng đoán gốc của Mersenne thất bại, nó dẫn tới Phỏng đoán Mersenne mớiPhỏng đoán Lenstra–Pomerance–Wagstaff

Phỏng đoán Mersenne mới[sửa | sửa mã nguồn]

Phỏng đoán Mersenne mới hay Phỏng đoán Bateman, Selfridge và Wagstaff (Bateman et al. 1989) cho rằng bất cứ số tự nhiên p lẻ nào mà thoả mãn 2 trong số những điều kiên trên, chúng cũng sẻ thoả mãn điều kiên thứ 3:

  1. p = 2k ± 1 hoặc p = 4k ± 3 cho một vài số tự nhiên k.
  2. 2p − 1 là số nguyên tố (Số nguyên tố Mersenne).
  3. (2p + 1) / 3 là số nguyên tố (Số nguyên tố Wagstaff).

Nếu p là hợp số lẻ, thì 2p − 1 và (2p + 1)/3 đều là hợp số. Điều đó có nghĩa là chỉ cần kiêm tra các số nguyên tố là đủ để kiểm tra sự đúng đắn của phỏng đoán.

Liên kết ngoài[sửa | sửa mã nguồn]