Số nguyên tố
Lịch sử

Cuộn giấy Rhind (từ khoảng năm 1550 trước Công nguyên) có chứa các khai triển phân số Ai Cập 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 lưu lại sớm nhất đến từ toán học Hy Lạp cổ đại. 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  (n-1)!+1. Ông cũng phỏng đoán rằng tất cả số hoàn thiện chẵn đều có thể được tạo ra từ số Mersenne theo cách xây dựng của Euclid, nhưng không chứng minh được. 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 số 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ả phép chia thử để kiểm tra tính nguyên tố chỉ bằng việc kiểm tra các ước số 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 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 phươ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 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. Một hệ quả yếu hơn từ kết quả về mật độ số nguyên tố nói trên là định đề Bertrand rằng với một số nguyên  n>1 bất kỳ thì tồn tại một số nguyên tố nằm giữa  n và  2n, được Pafnuty Chebyshev chứng minh vào năm 1852. Ý tưởng của Bernhard Riemann trong bài báo năm 1859 về hàm zeta của mình đã 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 cươ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 đị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 ra 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 tồn tại các cấp số cộng dài bất kỳ chỉ chứa số nguyên tố, và chứng minh của Yitang Zhang năm 2013 rằng tồn tại vô số khoảng cách số nguyên tố với kích thước giới hạn.