Tớ nghĩ ra một cách cực kỳ đơn giản để tạo ra các số nguyên tố cùng nhau mà không cần đoán mò, và tớ muốn hỏi xem có ai từng thấy cái gì giống vầy chưa. Tớ đã tìm kiếm rất nhiều trên Google nhưng vẫn chưa tìm thấy nó ở đâu cả. Có lẽ những ý tưởng này đã được dùng để phát triển một thuật toán thông minh hơn và tớ chỉ chưa thấy sự liên kết, hoặc trong khi lười biếng lướt qua các trang Wikipedia, tớ có thể đã bỏ lỡ nó. Dù sao thì đây là những gì tớ đã nghĩ ra:
Tớ bắt đầu với ý tưởng rằng vì 2 là số nguyên tố, điều đó có nghĩa là tất cả các số chẵn (hoặc 1/2 của tất cả các số) chắc chắn là hợp số. Do đó, bất kỳ số nào đồng dư với 1(mod 2) có thể là số nguyên tố và là số nguyên tố cùng nhau với 2.
Vì 3 cũng là số nguyên tố, điều đó có nghĩa là cứ mỗi số thứ 3 (hoặc 1/3 của tất cả các số) là hợp số. Điều này cũng có nghĩa là bất kỳ số nào đồng dư với 1(mod 3) hoặc 2(mod 3) đều là số nguyên tố cùng nhau với 3 và có thể là số nguyên tố.
Nếu chúng ta kết hợp các đồng dư này cho 2 và 3, chúng ta sẽ có hai hệ phương trình có thể được giải bằng Định lý phần dư Trung Quốc [:
Hệ 1:
x ≡ 1 (mod 2)
x ≡ 1 (mod 3)
Hệ 2:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
Bất kỳ nghiệm nào của một trong hai hệ này đều chắc chắn là số nguyên tố cùng nhau với cả 2 và 3, và là số nguyên tố hoặc chia hết cho một số nguyên tố không phải là 2 hoặc 3.
Chúng ta có thể tiếp tục mẫu này bằng cách thêm số nguyên tố tiếp theo, 5, vào hệ phương trình của chúng ta:
Hệ 1:
x ≡ 1 (mod 2)
x ≡ 1 (mod 3)
x ≡ 1 (mod 5)
Hệ 2:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 1 (mod 5)
Hệ 3:
x ≡ 1 (mod 2)
x ≡ 1 (mod 3)
x ≡ 2 (mod 5)
Hệ 4:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 2 (mod 5)
…
Hệ (2-1)(3-1)(5-1) = 8:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 4 (mod 5)
Vì vậy, tùy thuộc vào việc chúng ta sử dụng bao nhiêu số nguyên tố làm “hạt giống”, chúng ta sẽ có nhiều hệ phương trình có dạng:
x ≡ ai ( mod ni )
(Các i được cho là chỉ số dưới.)
Chúng ta có thể sử dụng tổ hợp để đếm tổng số hệ mà chúng ta có và bằng cách mở rộng, tổng số nghiệm sẽ có. Ví dụ, với một “hạt giống” là {2,3,5}, chúng ta sẽ có (2-1)(3-1)(5-1) nhiều hệ phương trình.
Bây giờ cuối cùng chúng ta có thể sử dụng CRT để tính toán 8 nghiệm của chúng ta. Theo CRT, mỗi nghiệm cuối cùng là:
x = ( a1 * B1 * m1 + a2 * B2 * m2 + a3 * B3 * m3 ) mod P
(Một lần nữa, các “số mũ” được cho là chỉ số dưới)
Trong đó B, m và P được lấy từ CRT. Hóa ra B, m và P từ tất cả 8 nghiệm có thể có vẫn không đổi, vì vậy, bây giờ, chúng ta cứ nói:
Bi * mi = Ci
Điều này cho chúng ta:
x = (a1 * C1 + a2 * C2 + a3 * C3) mod P
Vì vậy, bây giờ bằng cách hoán đổi các a khác nhau từ mỗi hệ, chúng ta có thể dễ dàng tính toán tất cả 8 nghiệm. Chúng ta kết thúc với tập nghiệm:
{1, 7, 11, 13, 19, 17, 23, 29}
Hóa ra bất cứ khi nào tất cả các ai đều là 1 thì nghiệm cũng là 1.
Tớ đã triển khai điều này trong C++ (mặc dù rất không hiệu quả) và nó có vẻ hoạt động rất tốt. Khi sử dụng một “hạt giống” của tất cả các số nguyên tố từ 1-1000, tớ đã có thể tạo ra một số nguyên tố 416 chữ số (được xác nhận bằng kiểm tra tính nguyên tố Miller-Rabin bằng cách sử dụng 4 lần lặp) sau 28 nghiệm hợp số.
Đây là điều xa nhất mà tớ đã điều tra về Lý thuyết số và các số nguyên tố, vì vậy tớ không chắc liệu kết quả đó có ý nghĩa gì so với các phương pháp khác hay không. Tớ nghi ngờ rằng độ phức tạp về thời gian của thuật toán này khiến nó tương đối vô dụng, nhưng sẽ rất tuyệt nếu biết liệu phương pháp này đã từng được điều tra trước đây hay chưa.
Số nguyên tố tớ tìm thấy sau 28 nghiệm trước đó:
13007828993971307152954644360293504766834573442898858339227968633678291977375601181691065187059816747138118323103729834179301372796481952431423762627827937465863719339790832372830502762657013627224844656215911965643957008489902164235417923907219084872649271473027140080587855297232683010834859003890498970847297694587958274644302279340973991678011684881059955599964477867800859305371265213040241554504859337636835861