Chuyên đề : Số Nguyên Tố

đưa ra hai phỏng đoán giữa a và 2a ( a là số nguyên dương lớn hơn 1 ) có ít nhất 1 số nguyên tố. Và năm 1852, Pafnouti Livovitch Tchebychev ( 16/5/1821 – 8/12/1894 ) người Nga đã chứng minh phỏng đoán này là đúng. 
Câu hỏi : có phải lúc nào cũng có 1 số nguyên tố giữa không thì vẫn chưa có câu trả lời.
Bạn đọc tự chứng minh kết luận sau đây : khi a > 1 thì giữa ít nhất có 1 số nguyên tố. 
Năm 1830 nhà toán học Adrien Marie Legredre ( 18/9/1752 – 10/1/1833 ) người pháp đã đưa ra phỏng đoán sau đây :
Gọi là số lượng các số nguyên tố nhỏ hơn 1 thì:
Tức là sẽ tiến tới 1 khi n tiến tới vô cùng . Nói cách khác, ( gọi là mật độ các số nguyên tố trong n số nguyên dương đầu tiên ) xấp xỉ bằng và giá trị xấp xỉ sẽ tốt hơn khi n tăng. 
Điều này cũng được “vua toán học” Card Friedrich Gauss ( 30/4/1777 – 23/2/1855 ) người Đức, độc lập phỏng đoán gần như cùng thời gian với A.M.Legendre.
Năm 1848 nhà toán học Sobisev người Nga đã có được kết quả về chứng minh phỏng đoán này. Sau đó P.L.Tchebychev đã chứng minh được :
Năm 1896, viện sĩ toán học Jacques Salomon Hadamard ( 8/12/1865 – 17/10/1963 ) người pháp đã chứng minh được ( 2 – 1 ). Kết quả này cũng được nhà toán học charles. Jean.de la vallés – Poussin ( 14/8/1866 – 2/3/1962 ) người Bỉ độc lập chứng minh năm 1896.
Đến năm 1949, P.Erdos và nhà toán học Atle Selberg ( 19/6/1917 - ?) Người Nauy cũng độc lập chứng minh được ( 2 - 1) bằng cách dựa vào đẳng thức Selberg. Công việc của họ được coi là quan trọng có ý nghĩa hàng đầu đối với lý thuyết số nguyên tố. Nhờ công lao này mà A. Selberg dành được giải thưởng Fields năm 1950, còn P.Erdos thì nhận được giải thưởng đại số và lý thuyết số của Mỹ năm 1951.
Như vậy, phỏng đoán (2 – 1 ) được coi là định lý về sự phân bố số nguyên tố ( của A.M.Legendre và C.F.Gauss ) là định lý nổi tiến và quan trọng nhất trong lý thuyết số. 
A.M.legendre còn khẳng địng rằng, trong 1 triệu số nguyên dương đầu tiên, số lượng số nguyên tố nhỏ hơn n xấp xỉ bằng và ông cho rằng điều này vẫn đáung khi , nhưng P.L.Tchebychev đã bằng cách lập luận chặt chẽ, chứng minh rằng điều này là không có cơ sở khoa học và không đúng nếu .
Từ các kết quả nghiên cứu ta có mật độ các số nguyên tố như sau :
Đến n
10
0,4
0,25
0,168
0,1229
0,09592
0,078496
0,0664579
0,05761555
0,0508475345
0,0455052511
Về số lượng số nguyên tố, nếu không trực tiếp đếm thì không thể nào biết được từ 1 đến 10 triệu số tự nhiên có bao nhiêu số nguyên tố ? Đây là 1 trong hai câu hỏi khó nhất mà đến nay vẫn chưa có câu trả lời. Người ta chỉ biết rằng số nguyên tố càng lớn thì số lượng càng giảm trong mỗi đơn vị số nguyên dương. Chẳng hạn giữa các số tự nhiên. 
1 – 1000 có 168 số nguyên tố 
1000 – 2000 có 135 số nguyên tố 
2000 – 3000 có 124 số nguyên tố 
3000 – 4000 có 120 số nguyên tố 
4000 – 5000 có 119 số nguyên tố 
……….
Số lượng các số nguyên tố là vô hạn đã được Euclice chứng minh khoảng năm 275 trước công nguyên. Đây là một trong hai kết quả chính đạt được trong thời kì Cổ Đại khi nghiên cứu số nguyên tố và được gọi là định lý Euclice, là một định lý quan trọng trong lý thuyết số, đó chính là mệnh đề 20 trong quyển IX của bộ sách “Nguyên lý” được ông viết vào cuối thế kỉ IV trước công nguyên :
“cho trước bao nhiêu số nguyên tố thì sẽ có nhiều số nguyên tố hơn so với chúng.”
Nhưng các số nguyên tố có dạng 
 trong đó và h là số nguyên tố cho trước, có nhiều vô hạn hay hữu hạn số nguyên tố thì vẫn chưa có câu trả lời thích đáng. 
