Số nguyên tố

Hợp số có thể được sắp xếp thành các hình chữ nhật, còn số nguyên tố thì không

Số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Chẳng hạn, 5 là số nguyên tố bởi vì cách duy nhất để viết nó dưới dạng một tích, 1 × 5 hoặc 5 × 1, có một thừa số là chính số 5. Tuy nhiên, 4 là hợp số vì nó là tích của hai số (2 × 2) mà trong đó hai số đó đều nhỏ hơn 4. Số nguyên tố là nội dung trọng tâm trong lý thuyết số theo định lý cơ bản của số học: mọi số tự nhiên lớn hơn 1 hoặc là số nguyên tố hoặc có thể được phân tích nhân tử thành tích của các số nguyên tố một cách duy nhất xê xích một phép hoán vị.

Tính chất của một số nguyên tố được gọi là tính nguyên tố. Một phương pháp đơn giản để kiểm tra tính nguyên tố của một số $n$, được gọi là giải thuật chia thử, kiểm tra xem $n$ có phải là bội số của bất kỳ số nguyên nào giữa 2 và ${\sqrt {n}}$ hay không. Một số thuật toán khác bao gồm kiểm tra Miller–Rabin, tuy nhanh nhưng có thể xảy ra lỗi và phép kiểm tra tính nguyên tố AKS, vốn luôn tạo ra câu trả lời đúng trong khoảng thời gian đa thức nhưng quá chậm để áp dụng trong thực tế. Ngoài ra, còn có một số thuật toán nhanh dành cho các số có dạng đặc biệt, chẳng hạn như số nguyên tố Mersenne. Tính đến tháng 12 năm 2018 số nguyên tố lớn nhất đã biết có 24.062.048 chữ số.

Có vô số số nguyên tố, như đã được Euclid chứng minh vào khoảng năm 300 TCN. Hầu như không có công thức đơn giản nào để phân biệt số nguyên tố và hợp số. Tuy nhiên, sự phân phối các số nguyên tố trong tập hợp các số tự nhiên có thể được mô hình hóa theo thống kê. Kết quả đầu tiên theo hướng đó là định lý số nguyên tố, được chứng minh vào cuối thế kỷ 19, cho rằng xác suất để một số bất kỳ là số nguyên tố tỷ lệ nghịch với số chữ số của nó, nghĩa là với logarit của nó.

Một số bài toán lịch sử liên quan đến số nguyên tố vẫn chưa có lời giải. Chúng bao gồm giả thuyết của Goldbach, cho rằng mọi số nguyên chẵn lớn hơn 2 có thể được biểu diễn thành tổng của hai số nguyên tố, và phỏng đoán về số nguyên tố sinh đôi, cho rằng có vô số cặp số nguyên tố chỉ có một số chẵn giữa chúng. Những bài toán như thế đã góp phần thúc đẩy sự phát triển của nhiều nhánh trong lý thuyết số, trong đó có lý thuyết số đại số và lý thuyết số giải tích. Số nguyên tố cũng có ứng dụng trong một số lĩnh vực của công nghệ thông tin, chẳng hạn như mật mã hóa khóa công khai, dựa vào sự phức tạp trong việc phân tích các số nguyên lớn thành nhân tử. Trong đại số trừu tượng, còn có một số khái niệm toán học khác có đặc điểm và tính chất giống với số nguyên tố, chẳng hạn như phần tử nguyên tố và ideal nguyên tố.

Định nghĩa và ví dụ

Bài chi tiết: Danh sách số nguyên tố

Một số tự nhiên (1, 2, 3, 4, 5, 6, ...) được gọi là số nguyên tố nếu nó lớn hơn 1 và không thể được biểu diễn thành tích của hai số tự nhiên nhỏ hơn. Các số lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Nói cách khác, $n$ là số nguyên tố nếu $n$ vật không thể chia đều thành nhiều nhóm nhỏ gồm nhiều hơn một vật, hoặc $n$ dấu chấm không thể được sắp xếp thành một hình chữ nhật có chiều dài và chiều rộng nhiều hơn một dấu chấm. Chẳng hạn, trong các số từ 1 đến 6, số 2, 3 và 5 là số nguyên tố vì không có số nào khác có thể chia hết được chúng (số dư bằng 0). 1 không phải là số nguyên tố vì nó đã được loại trừ ra khỏi định nghĩa. 4 = 2 × 2 và 6 = 2 × 3 đều là hợp số.

Hình minh họa cho thấy 7 là số nguyên tố vì không có số nào trong các số 2, 3, 4, 5, 6 có thể chia hết được 7

Ước của một số tự nhiên $n$ là các số tự nhiên có thể chia hết được $n$. Mọi số tự nhiên đều có ít nhất hai ước là 1 và chính nó. Nếu nó còn có thêm một ước khác thì nó không thể là số nguyên tố. Từ ý tưởng đó mà ta có một định nghĩa khác về số nguyên tố: đó là những số chỉ có đúng hai ước dưong là 1 và chính nó. Ngoài ra, còn có một cách diễn đạt khác nữa: $n$ là số nguyên tố nếu nó lớn hơn 1 và không có số nào trong các số $2,3,\dots ,n-1$ có thể chia hết được nó.

25 số nguyên tố đầu tiên (tất cả các số nguyên tố nhỏ hơn 100) là:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (dãy số A000040 trong bảng OEIS).

Không có số chẵn $n$ lớn hơn 2 nào là số nguyên tố vì một số chẵn bất kỳ có thể được biểu diễn thành $2\times n/2$. Do đó, tất cả số nguyên tố ngoài số 2 là số lẻ và được gọi là số nguyên tố lẻ. Tuơng tự, khi được viết trong hệ thập phân, tất cả số nguyên tố lớn hơn 5 đều có tận cùng là 1, 3, 7 hoặc 9. Các số có tận cùng là chữ số khác đều là hợp số: số có tận cùng là 0, 2, 4, 6 hoặc 8 là số chẵn, và số có tận cùng là 0 hoặc 5 thì chia hết cho 5.

Tập hợp các số nguyên tố được ký hiệu là $\mathbf {P}$ hoặc $\mathbb {P}$.

Lịch sử

Giấy cọ Rhind

Giấy cọ Rhind (từ khoảng năm 1550 trước Công nguyên) chứa các phân số Ai Cập được mở rộng theo nhiều dạng khác nhau cho số nguyên tố và hợp số. Tuy nhiên, các công trình nghiên cứu cụ thể về số nguyên tố của toán học Hy Lạp cổ đại được lưu lại sớm nhất. Bộ Cơ sở của Euclid (khoảng 300 TCN) có phần chứng minh sự tồn tại vô số số nguyên tố và định lý cơ bản của số học, đồng thời nêu cách tạo ra một số hoàn thiện từ số nguyên tố Mersenne. Một phát minh khác từ Hy Lạp là sàng Eratosthenes vẫn còn được dùng để lập danh sách các số nguyên tố.

Khoảng năm 1000, nhà toán học Hồi giáo Ibn al-Haytham (Alhazen) tìm ra định lý Wilson, xác định số nguyên tố là các số $n$ chia hết được $(n-1)!+1$. Ông cũng phỏng đoán rằng tất cả số hoàn thiện chẵn đều có được khi tạo ra từ số nguyên tố Mersenne theo cách của Euclid, nhưng không chứng minh được nó. Một nhà toán học Hồi giáo khác, Ibn al-Banna' al-Marrakushi tìm ra rằng sàng Eratosthenes có thể được đẩy nhanh khi chỉ kiểm tra các ước lớn đến căn bậc hai của số lớn nhất được kiểm tra. Fibonacci sau đó đã mang những ý tưởng mới này từ toán học Hồi giáo về châu Âu. Cuốn Liber Abaci (1202) của ông là cuốn sách đầu tiên mô tả giải thuật chia thử để kiểm tra tính nguyên tố chỉ bằng việc kiểm tra các ước lớn đến căn bậc hai của số cần kiểm tra.

Năm 1640, Pierre de Fermat phát biểu định lý nhỏ Fermat (về sau được Leibniz và Euler chứng minh). Fermat cũng đã nghiên cứu và kiểm tra tính nguyên tố của số Fermat $2^{2^{n}}+1$, và Marin Mersenne nghiên cứu số nguyên tố Mersenne, số nguyên tố có dạng $2^{p}-1$ với $p$ cũng là số nguyên tố. Trong bức thư gửi Euler năm 1742, Christian Goldbach đã phát biểu giả thuyết Goldbach cho rằng mọi số chẵn đều là tổng của hai số nguyên tố. Euler chứng minh được giả thuyết của Alhazen (về sau gọi là định lý Euclid–Euler) rằng mọi số hoàn thiện chẵn có thể được tạo ra từ số nguyên tố Mersenne. Ông cũng giới thiệu các phuơng pháp được ứng dụng từ giải tích toán học trong lĩnh vực này khi chứng minh sự tồn tại vô số số nguyên tố và tính phân kỳ của tổng nghịch đảo các số nguyên tố ${\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots$. Đầu thế kỷ 19, Legendre và Gauss đưa ra phỏng đoán cho rằng khi $x$ tiến về vô hạn thí số lượng số nguyên tố nhỏ hơn hoặc bằng $x$ tiệm cận về $x/\log x$ với $\log x$ là logarit tự nhiên của $x$. Ý tưởng của Bernhard Riemann trong công trình năm 1859 về hàm zeta của ông đã góp phần vạch ra hướng đi để chứng minh phỏng đoán đó. Mặc dù một phỏng đoán liên quan là giả thuyết Riemann vẫn chưa có lời giải, đại cuơng của Riemann đã được hoàn thành vào năm 1896 bởi Hadamard và de la Vallée Poussin và kết quả này hiện được biết đến với tên gọi là định lý số nguyên tố. Một thành tựu quan trọng khác trong thế kỷ 19 là định lý Dirichlet về cấp số cộng cho rằng một cấp số cộng nhất định chứa vô số số nguyên tố.

Nhiều nhà toán học đã nghiên cứu các thuật toán kiểm tra tính nguyên tố với các số lớn hơn so với các số mà giải thuật chia thử có thể áp dụng được. Các thuật toán giới hạn về một dạng số cụ thể bao gồm kiểm tra Pépin cho số Fermat (1877), định lý Proth (khoảng 1878), kiểm tra Lucas–Lehmer (1856) và dạng tổng quát của nó, kiểm tra Lucas.

Từ năm 1951, tất cả các số nguyên tố lớn nhất đã biết đều được tìm thông qua các thuật toán trên máy tính. Công cuộc tìm ra số nguyên tố lớn hơn thế đã gây chú ý ngoài phạm vi toán học với dự án Great Internet Mersenne Prime Search và nhiều dự án điện toán phân tán khác. Quan niệm rằng số nguyên tố ít được ứng dụng ngoài toán học thuần túy đã bị xóa bỏ vào những năm 1970 khi mật mã hóa khóa công khai và mã hóa RSA được phát minh dựa trên số nguyên tố.

Tầm quan trọng ngày càng lớn của việc kiểm tra tính nguyên tố và phân tích số nguyên tố trên máy tính dẫn đến sự phát triển của nhiều thuật toán khác có thể thực hiện được với các số rất lớn không thuộc bất kỳ dạng đặc biệt nào. Lý thuyết toán học về số nguyên tố cũng tiếp tục phát triển trong thời kỳ hiện đại với định lý Green–Tao (2004) phát biểu rằng dãy các số nguyên tố có chứa một cấp số cộng với độ dài bất kỳ, và chứng minh của Yitang Zhang năm 2013 rằng tồn tại vô số khoảng cách nguyên tố với kích thước giới hạn.

Tính nguyên tố của số 1

Đa số nhà toán học Hy Lạp cổ không cho rằng 1 là một số nên họ không thể xét được tính nguyên tố của nó. Một số nhà toán học thời điểm đó cũng cho rằng số nguyên tố có được từ sự chia nhỏ các số lẻ nên họ không xem số 2 là số nguyên tố. Tuy nhiên, Euclid và đa số nhà toán học Hy Lạp cổ xem 2 là số nguyên tố. Các nhà toán học Hồi giáo cũng nối tiếp theo Hy Lạp, không công nhận 1 là một số. Đến thời Trung Cổ và Phục Hưng, các nhà toán học bắt đầu thừa nhận 1 là một số, và một vài trong số đó cho rằng số 1 là số nguyên tố đầu tiên. Giữa thế kỷ 18, Christian Goldbach công nhận số 1 là số nguyên tố trong thư gửi Leonhard Euler, nhưng Euler lại không thừa nhận như thế. Nhiều nhà toán học thế kỷ 19 vẫn cho rằng 1 là số nguyên tố, và danh sách số nguyên tố có chứa số 1 vẫn tiếp tục được xuất bản cho đến năm 1956.

Nếu định nghĩa số nguyên tố bị thay đổi để công nhận 1 là số nguyên tố, nhiều định lý liên quan đến nó phải được diễn đạt lại một cách rắc rối. Chẳng hạn, định lý cơ bản của số học khi đó sẽ bị sửa lại về mặt phân tích thành các số nguyên tố lớn hơn 1, vì mọi số đều có vô số cách phân tích mà trong đó số 1 xuất hiện với số lần bất kỳ. Tuơng tự, sàng Eratosthenes cũng sẽ không hoạt động đúng cách, vì khi đó nó loại bỏ tất cả các bội của 1 (tức là tất cả các số khác) và cho đầu ra chỉ có duy nhất số 1. Một số tính chất của số nguyên tố cũng không đúng đối với số 1: ví dụ, công thức của hàm phi Euler hoặc hàm tổng các ước khác nhau với số nguyên tố so với số 1. Đến đầu thế kỷ 20, các nhà toán học bắt đầu thừa nhận rằng số 1 không nên nằm trong danh sách số nguyên tố, mà thay vào đó cần nằm trong khái niệm đặc biệt: "đơn vị" trong lý thuyết vành.

Tính chất cơ bản

Sự phân tích duy nhất

Bài chi tiết: Định lý cơ bản của số học

Viết một số thành tích của các số nguyên tố được gọi là phân tích nguyên tố của số đó. Chẳng hạn:

${\begin{aligned}34866&=2\cdot 3\cdot 3\cdot 13\cdot 149\\&=2\cdot 3^{2}\cdot 13\cdot 149.\end{aligned}}$

Các thừa số trong tích được gọi là thừa số nguyên tố. Một thừa số nguyên tố có thể xuất hiện nhiều lần, khi đó có thể dùng lũy thừa để gộp nhiều thừa số giống nhau đó lại thành một. Trong ví dụ trên, số 3 xuất hiện 2 lần và $3^{2}$ là bình phương hay lũy thừa bậc 2 của 3.

Tầm quan trọng thiết yếu của số nguyên tố trong lý thuyết số và toán học nói chung có được từ định lý cơ bản của số học. Định lý này phát biểu rằng bất kỳ số nguyên nào hơn 1 đều có thể được viết thành tích của một hoặc nhiều số nguyên tố. Hơn nữa, tích đó là duy nhất, vì dễ thấy trong hai phân tích nguyên tố của cùng một số, các thừa số nguyên tố luôn xuất hiện với số lần bằng nhau dù thứ tự của chúng có thể khác nhau. Do đó, mặc dù có nhiều cách khác nhau để tìm cách phân tích một số thông qua thuật toán phân tích số nguyên nhưng chúng đều phải cho cùng một kết quả. Số nguyên tố vì vậy còn được gọi là "khối gạch cơ bản" của số tự nhiên.

Một số chứng minh về tính duy nhất của phân tích nguyên tố được dựa trên bổ đề Euclid: Nếu $p$ là số nguyên tố và $p$ chia được một tích $ab$ với $a$ và $b$ là số nguyên thì $p$ cũng chia được $a$ hoặc $b$ (hoặc cả hai). Ngược lại, nếu một số $p$ có tính chất khi chia được một tích thì nó cũng chia được ít nhất một thừa số trong tích, thì $p$ phải là số nguyên tố.

Sự tồn tại vô số số nguyên tố

Bài chi tiết: Định lý Euclid

Có vô số số nguyên tố. Nói cách khác, dãy các số nguyên tố

2, 3, 5, 7, 11, 13, ...

không bao giờ kết thúc. Phát biểu trên còn được gọi là định lý Euclid theo tên của nhà toán học Hy Lạp cổ đại Euclid vì ông là người đầu tiên chứng minh được phát biểu này. Một số cách chứng minh khác về sự tồn tại vô số số nguyên tố bao gồm một chứng minh bằng giải tích của Euler, chứng minh của Goldbach dựa trên số Fermat, chứng minh của Furstenberg từ tô pô học, hay cách chứng minh đơn giản của Kummer.

Chứng minh của Euclid cho thấy rằng một tập hợp hữu hạn các số nguyên tố bất kỳ là chưa hoàn thành. Thật vậy, xét một tập hợp hữu hạn gồm các số nguyên tố $p_{1},p_{2},\ldots ,p_{n}$. Khi nhân các số đó với nhau và cộng thêm 1 thì ta được

$N=1+p_{1}\cdot p_{2}\cdots p_{n}.$

Theo định lý cơ bản của số học thì $N$ có một phân tích nguyên tố

$N=p'_{1}\cdot p'_{2}\cdots p'_{m}$

với một hoặc nhiều thừa số nguyên tố. $N$ có thể chia được hết bởi bất kỳ thừa số nào trong tích trên, nhưng lại có phần dư bằng 1 khi được chia bởi bất kỳ số nguyên tố nào trong tập hợp đã cho, nên không có thừa số nguyên tố nào của $N$ có trong tập hợp đó. Vì không tồn tại một tập hợp hữu hạn nào chứa tất cả các số nguyên tố nên phải có vô số số nguyên tố.

Các số được tạo ra khi cộng thêm 1 vào tích của các số nguyên tố nhỏ nhất được gọi là số Euclid. Năm số Euclid đầu tiên là số nguyên tố, nhưng số Euclid thứ sáu,

$1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,$

là hợp số.

Công thức số nguyên tố

Bài chi tiết: Công thức số nguyên tố

Không có công thức số nguyên tố hiệu quả nào được biết đến. Chẳng hạn, không có đa thức khác hằng số nào, kể cả đa thức đa biến, chỉ cho duy nhất các giá trị nguyên tố. Tuy nhiên, có một số biểu thức có thể tạo ra các giá trị nguyên tố, nhưng hiệu quả hoạt động khá thấp. Một công thức như thế được dựa trên định lý Wilson và có thể cho giá trị 2 nhiều lần, các giá trị nguyên tố khác đúng một lần. Một hệ phương trình Diophantine gồm 9 biến và một tham số cũng tồn tại với tính chất: tham số đó là số nguyên tố khi và chỉ khi hệ phương trình thu được có một nghiệm trên tập hợp số tự nhiên. Tính chất đó có thể được dùng để suy ra một công thức với tính chất là tất cả các giá trị dương của nó đều là số nguyên tố.

Hai công thức số nguyên tố khác đến từ định lý Mills và một định lý của Wright, cho rằng tồn tại hằng số thực $A>1$ và $\mu$ sao cho giá trị của

$\left\lfloor A^{3^{n}}\right\rfloor {\text{ và }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor$

là số nguyên tố với mọi số tự nhiên $n$ bất kỳ ở công thức thứ nhất và bất kỳ số lũy thừa nào trong công thức thứ hai. Ở đây $\lfloor {}\cdot {}\rfloor$ là hàm sàn, số lớn nhất nhỏ hơn hoặc bằng với số được xét. Tuy nhiên, các công thức này không hữu ích vì cần phải tạo ra các số nguyên tố trước tiên để tính $A$ hoặc $\mu$.

Các bài toán mở

Đã có nhiều giả thuyết được đặt ra liên quan đến số nguyên tố, và đa số giả thuyết như vậy không được chứng minh trong nhiều thập kỷ: cả bốn bài toán của Landau từ năm 1912 vẫn chưa có lời giải. Một trong số đó là giả thuyết Goldbach cho rằng mọi số nguyên tố chẵn $n$ lớn hơn 2 có thể được viết thành tổng của hai số nguyên tố. Tính đến năm 2014, giả thuyết này đã được xác nhận là đúng với các số lớn đến $n=4\cdot 10^{18}$. Một số giả thuyết tương tự như vậy đã được chúng minh, chẳng hạn, định lý Vinogradov cho rằng một số nguyên lẻ đủ lớn có thể được viết thành tổng của ba số nguyên tố. Còn theo định lý Chen, một số nguyên tố chẵn đủ lớn có thể được biểu diễn thành tổng của một số nguyên tố và một số nửa nguyên tố (tích của hai số nguyên tố). Đồng thời, một số nguyên chẵn lớn hơn 10 có thể được viết thành tổng của 6 số nguyên tố. Nhánh của lý thuyết số nghiên cứu những bài toán như thế được gọi là lý thuyết cộng tính số.

Một dạng bài toán khác có liên quan đến khoảng cách nguyên tố, tức là chênh lệch giữa hai số nguyên tố liên tiếp. Có thể thấy được sự tồn tại của các khoảng cách nguyên tố lớn tùy ý bằng cách chú ý rằng dãy số $n!+2,n!+3,\dots ,n!+n$ chứa $n-1$ hợp số với $n$ là số tự nhiên. Tuy nhiên, khoảng cách nguyên tố lớn này bắt đầu xuất hiện sớm hơn so với thời điểm mà lập luận này đã cho. Chẳng hạn, khoảng cách nguyên tố đầu tiên với độ dài bằng 8 nằm giữa hai số 89 và 97, nhỏ hơn nhiều so với $8!=40320$. Có giả thuyết cho rằng có vô số cặp số nguyên tố sinh đôi, tức là cặp số nguyên tố với chênh lệch bằng 2; đó chính là giả thuyết số nguyên tố sinh đôi. Giả thuyết Polignac phát biểu tổng quát hơn rằng với một số nguyên dương $k$ bất kỳ, tồn tại vô số các cặp số nguyên tố liên tiếp sai khác nhau $2k$. Giả thuyết Andrica, giả thuyết Brocard, giả thuyết Legendre và giả thuyết Oppermann đều cho rằng khoảng cách lớn nhất giữa các số nguyên tố từ 1 đến $n$ phải là xấp xỉ ${\sqrt {n}}$, một kết quả được cho là suy ra từ giả thuyết Riemann, trong khi giả thuyết Cramér đặt khoảng cách lớn nhất đó bằng $O((\log n)^{2})$. Khoảng cách nguyên tố có thể được khái quát hóa thành bộ $k$ số nguyên tố, một bộ gồm khoảng cách giữa nhiều hơn hai số nguyên tố. Tính vô hạn và mật độ của chúng là vấn đề chính trong giả thuyết Hardy–Littlewood đầu tiên, vốn có thể được suy ra từ thuật giải heuristic rằng số nguyên tố có tính chất tương tự như một dãy số ngẫu nhiên với mật độ được cho bởi định lý số nguyên tố.

Tính chất trong giải tích

Lý thuyết số giải tích nghiên cứu lý thuyết số qua các khái niệm hàm số liên tục, giới hạn, chuỗi vô hạn và các khái niệm liên quan đến vô hạn và số nhỏ vô hạn.

Leonhard Euler là người đầu tiên khởi xướng ra ngành nghiên cứu này với thành tựu quan trọng đầu tiên là lời giải cho bài toán Basel. Bài toán yêu cầu tìm giá trị của tổng vô hạn $1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots$ mà ngày nay được công nhận là giá trị $\zeta (2)$ của hàm zeta Riemann. Hàm này có liên hệ mật thiết với số nguyên tố và giả thuyết Riemann, một trong những bài toán chưa được giải có ý nghĩa quan trọng nhất trong toán học. Euler chứng minh được rằng $\zeta (2)=\pi ^{2}/6$. Nghịch đảo của số đó, $6/\pi ^{2}$, là giới hạn của xác suất để hai số được chọn ngẫu nhiên từ một khoảng giá trị lớn là hai số nguyên tố cùng nhau (không có thừa số chung nào).

Sự phân phối các số nguyên tố trong khoảng giá trị lớn đó, chẳng hạn như có bao nhiêu số nguyên tố nhỏ hơn một số lớn cho trước, được mô tả bởi định lý số nguyên tố, nhưng không có công thức cho số nguyên tố thứ $n$ được biết đến. Ở dạng cơ bản nhất, định lý Dirichlet về cấp số cộng phát biểu rằng đa thức tuyến tính

$p(n)=a+bn$

với $a$ và $b$ nguyên tố cùng nhau cho vô số các giá trị nguyên tố. Dạng chặt chẽ hơn của định lý phát biểu rằng tổng của nghịch đảo các giá trị nguyên tố đó phân kỳ, và các đa thức tuyến tính khác nhau với $b$ bằng nhau có tỷ lệ số nguyên tố gần như nhau. Mặc dù đã có nhiều giả thuyết được đặt ra về tỷ lệ số nguyên tố trong các đa thức bậc cao nhưng chúng vẫn chưa được chứng minh, và không rõ có tồn tại một đa thức bậc hai nào có thể luôn cho các giá trị nguyên tố một cách thường xuyên hơn hay không.

Chứng minh định lý Euclid bằng giải tích

Chứng minh của Euler về sự tồn tại vô số số nguyên tố xét tổng nghịch đảo các số nguyên tố

${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.$

Euler chứng minh được rằng với một số thực $x$ bất kỳ, tồn tại một số nguyên tố $p$ sao cho tổng trên lớn hơn $x$. Nếu chỉ có một số hữu hạn các số nguyên tố thì tổng này phải đạt giá trị lớn nhất tại số nguyên tố lớn nhất thay vì tăng dần qua các giá trị của $x$, do đó có vô số số nguyên tố. Tốc độ gia tăng giá trị của tổng này được mô tả rõ hơn trong định lý thứ hai của Mertens. Để so sánh, tổng

${\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}$

không tăng đến vô hạn khi $n$ tiến đến vô hạn (xem bài toán Basel). Trong trường hợp này, số nguyên tố xuất hiện thường xuyên hơn so với bình phuơng các số tự nhiên, mặc dù cả hai tập hợp đều là vô hạn. Định lý Brun phát biểu rằng tổng nghịch đảo các số nguyên tố sinh đôi

$\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots$

là hữu hạn. Do định lý này nên không thể áp dụng cách của Euler để chứng minh giả thuyết số nguyên tố sinh đôi rằng có vô số cặp số nguyên tố sinh đôi.

Số lượng số nguyên tố nằm dưới một số cho trước

Bài chi tiết: Định lý số nguyên tố và Hàm đếm số nguyên tố

Sai số tuơng đối của ${\frac {n}{\log n}}$ và tích phân logarit $\operatorname {Li} (n)$, hai xấp xỉ của hàm đếm số nguyên tố. Cả hai sai số tuơng đối đều giảm dần về 0 khi $n$ tăng dần, nhưng tốc độ giảm này nhanh hơn nhiều đối với tích phân logarit.

Hàm đếm số nguyên tố $\pi (n)$ được định nghĩa là số lượng số nguyên tố không lớn hơn $n$. Ví dụ, $\pi (11)=5$, nghĩa là có 5 số nguyên tố nhỏ hơn hoặc bằng 11. Có một số phuơng pháp để tính giá trị chính xác của $\pi (n)$ nhanh hơn so với khi liệt kê tất cả các số nguyên tố lớn đến $n$, chẳng hạn như thuật toán Meissel–Lehmer. Định lý số nguyên tố phát biểu rằng $\pi (n)$ tiệm cận với $n/\log n$ hay

$\pi (n)\sim {\frac {n}{\log n}},$

nghĩa là tỷ số giữa $\pi (n)$ và phân số ở vế phải tiến về 1 khi $n$ tăng đến vô hạn. Kéo theo đó, xác suất để một số nhỏ hơn $n$ được chọn ngẫu nhiên là số nguyên tố tỷ lệ nghịch với số chữ số của $n$. Đồng thời, số nguyên tố thứ $n$ tỷ lệ thuận với $n\log n$ và độ dài trung bình của khoảng cách nguyên tố tỷ lệ thuận với $\log n$. Một xấp xỉ chính xác hơn của $\pi (n)$ được cho bởi tích phân logarit bù

$\pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.$

Cấp số cộng

Cấp số cộng là một dãy số hữu hạn hoặc vô hạn sao cho các số liên tiếp trong dãy đều có chênh lệch bằng nhau. Chênh lệch đó được gọi là mô đun (công sai) của cấp số cộng. Ví dụ,

3, 12, 21, 30, 39, ...

là cấp số cộng vô hạn với mô đun bằng 9. Trong một cấp số cộng, phép chia của tất cả các số cho mô đun đều cho số dư bằng nhau; trong ví dụ trên, số dư đó bằng 3. Vì cả mô đun 9 và số dư 3 đều là bội của 3 nên các phần tử khác trong dãy cũng vậy. Do đó, cấp số cộng đã cho chỉ chứa một số duy nhất, đó chính là số 3. Tổng quát, cấp số cộng vô hạn

$a,a+q,a+2q,a+3q,\dots$

có thể chứa nhiều hơn một số nguyên tố chỉ khi số dư $a$ và mô đun $q$ nguyên tố cùng nhau. Khi đó, theo định lý Dirichlet về cấp số cộng, cấp số cộng đó chứa vô số số nguyên tố.

Số nguyên tố trong cấp số cộng mô đun 9. Mỗi hàng trong thanh nhỏ nằm ngang chỉ một trong chín cấp số cộng mod 9 khác nhau, trong đó số nguyên tố được đánh dấu màu đỏ. Cấp số cộng 0, 3 hoặc 6 mod 9 chỉ chứa nhiều nhất một số nguyên tố (số 3); các cấp số cộng còn lại là 2, 4, 5, 7 và 8 mod 9 chứa vô số số nguyên tố với số lượng số nguyên tố như nhau trong mỗi cấp số cộng

Định lý Green–Tao cho thấy tồn tại các cấp số cộng hữu hạn dài tùy ý chỉ chứa các số nguyên tố.

Giá trị nguyên tố của đa thức bậc hai

Xoắn Ulam. Các số nguyên tố (màu đỏ) tập trung ở một số đường chéo nhất định. Các giá trị nguyên tố của $4n^{2}-2n+41$ được tô màu xanh.

Euler nhận thấy rằng hàm

$n^{2}-n+41$

cho giá trị là số nguyên tố với $1\leq n\leq 40$, mặc dù các giá trị hợp số bắt đầu xuất hiện khi $n$ lớn hơn 40. Việc tìm ra giải thích cho hiện tượng này chính là tiền đề của lý thuyết số đại số với số Heegner và bài toán lớp số. Giả thuyết F của Hardy–Littlewood dự đoán mật độ số nguyên tố trong các giá trị của đa thức bậc hai với hệ số nguyên về mặt tích phân logarit và hệ số của đa thức. Không có đa thức bậc hai nào được chứng minh là chỉ cho các giá trị nguyên tố.

Xoắn Ulam sắp xếp các số tự nhiên thành một mặt phẳng hai chiều, xoắn ở các hình vuông đồng tâm quanh điểm gốc với sồ nguyên tố được đánh dấu. Dễ thấy trong ví dụ này, các số nguyên tố chỉ tập trung ở một số đường chéo nhất định, ngụ ý rằng có một số đa thức bậc hai cho giá trị nguyên tố thường xuyên hơn các đa thức khác.

Hàm zeta và giả thuyết Riemann

Bài chi tiết: Giả thuyết Riemann

Đồ thị giá trị tuyệt đối của hàm zeta

Giả thuyết Riemann (1859) là một trong những bài toán chưa được giải nổi tiếng nhất toán học và một là trong bảy bài toán thiên niên kỷ, yêu cầu tìm các nghiệm số của hàm zeta Riemann $\zeta (s)$. Hàm này là một hàm giải tích trên tập số phức. Với số phức $s$ có phần thực lớn hơn 1, nó bằng một tổng vô hạn trên tất cả số nguyên và một tích vô hạn trên tất cả số nguyên tố:

$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ nguyên tố}}}{\frac {1}{1-p^{-s}}}.$