Tuy vậy, tháng 4 – 1995 người ta đã xác định được trong phạm vi h < 35 000 có : 2, 3, 5, 7, 11, 31, 379, 1 019, 1 021, 2 657, 3 229, 4 547, 4 787, 11 549, 13 649, 18 523, 23 801 và 24 029 cho là số nguyên tố ( số nguyên tố gồm 10 378 chữ số ) và 17 số 3, 5, 11, 41, 89, 317, 337, 991, 1 873, 2 053, 2 377, 4 093, 4 297, 4 538, 6 569, 13 033 và 15 877 sao cho là số nguyên tố ( số nguyên tố gồm 6 845 chữ số ).
Khi chứng minh tính vô hạn của số nguyên tố, R.F.Fortane đã đặt p là số nguyên tố nhỏ nhất lớn hơn và phỏng đoán rằng :
“đối với số tự nhiên tuỳ ý đều có số nguyên tố ”.
Chẳng hạn :
Nếu tiếp tục cho h bằng 7,8,9,…,21 thì tương ứng là 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109, 89, 103, 79.
Phần lớn các nhà nghiên cứu về số nguyên tố cho rằng phỏng đoán của R.F.Fortane là đúng nhưng vẫn chưa chứng minh chặt chẽ. 
Người ta cò đặt là số nguyên tố tuỳ ý, lấy số nguyên dương n lớn hơn một số nguyên tố bất kỳ trong dãy và gọi thì đều không chia hết cho có ước số nguyên tố khác với .
Đương nhiên cũng có thể đổi thành 
Phỏng đoán này dẫn chúng ta đến việc nghiên cứu và là số nguyên tố. Trong phạm vi n < 4580, người ta đã phát hiện được 17 giá trị của n : 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477 cho là một số nguyên tố và 20 giá trị của n : 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 378, 469, 546, 974, 1963, 3507, 3610 cho là số nguyên tố. 
Vậy số nguyên tố dạng có vô hạn hay hữu hạn vẫn chưa được làm sáng tỏ.
Cống hiến về việc chứng minh dãy số nguyên tố là vô hạn phải kể đến công lao của L. Euler thật tuyệt vời, tuy có phức tạp hơn cách chứng minh của Euclice, nhưng các nhà toán học lại rất bai phục, vì kết quả có được lớn hơn rất nhiều so với việc chứng minh định lý này. ( xem chi tiết ở tập 4 – các câu chuyên toán học )
In là Logarit tự nhiên của n, lấy e = 2,71828… làm cơ số :
 giải thưởng Fields 4 năm xét 1 lần, là 1 kiểu giải thưởng Nobel cho tóan học ( bởi vì giải thưởng Nobel không xét cho toán học ), do Hội Nghị Toán học thế giới đặt ra năm 1932, với ngân quỹ do nhà toán học John Charles Fields ( 14/5/1963 – 9/8/1932 ) người Canada để lại. 