Sự bằng nhau này giữa một tổng và một tích (do Euler tìm ra) được gọi là tích Euler. Tích Euler có thể được suy ra từ định lý cơ bản của số học và cho thấy sự liên hệ giữa hàm zeta và số nguyên tố. Nó dẫn đến một cách chứng minh khác về sự tồn tại vô số số nguyên tố: nếu chỉ có một số hữu hạn số nguyên tố thì dấu bằng giữa tổng và tích cũng xảy ra tại $s=1$ nhưng tổng có tính phân kỳ (đó chính là chuỗi điều hòa $1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots$) trong khi tích có tính hội tụ (mang giá trị hữu hạn), mâu thuẫn.

Giả thuyết Riemann phát biểu rằng nghiệm số của hàm zeta là tất cả các số âm chẵn hoặc các số phức với phần thực bằng 1/2. Chứng minh ban đầu của định lý số nguyên tố được dựa trên dạng không chặt chẽ của giả thuyết này cho rằng không có nghiệm số nào có phần thực bằng 1, mặc dù còn có thêm một số cách chứng minh cơ bản khác. Hàm đếm số nguyên tố có thể được biểu diễn bởi công thức tường minh của Riemann thành một tổng mà trong đó, mỗi số hạng đến từ một nghiệm số của hàm zeta: số hạng chính của tổng là tích phân logarit và các số hạng còn lại làm cho giá trị của tổng dao động quanh số hạng chính đó. Trong trường hợp này, các nghiệm số làm ảnh hưởng đến sự phân phối các số nguyên tố như thế nào. Nếu giả thuyết Riemann là đúng, độ dao động đó sẽ nhỏ lại và sự phân phối tiệm cận các số nguyên tố được cho bởi định lý số nguyên tố cũng đúng trên các khoảng nhỏ hơn rất nhiều (có độ dài gần bằng căn bậc hai của $x$ đối với khoảng nằm gần một số $x$).

Bảng số nguyên tố-sàng Eratosthene

Sàng Eratosthene

Bài chi tiết: Sàng Eratosthenes

Hình minh họa cho thấy thuật toán đơn giản để tìm số nguyên tố và các bội số
Các số tô màu giống nhau là cùng một họ mà dẫn đầu (đậm hơn) sẽ là số nguyên tố

Sàng Eratosthenes là một giải thuật cổ xưa để lập bảng tất cả các số nguyên tố nhỏ hơn một số $n$ cho trước. Giải thuật dựa trên tính chất: mọi hợp số $n$ đều có ước nguyên tố không vượt quá căn của chính nó (${\sqrt {n}}$). Giải thuật đầu tiên xóa số 1 ra khỏi tập các số nguyên tố. Số tiếp theo số 1 là số 2, là số nguyên tố. Bắt đầu từ số 2 xoá tất cả các bội của 2 ra khỏi bảng. Số đầu tiên không bị xoá sau số 2 (số 3) là số nguyên tố. Tiếp theo lại xoá các bội của 3... Giải thuật tiếp tục cho đến khi găp số nguyên tố lớn hơn hoặc bằng sqrt(n) thì dừng lại. Tất cả các số chưa bị xoá là số nguyên tố. Theo ngôn ngữ thuật toán ta có thể diễn đạt giải thuật sàng Eratosthene như sau:

Eratosthene(n) 
Var List Prime[1..n] 
Int i,j,k 
for i:=1 to n Prime[i]:=True
Prime[1]:=false
k=0
while k < sqrt(n) {
i=k+1
while Prime[i]=False i:=i+1
k=i
j=2
while k*j<=n { 
Prime[k*j]:= False
j:=j+1
}
} 

Xem thêm

• Số tự nhiên
• Số chẵn
• Số lẻ
• Số nguyên
• Phân tích số nguyên (ra thừa số nguyên tố)
• Phân số
• Số vô tỷ
• Số hữu tỷ
• Số phức
• Số nguyên Gauss
• Số nguyên Eisenstein
• Số vô tỷ Quadratic
• Căn của đơn vị
• Gaussian period
• Số Pisot-Vijayaraghavan
• Số Salem

Liên kết ngoài

Tiếng Anh:

• Prime (number) tại Encyclopædia Britannica (tiếng Anh)
• Trang web số nguyên tố
• Lịch sử nghiên cứu số nguyên tố
• Prime Number Generator - Generate a given number of primes above a given start number.
• 15, 000, 000 số nguyên tố đầu tiên
• The prime puzzles
• Phiên bản tiếng Anh của định lý Euclid về giới hạn số nguyên tố
• Số nguyên tố trên WIMS
• Vòng số với họa tiết tạo bởi phân bố số nguyên tố
• An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier
• Factorizer Windows software to find prime numbers and pairs of prime numbers less than 2.147.483.646.
• A fast, downloadable prime number calculator written in Visual Basic 6
• Số nguyên tố tại trang PlanetMath.org.
• Weisstein, Eric W., "Prime Number" từ MathWorld.

(tiếng Việt)

• Bảng số nguyên tố tại Từ điển bách khoa Việt Nam