Kiểm tra tính nguyên tố
Kiểm tra tính nguyên tố (tiếng Anh: primality test) là bài toán kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không. Bài toán này đặc biệt trở nên quan trọng khi các hệ mật mã khoá công khai ra đời.
Mục lục
1 Các phương pháp thô sơ 
2 Kiểm tra theo xác suất 
3 Các phép kiểm tra tất định 
4 Độ phức tạp 
5 Các phương pháp lý thuyết số 
Các phương pháp thô sơ
Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m từ 2 đến n − 1 hay không. Nếu n chia hết cho một số m nào đó thì n là hợp số (composite), ngược lại n là số nguyên tố.
Thực ra việc kiểm tra với m từ 2 đến n − 1 là không cần thiết, mà chỉ cần kiểm tra đến. Đó là vì nếu n là hợp số thì nó chắc chắn có ước số không vượt quá.
Chúng ta cũng có thể bỏ qua việc kiểm tra trường hợp m = 2 bằng cách chỉ xét các số lẻ. Đi xa hơn một chút, ta chỉ cần xét các số dạng và bỏ qua việc kiểm tra 2 trường hợp m = 2 và m = 3. Đó là vì tất cả các số nguyên đều có dạng 6k + i với k nào đó và ; mà trong đó 6k + 0, 6k + 2, 6k + 4 chia hết cho 2, còn 6k + 3 thì chia hết cho 3. Tiếp tục với các nhận xét đó, ta có thể tổng quát hóa thành thuật toán sàng Eratosthenes.
Kiểm tra theo xác suất
Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên, khi đó a có khả năng là một số nguyên tố. Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên không bao giờ kết luận một số nguyên tố là hợp số nhưng có thể kết luận một hợp số là số nguyên tố. Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số a; nếu với mỗi số a xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần thử độc lập, xác suất sai là nhỏ hơn 2−k, độ tin cậy của thuật toán sẽ tăng lên theo k.
Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:
Chọn một số ngẫu nhiên a. 
Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số a là "bằng chứng" chứng tỏ n là hợp số) và dừng thuật toán. 
Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp bước 2. 
Sau một loạt lần kiểm tra, nếu không tìm được bằng chứng chứng tỏ n là hợp số thì ta kết luận n là số nguyên tố.
Các phép kiểm tra tính nguyên tố ngẫu nhiên là
Phép kiểm tra tính nguyên tố của Fermat(kiểm tra Fermat. Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử này 
Được sử dụng nhiều hơn là Kiểm tra Miller-Rabin và Kiểm tra Solovay-Strassen. Với mói hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin) hoặc 1/2 (Với kiểm tra Solovay-Strassen) các số a là bằng chứng chứng tỏ n là hợp số). 
Các phép kiểm tra tất định
Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất.
Độ phức tạp
Trong lý thuyết độ phức tạp, bài toán về tính nguyên tố được gọi đơn giản là bài toán nguyên tố. Dễ thấy rằng nó là conp: bài toán ngược của nó, bài toán hợp số là NP.
Năm 1975, Vaughan Pratt nhận thấy rằng tồn tại các thuật toán kiểm tra tính nguyên tố trong thời gian đa thức, và như vậy PRIMES là NP, và do đó thuộc về NP ∩ conp.
Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Thế cho nên PRIMES là P.
Các phương pháp lý thuyết số
Có một vài phương pháp khác trong lý thuyết số để kiểm tra tính nguyên tố như kiểm tra Lucas-Lehmer và kiểm tra Proth. Chúng thường dựa vào việc phân tích n + 1, n − 1, hoặc những số khác. Tuy nhiên các phương pháp này không dừng cho các số tự nhiên n bất kỳ mã chỉ cho các số có một dạng đặc biệt nào đó Kiểm tra Lucas-Lehmer dựa trên tính chất: bậc (multiplicative order) cúa một số a modulo n là n − 1 với n là số nguyên tố và a là căn nguyên thuỷ (primitive root) modulo n. Nếu ta có thể biểu diễn a chỉ theo n, ta có thể thấy n là nguyên tố.
Hợp số
Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiế