Xem mã nguồn của Số nguyên tố

[[Tập tin:Primes-vs-composites vi.svg|thế=Groups of two to twelve dots, showing that the composite numbers of dots (4, 6, 8, 9, 10, and 12) can be arranged into rectangles but the prime numbers cannot|nhỏ| 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 (toán học)|tích]] của hai số tự nhiên nhỏ hơn chính nó. Nói cách khác, số nguyên tố là những số chỉ có đúng hai [[Chia hết|ước số]] là 1 và chính nó. Các 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 (toán học)|tích]], {{Nowrap|1 × 5}} hoặc {{Nowrap|5 × 1}}, có một thừa số là chính số 5. Tuy nhiên, 6 là hợp số vì nó là tích của hai số ({{Nowrap|2 × 3}}) mà cả hai số đều nhỏ hơn 6. 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 số nguyên|phân tích ra thừa 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 nguyên tố của một số đượ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ố <math>n</math>, được gọi là [[chia thử|giải thuật chia thử]], kiểm tra xem <math>n</math> có phải là bội số của bất kỳ số nguyên nào giữa 2 và <math>\sqrt{n}</math> hay không. Một số thuật toán khác bao gồm [[Kiểm tra Miller-Rabin|phép kiểm tra Miller–Rabin]], tuy nhanh nhưng có xác suất nhỏ cho kết quả sai và [[phép kiểm tra tính nguyên tố AKS]], vốn luôn cho lời giả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]]. Đến nay, số nguyên tố lớn nhất đã biết là một số nguyên tố Mersenne có 41.024.320 chữ số, được khám phá vào tháng 10 năm 2024.<ref name="GIMPS-2024">{{chú thích web|url=https://www.mersenne.org/primes/?press=M136279841|title=GIMPS Project Discovers Largest Known Prime Number: 2<sup>136,279,841</sup>-1|tác giả=|họ=|tên=|date=2024-10-21|work=Mersenne Research, Inc.|url lưu trữ=https://web.archive.org/web/20181221183807/https://www.mersenne.org/primes/?press=M136279841|ngày lưu trữ=2024-10-21|url hỏng=không|access-date = 2024-10-21}}</ref><ref>{{Cite journal |last=Sparkes |first=Matthew |date=November 2, 2024 |title=Amateur sleuth finds largest known prime number with 41 million digits |url=https://www.newscientist.com/article/2452686-amateur-sleuth-finds-largest-known-prime-number-with-41-million-digits/ |journal=New Scientist |page=19 |access-date=March 14, 2025}}</ref>

Có [[Tập hợp vô hạn|vô số]] số nguyên tố, như đã [[Định lý Euclid|đượ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ó trong một khoảng giá trị lớ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 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ố [[Số nguyên tố sinh đôi|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ố tập trung vào khía cạnh [[lý thuyết số đại số|đại số]] và [[lý thuyết số giải tích|giải tích]] của các số. 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 số nguyên|phân tích]] các số nguyên lớn ra thừa số nguyên tố. Trong [[đại số trừu tượng]], còn có một số đối tượng khác có đặc điểm và tính chất giống với số nguyên tố, trong đó gồm [[phần tử nguyên tố]] và [[i-đê-an 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 khác 1. Các số lớn hơn 1 không phải là số nguyên tố được gọi là [[hợp số]].<ref name=":0">{{chú thích sách|url=https://archive.org/details/mathematicalolym1997gard|title=The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996|last=Gardiner|first=Anthony|publisher=Oxford University Press|year=1997|isbn=978-0-19-850105-3|location=|page=[https://archive.org/details/mathematicalolym1997gard/page/26 26]|pages=}}</ref> Nói cách khác, <math>n</math> là số nguyên tố nếu <math>n</math> vật không thể chia đều thành nhiều nhóm nhỏ gồm nhiều hơn một vật,<ref name=":1">{{chú thích sách|url=https://books.google.com/books?id=uy-yGVRUilMC&pg=PA62|title=Dyslexia, Dyscalculia and Mathematics: A practical guide|last=Henderson|first=Anne|publisher=Routledge|year=2014|isbn=978-1-136-63662-2|edition=2 |page=62}}</ref> hoặc <math>n</math> 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.<ref name=":2">{{chú thích sách|url=https://archive.org/details/giantgoldenbooko00adle|title=The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space|last=Adler|first=Irving|publisher=Golden Press|year=1960|isbn=|location=|page=[https://archive.org/details/giantgoldenbooko00adle/page/16 16]|pages=|oclc=6975809}}</ref> 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).<ref name=":3">{{chú thích sách|url=https://archive.org/details/barronsmathworkb00leff_0|title=Math Workbook for the SAT I|last=Leff|first=Lawrence S.|publisher=Barron's Educational Series|year=2000|isbn=978-0-7641-0768-9|location=|page=[https://archive.org/details/barronsmathworkb00leff_0/page/360 360]|pages=}}</ref> 1 không phải là số nguyên tố vì nó đã được loại trừ ra khỏi định nghĩa. {{nowrap|1=4 = 2 × 2}} và {{nowrap|1=6 = 2 × 3}} đều là hợp số.
[[Tập tin:Prime number Cuisenaire rods 7.png|nhỏ|upright=1.2|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 7]]
[[Ước số]] của một số tự nhiên <math>n</math> là các số tự nhiên có thể chia hết được <math>n</math>. Mọi số tự nhiên đều có ít nhất hai ước số là 1 và chính nó. Nếu nó còn có thêm một ước số 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 số dương là 1 và chính nó.<ref>{{chú thích sách|url=https://archive.org/details/elementarynumber00dudl_0/page/10|title=Elementary number theory|last1=Dudley|first1=Underwood|publisher=W.H. Freeman and Co.|year=1978|isbn=978-0-7167-0076-0|edition=2 |location=|page=[https://archive.org/details/elementarynumber00dudl_0/page/10 10]|pages=|contribution=Section 2: Unique factorization|contribution-url=https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA10}}</ref> Ngoài ra, còn có một cách diễn đạt khác nữa: <math>n</math> là số nguyên tố nếu nó lớn hơn 1 và không có số nào trong các số <math>2, 3, \dots, n-1</math> có thể chia hết được nó.<ref>{{chú thích sách|url=https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA113|title=Elementary Theory of Numbers|last=Sierpiński|first=Wacław|publisher=Elsevier|year=1988|isbn=978-0-08-096019-7|edition=2 |series=North-Holland Mathematical Library|volume=31|page=113|authorlink=Wacław Sierpiński}}</ref>

25 số nguyên tố đầu tiên (tất cả các số nguyên tố nhỏ hơn 100) là:<!--Do not add 1 to this list. Its exclusion from the list is addressed in the "History of prime numbers" section below.--><ref name="ziegler">{{chú thích tạp chí|last=Ziegler|first=Günter M.|authorlink=Günter M. Ziegler|date=|year=2004|title=The great prime number record races|url=|journal=Notices of the American Mathematical Society|volume=51|issue=4|pages=414–416|mr=2039814|via=}}</ref>
:[[2 (số)|2]], [[3 (số)|3]], [[5 (số)|5]], [[7 (số)|7]], [[11 (số)|11]], [[13 (số)|13]], [[17 (số)|17]], [[19 (số)|19]], [[23 (số)|23]], [[29 (số)|29]], [[31 (số)|31]], [[37 (số)|37]], [[41 (số)|41]], [[43 (số)|43]], [[47 (số)|47]], [[53 (số)|53]], [[59 (số)|59]], [[61 (số)|61]], [[67 (số)|67]], [[71 (số)|71]], [[73 (số)|73]], [[79 (số)|79]], [[83 (số)|83]], [[89 (số)|89]], [[97 (số)|97]] {{OEIS|id=A000040}}.

Không có [[số chẵn]] <math>n</math> 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 <math>2\times \frac{n}{2}</math>. Do đó, số 2 là ''số nguyên tố chẵn'' duy nhất; tất cả số nguyên tố ngoài số 2 là [[số lẻ]] và được gọi là ''số nguyên tố lẻ''.<ref>{{chú thích sách|url=https://books.google.com/books?id=4elkHwVS0eUC&pg=PA9|title=Numbers and Geometry|last=Stillwell|first=John|publisher=Springer|year=1997|isbn=978-0-387-98289-2|series=Undergraduate Texts in Mathematics|location=|page=9|pages=}}</ref> Tươ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.<ref>{{chú thích sách|url=https://archive.org/details/selectionproblem00sier|title=A Selection of Problems in the Theory of Numbers|last=Sierpiński|first=Wacław|publisher=Macmillan|year=1964|isbn=|location=New York|page=[https://archive.org/details/selectionproblem00sier/page/n37 40]|pages=|mr=0170843|authorlink=Wacław Sierpiński}}</ref>

[[Tập hợp (toán học)|Tập hợp]] các số nguyên tố được ký hiệu là <math>\mathbf{P}</math> (chữ ''P'' viết hoa, in đậm)<ref>{{chú thích sách|title=Elementary Methods in Number Theory|last=Nathanson|first=Melvyn B.|publisher=Springer|year=2000|isbn=978-0-387-22738-2|series=Graduate Texts in Mathematics|volume=195|location=|pages=|contribution=Notations and Conventions|mr=1732941|contribution-url=https://books.google.com/books?id=sE7lBwAAQBAJ&pg=PP10}}</ref> hoặc <math>\mathbb{P}</math> (chữ ''P'' viết hoa, in đậm bảng đen).<ref>{{chú thích sách|url=https://books.google.com/books?id=I433i_ZGxRsC&pg=PA44|title=The Mathematics of Infinity: A Guide to Great Ideas|last=Faticoni|first=Theodore G.|publisher=John Wiley & Sons|year=2012|isbn=978-1-118-24382-4|edition=2 |series=Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts|volume=111|page=44}}</ref>

== Lịch sử ==
[[Tập tin:Rhind Mathematical Papyrus.jpg|nhỏ|Cuộn giấy Rhind]]
[[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ố.<ref>Bruins, Evert Marie, bình duyệt trong ''Mathematical Reviews'' của {{chú thích tạp chí|last=Gillings|first=R.J.|year=1974|title=The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it?|journal=Archive for History of Exact Sciences|volume=12|issue=4|pages=291–298|doi=10.1007/BF01307175|mr=0497458}}</ref> 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ở (Euclid)|Cơ sở]]'' của [[Euclid]] (khoảng 300 TCN) có phần chứng minh [[Định lý Euclid|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]].<ref>{{chú thích web|url=https://primes.utm.edu/notes/proofs/infinite/euclids.html|title=Euclid's Proof of the Infinitude of Primes (c. 300 BC)|author=Caldwell|tên=Chris K.|ngày=|website=The Prime Pages|publisher=University of Tennessee|url lưu trữ=https://web.archive.org/web/20200524101246/https://primes.utm.edu/notes/proofs/infinite/euclids.html|ngày lưu trữ=2020-05-24|url hỏng=không|access-date = 2020-09-20}}</ref><ref name="stillwell-2010-p40">{{chú thích sách|url=https://books.google.com/books?id=V7mxZqjs5yUC&pg=PA40|title=Mathematics and Its History|last=Stillwell|first=John|publisher=Springer|year=2010|isbn=978-1-4419-6052-8|edition=3 |series=Undergraduate Texts in Mathematics|location=|page=40|pages=}}</ref> 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ố.<ref name="pomerance-sciam">{{chú thích tạp chí|last=Pomerance|first=Carl|date=December 1982|title=The Search for Prime Numbers|url=https://archive.org/details/sim_scientific-american_1982-12_247_6/page/136|journal=[[Scientific American]]|volume=247|issue=6|pages=136–147|bibcode=1982SciAm.247f.136P|doi=10.1038/scientificamerican1282-136|jstor=24966751|via=}}</ref><ref name="mollin">{{chú thích tạp chí|last=Mollin|first=Richard A.|year=2002|title=A brief history of factoring and primality testing B. C. (before computers)|url=https://archive.org/details/sim_mathematics-magazine_2002-02_75_1/page/18|journal=Mathematics Magazine|volume=75|issue=1|pages=18–29|doi=10.2307/3219180|jstor=3219180|mr=2107288}}</ref>

Khoảng năm 1000, nhà [[Toán học Hồi giáo Trung Cổ|toán học Hồi giáo]] [[Alhazen|Ibn al-Haytham]] (Alhazen) tìm ra [[định lý Wilson]], xác định số nguyên tố là các số <math>n</math> chia hết <math>(n-1)!+1</math>. Ô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.<ref>{{chú thích web|last1=O'Connor|first1=John J.|last2=Robertson|first2=Edmund F.|authorlink2=Edmund F. Robertson|title=Abu Ali al-Hasan ibn al-Haytham|url=http://mathshistory.st-andrews.ac.uk/Biographies/Al-Haytham.html|website=[[Bộ lưu trữ lịch sử toán học MacTutor]]|publisher=[[Đại học St. Andrews]]|archive-url=https://web.archive.org/web/20201219031116/https://mathshistory.st-andrews.ac.uk/Biographies/Al-Haytham/|archive-date=2020-12-19|url-status=live|access-date = ngày 10 tháng 3 năm 2021}}</ref> 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.<ref name="mollin" />

Năm 1640, [[Pierre de Fermat]] phát biểu [[định lý nhỏ Fermat]] (về sau được [[Gottfried Leibniz|Leibniz]] và [[Leonhard Euler|Euler]] chứng minh).<ref>{{chú thích sách|chapter-url=https://books.google.com/books?id=sohHs7ExOsYC&pg=PA45&redir_esc=y#v=onepage&q&f=false|title=How Euler Did It|last=Sandifer|first=C. Edward|publisher=Mathematical Association of America|year=2007|isbn=978-0-88385-563-8|series=MAA Spectrum|location=|page=45|chapter=8. Fermat's Little Theorem (November 2003)|url=https://books.google.com/books?id=sohHs7ExOsYC&hl=vi&source=gbs_navlinks_s}}</ref> Fermat cũng đã nghiên cứu và kiểm tra tính nguyên tố của [[số Fermat]] <math>2^{2^n}+1</math>,<ref>{{chú thích sách|url=https://books.google.com/books?id=3c6iBQAAQBAJ&pg=PA42|title=How Euler Did Even More|last=Sandifer|first=C. Edward|publisher=Mathematical Association of America|year=2014|isbn=978-0-88385-584-3|page=42}}</ref> và [[Marin Mersenne]] nghiên cứu [[số nguyên tố Mersenne]], số nguyên tố có dạng <math>2^p-1</math> với <math>p</math> cũng là số nguyên tố.<ref>{{chú thích sách|url=https://books.google.com/books?id=-9pg-4Pa19IC&pg=PA369|title=Elementary Number Theory with Applications|last=Koshy|first=Thomas|publisher=Academic Press|year=2002|isbn=978-0-12-421171-1|page=369}}</ref> 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ố.<ref>{{chú thích sách|url=https://books.google.com/books?id=g4jVCgAAQBAJ&pg=PA21|title=Goldbach Conjecture|last=Yuan|first=Wang|publisher=World Scientific|year=2002|isbn=978-981-4487-52-8|edition=2 |series=Series In Pure Mathematics|volume=4|page=21}}</ref> 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.<ref name="stillwell-2010-p40" /> Ô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ố]] <math>\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\tfrac{1}{11}+\cdots</math>.<ref>{{chú thích sách|title=The Development of Prime Number Theory: From Euclid to Hardy and Littlewood|last=Narkiewicz|first=Wladyslaw|publisher=Springer|year=2000|isbn=978-3-540-66289-1|series=Springer Monographs in Mathematics|page=11|contribution=1.2 Sum of Reciprocals of Primes|contribution-url=https://books.google.com/books?id=VVr3EuiHU0YC&pg=PA11}}</ref> Đầu thế kỷ 19, [[Adrien-Marie Legendre|Legendre]] và [[Carl Friedrich Gauß|Gauss]] đưa ra phỏng đoán rằng khi <math>x</math> tiến về [[Vô tận|vô hạn]] thì số lượng số nguyên tố nhỏ hơn hoặc bằng <math>x</math> [[Tiệm cận (giải tích)|tiệm cận]] về <math>x/\log x</math> với <math>\log x</math> là [[logarit tự nhiên]] của <math>x</math>. 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 <math>n > 1</math> bất kỳ thì tồn tại một số nguyên tố nằm giữa <math>n</math> và <math>2n</math>, được [[Pafnuty Chebyshev]] chứng minh vào năm 1852.<ref>{{chú thích tạp chí|first=P. |last=Tchebychev |author-link=Pafnuty Chebyshev |title=Mémoire sur les nombres premiers. |journal=Journal de mathématiques pures et appliquées |series=Série 1 |year=1852 |pages=366–390 |url=http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf |language=fr}} (Phần chứng minh định đề: 371–382). Xem thêm ''[https://archive.org/details/mmoiresprsentsla07impe/ Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg]'', tập 7, [https://archive.org/details/mmoiresprsentsla07impe/page/n27/mode/2up tr. 15–33], 1854</ref> Ý tưởng của [[Bernhard Riemann]] trong [[Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse|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 [[Jacques Hadamard|Hadamard]] và [[Charles Jean de la Vallée Poussin|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ố]].<ref>{{chú thích sách|title=Number Theory|last=Apostol|first=Tom M.|publisher=Birkhäuser|year=2000|isbn=|editor1-last=Bambah|editor1-first=R.P.|series=Trends in Mathematics|location=Basel|pages=1–14|contribution=A centennial history of the prime number theorem|mr=1764793|editor2-last=Dumir|editor2-first=V.C.|editor3-last=Hans-Gill|editor3-first=R.J.|contribution-url=https://books.google.com/books?id=aiDyBwAAQBAJ&pg=PA1}}</ref> 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ố.<ref>{{chú thích sách|title=Introduction to Analytic Number Theory|last=Apostol|first=Tom M.|publisher=Springer-Verlag|year=1976|isbn=|location=New York; Heidelberg|pages=146–156|contribution=7. Dirichlet's Theorem on Primes in Arithmetical Progressions|mr=0434929|contribution-url=https://books.google.com/books?id=3yoBCAAAQBAJ&pg=PA146}}</ref>

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),<ref>{{chú thích sách|url=https://books.google.com/books?id=XcDqCAAAQBAJ&pg=PA261|title=A History of Algorithms: From the Pebble to the Microchip|last=Chabert|first=Jean-Luc|publisher=Springer|year=2012|isbn=978-3-642-18192-4|page=261}}</ref> [[Kiểm tra Proth|định lý Proth]] (khoảng 1878),<ref>{{chú thích sách|title=Elementary Number Theory and Its Applications|last=Rosen|first=Kenneth H.|publisher=Addison-Wesley|year=2000|isbn=978-0-201-87073-2|edition=4 |page=342|contribution=Theorem 9.20. Proth's Primality Test}}</ref> [[Kiểm tra Lucas-Lehmer|kiểm tra Lucas–Lehmer]] (1856) và dạng tổng quát của nó, [[kiểm tra Lucas]].<ref name="mollin" />

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]].{{efn|Một số nguyên tố có 44 chữ số do Aimé Ferrier tìm ra vào năm 1951 đến nay vẫn là số nguyên tố lớn nhất được tìm thấy mà không có sự hỗ trợ của máy tính điện tử.<ref>{{chú thích sách|title=The Once and Future Turing|first1=S. Barry|last1=Cooper|first2=Andrew|last2=Hodges|publisher=Cambridge University Press|year=2016|isbn=978-1-107-01083-3|pages=37–38|url=https://books.google.com/books?id=h12cCwAAQBAJ&pg=PA37}}</ref>}} 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.<ref name="ziegler" /><ref>{{harvnb|Rosen|2000|p=245}}</ref> Quan niệm rằng số nguyên tố ít được ứng dụng ngoài [[toán học thuần túy]]{{efn|Chẳng hạn, Beiler viết rằng nhà lý thuyết số [[Ernst Kummer]] thích [[số i-đê-an]], một loại số có liên hệ gần với số nguyên tố do ông phát triển, "vì chúng không tự làm bẩn chính mình với bất kỳ ứng dụng thực tế nào",<ref>{{chú thích sách|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|first=Albert H.|last=Beiler|year=1999|publisher=Dover|orig-year=1966|isbn=978-0-486-21096-4|page=2|url=https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA2|oclc=444171535}}</ref> và Katz viết rằng [[Edmund Landau]], người được biết đến với công trình về sự phân phối các số nguyên tố, "không thích ứng dụng thực tế của toán học", và vì lý do đó nên ông tránh một số chủ đề như [[hình học]], vốn đã được xem là có ích trong thực tiễn.<ref>{{chú thích tạp chí | last = Katz | first = Shaul | doi = 10.1017/S0269889704000092 | issue = 1–2 | journal = Science in Context | mr = 2089305 | pages = 199–234 | title = Berlin roots&nbsp;– Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem | volume = 17 | year = 2004}}</ref>|name="pure"}} đã 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 (mã hóa)|RSA]] được phát minh dựa trên số nguyên tố.<ref name="ent-7">{{chú thích sách|url=https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA7|title=Elementary Number Theory|last1=Kraft|first1=James S.|last2=Washington|first2=Lawrence C.|publisher=CRC Press|year=2014|isbn=978-1-4987-0269-0|series=Textbooks in mathematics|page=7}}</ref>

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.<ref name="pomerance-sciam" /><ref>{{chú thích sách|url=https://books.google.com/books?id=EBkEGAOlCDsC&pg=PA468|title=Secret History: The Story of Cryptology|last=Bauer|first=Craig P.|publisher=CRC Press|year=2013|isbn=978-1-4665-6186-1|series=Discrete Mathematics and Its Applications|page=468}}</ref><ref>{{chú thích sách|url=https://books.google.com/books?id=tRdoIhHh3moC&pg=PA224|title=Old and New Unsolved Problems in Plane Geometry and Number Theory|last1=Klee|first1=Victor|last2=Wagon|first2=Stan|publisher=Cambridge University Press|year=1991|isbn=978-0-88385-315-3|series=Dolciani mathematical expositions|volume=11|location=|page=224|pages=}}</ref> 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.<ref name=":5">{{chú thích sách|title=Closing the Gap: The Quest to Understand Prime Numbers|last=Neale|first=Vicky|publisher=Oxford University Press|year=2017|isbn=978-0-19-109243-5|location=|pages=18, 47|at=}}</ref>

=== 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ó.<ref name="crxk-34">{{chú thích tạp chí|last1=Caldwell|first1=Chris K.|last2=Reddick|first2=Angela|last3=Xiong|first3=Yeng|last4=Keller|first4=Wilfrid|date=|year=2012|title=The history of the primality of one: a selection of sources|url=https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html|journal=Journal of Integer Sequences|volume=15|issue=9|page=Article 12.9.8|pages=|mr=3005523|via=}} Đối với những câu nói chọn lọc của các nhà toán học Hy Lạp về vấn đề này, xem tr. 3–4. Đối với các nhà toán học Hồi giáo, xem tr. 6.</ref><ref>{{chú thích sách|url=https://books.google.com/books?id=cUPXqSb7V1wC&pg=PA35|title=Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary|last=Tarán|first=Leonardo|publisher=Brill|year=1981|isbn=978-90-04-06505-5|series=Philosophia Antiqua: A Series of Monographs on Ancient Philosophy|volume=39|pages=35–38}}</ref> 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ố.<ref name="crxk-34" /> Đế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.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012|p=7–13}}. Đặc biệt xem mục về Stevin, Brancker, Wallis và Prestet.</ref> Giữa thế kỷ 18, [[Christian Goldbach]] công nhận số 1 là số nguyên tố trong thư gửi [[Leonhard Euler]],<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012|p=6–7}}</ref> nhưng Euler lại không thừa nhận như thế.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012|p=15}}</ref> Nhiều nhà toán học thế kỷ 19 vẫn cho rằng 1 là số nguyên tố<ref name="cx">{{chú thích tạp chí|last1=Caldwell|first1=Chris K.|last2=Xiong|first2=Yeng|date=|year=2012|title=What is the smallest prime?|url=https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf|journal=Journal of Integer Sequences|volume=15|issue=9|page=Article 12.9.7|pages=|mr=3005530|via=}}</ref> và [[Derrick Norman Lehmer]] cũng liệt kê số 1 trong danh sách số nguyên tố nhỏ hơn 10 triệu do ông tổng hợp và xuất bản năm 1914.<ref>{{harvnb|Conway|Guy|1996|p=130}}</ref> Các 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.<ref>{{chú thích sách|url=https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA36|title=Prime Numbers and Computer Methods for Factorization|last=Riesel|first=Hans|publisher=Birkhäuser|year=1994|isbn=978-0-8176-3743-9|edition=2 |location=Basel, Switzerland|page=36|pages=|doi=10.1007/978-1-4612-0251-6|mr=1292250}}</ref><ref name="cg-bon-129-130">{{chú thích sách|url=https://archive.org/details/bookofnumbers0000conw|title=The Book of Numbers|last1=Conway|first1=John Horton|last2=Guy|first2=Richard K.|publisher=Copernicus|year=1996|isbn=978-0-387-97993-9|location=New York|pages=[https://archive.org/details/bookofnumbers0000conw/page/129 129–130]|doi=10.1007/978-1-4612-4072-3|mr=1411676}}</ref>

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ó sẽ 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ỳ.<ref name="cx" /> Tươ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.<ref name="cg-bon-129-130" /> 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 ước số|hàm tổng các ước số]] khác nhau với số nguyên tố so với số 1.<ref>Đối với hàm phi Euler, xem {{harvnb|Sierpiński|1988}}, [https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA245 tr. 245]. Đối với hàm tổng các ước số, xem {{Harvnb|Sandifer|2007|p=59}}.</ref> Đế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 ở một thể loại đặc biệt: "[[Đơn vị (lý thuyết vành)|đơn vị]]" trong lý thuyết vành.<ref name="cx" />

== Tính chất cơ bản ==

=== Sự phân tích duy nhất ===
{{Chính|Đị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: 
:<math>\begin{align}
   34866 &= 2\cdot 3\cdot 3\cdot 13 \cdot 149\\
   &=2\cdot 3^2\cdot 13 \cdot 149.
 \end{align}</math>
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 hai lần và <math>3^2</math> là [[bình phương]] hay lũy thừa bậc hai 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''.<ref>{{chú thích sách|url=https://books.google.com/books?id=Di0HyCgDYq8C&pg=PA188|title=The Nature of Mathematics|last=Smith|first=Karl J.|publisher=Cengage Learning|year=2011|isbn=978-0-538-73758-6|edition=12 |page=188}}</ref> Định lý này phát biểu rằng bất kỳ số nguyên nào lớn 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.<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA16 mục 2, định lý 2, tr. 16]; {{harvnb|Neale|2017|p=107}}</ref> 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.<ref>{{chú thích sách|url=https://archive.org/details/musicofprimessea00dusa|title=The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics|last=du Sautoy|first=Marcus|publisher=Harper Collins|year=2003|isbn=978-0-06-093558-0|location=|page=[https://archive.org/details/musicofprimessea00dusa/page/23 23]|pages=|authorlink=Marcus du Sautoy}}</ref>

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 <math>p</math> là số nguyên tố và <math>p</math> chia hết một tích <math>ab</math> với <math>a</math> và <math>b</math> là số nguyên thì <math>p</math> cũng chia hết <math>a</math> hoặc <math>b</math> (hoặc cả hai).<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA15 mục 2, bổ đề 5, tr. 15]; {{chú thích sách|url=https://books.google.com/books?id=LeYH8P8S9oQC&pg=PA77|title=Mathematics for the Curious|last=Higgins|first=Peter M.|publisher=Oxford University Press|year=1998|isbn=978-0-19-150050-3|pages=77–78}}</ref> Ngược lại, nếu một số <math>p</math> có tính chất khi chia hết một tích thì nó cũng chia hết ít nhất một thừa số trong tích, thì <math>p</math> phải là số nguyên tố.<ref>{{chú thích sách|title=A First Course in Abstract Algebra|url=https://archive.org/details/firstcourseinabs0000rotm_e5g6|last=Rotman|first=Joseph J.|publisher=Prentice Hall|year=2000|isbn=978-0-13-011584-3|edition=2 |location=|pages=[https://archive.org/details/firstcourseinabs0000rotm_e5g6/page/56 56]|at=}}</ref>

=== Sự tồn tại vô số số nguyên tố ===
{{Chính|Định lý Euclid}}
Có [[Vô tận|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 toán học|giải tích]] của [[Leonhard Euler|Euler]], chứng minh của [[Christian Goldbach|Goldbach]] dựa trên [[số Fermat]],<ref>[http://eulerarchive.maa.org//correspondence/letters/OO0722.pdf Thư của Goldbach gửi Euler] bằng [[tiếng Latinh]] năm 1730 trong {{Chú thích sách|title=Correspondance mathématique et physique de quelques célèbres géomètres du XVIIIème siècle|last=|first=|publisher=Viện Hàn lâm Khoa học|year=1843|isbn=|editor-last=Fuss|editor-first=P. H.|location=Saint Petersbourg, Nga|pages=32–34|trans-title=Thư từ toán học và vật lý của một số nhà hình học nổi tiếng thế kỷ 18|chapter=Lettre VIII. Goldbach à Euler}}</ref> [[Chứng minh của Furstenberg về sự tồn tại vô số số nguyên tố|chứng minh từ tô pô học]] của [[Hillel Furstenberg|Furstenberg]],<ref>{{Chú thích tạp chí|last1=Furstenberg|first1=Harry|date=|year=1955|title=On the infinitude of primes|url=https://archive.org/details/sim_american-mathematical-monthly_1955-05_62_5/page/353|journal=[[American Mathematical Monthly]]|volume=62|issue=5|pages=353|doi=10.2307/2307043|jstor=2307043|mr=0068566|via=}}</ref> hay cách chứng minh đơn giản của [[Ernst Kummer|Kummer]].<ref name="Ribenboim2004">{{chú thích sách|url=https://books.google.com/books?id=SvnTBwAAQBAJ&pg=PA5|title=The little book of bigger primes|last1=Ribenboim|first1=Paulo|publisher=Springer-Verlag|year=2004|isbn=978-0-387-20169-6|location=Berlin; New York|page=4|pages=}}</ref>

[[Định lý Euclid|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.<ref>Bộ ''[[Cơ sở (Euclid)|Cơ sở]]'' của [[Euclid]], quyển 9, mệnh đề 20. Xem [https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html bản dịch tiếng Anh của David Joyce] hoặc {{chú thích sách|url=https://babel.hathitrust.org/cgi/pt?id=umn.31951000084215o;view=1up;seq=95|title=The Elements of Euclid, With Dissertations|last=Williamson|first=James|publisher=Clarendon Press|year=1782|isbn=|location=Oxford|page=63|pages=|oclc=642232959}}</ref> Thật vậy, xét một tập hợp hữu hạn gồm các số nguyên tố <math>p_1,p_2,\ldots, p_n</math>. Khi nhân các số đó với nhau và cộng thêm 1 thì ta được

: <math> N = 1 + p_1\cdot p_2\cdots p_n. </math>

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

: <math> N =  p'_1\cdot p'_2\cdots p'_m </math>

với một hoặc nhiều thừa số nguyên tố. <math>N</math> có thể được chia 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 <math>N</math> 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]].<ref>{{chú thích sách|title=Computational Recreations in Mathematica|last=Vardi|first=Ilan|publisher=Addison-Wesley|year=1991|isbn=978-0-201-52989-0|pages=82–89}}</ref> Năm số Euclid đầu tiên là số nguyên tố, nhưng số Euclid thứ sáu,

: <math>1+\big(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\big) = 30031 = 59\cdot 509,</math>

là hợp số.

=== Công thức số nguyên tố ===
{{Chính|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ố.<ref name="matiyasevich2">{{chú thích sách|title=Kvant Selecta: Algebra and Analysis|last=Matiyasevich|first=Yuri V.|publisher=[[American Mathematical Society]]|year=1999|isbn=978-0-8218-1915-9|editor1-last=Tabachnikov|editor1-first=Serge|volume=II|location=|pages=13–24|chapter=Formulas for prime numbers|chapter-url=https://books.google.com/books?id=oLKlk5o6WroC&pg=PA13}}</ref> 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.<ref>{{chú thích tạp chí|last=Mackinnon|first=Nick|date=June 1987|title=Prime number formulae|url=https://archive.org/details/sim_mathematical-gazette_1987-06_71_456/page/113|journal=[[The Mathematical Gazette]]|volume=71|issue=456|pages=113–114|doi=10.2307/3616496|jstor=3616496}}</ref> Một hệ [[Phương trình Diophantos|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ố.<ref name="matiyasevich2" />

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

: <math>\left \lfloor A^{3^n}\right \rfloor \text{ và } \left \lfloor 2^{\cdots^{2^{2^\mu}}} \right \rfloor</math>

là số nguyên tố với mọi số tự nhiên <math>n</math> 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.<ref>{{chú thích tạp chí|last=Wright|first=E.M.|date=|year=1951|title=A prime-representing function|url=https://archive.org/details/sim_american-mathematical-monthly_1951-11_58_9/page/616|journal=[[American Mathematical Monthly]]|volume=58|issue=9|pages=616–618|doi=10.2307/2306356|jstor=2306356|via=}}</ref> Ở đây <math>\lfloor {}\cdot{} \rfloor</math> là [[Phần nguyên|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 <math>A</math> hoặc <math>\mu</math>.<ref name="matiyasevich2" />

=== Các bài toán mở ===
{{Xem thêm|Thể loại:Phỏng đoán về số nguyên tố}}
Đã 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.<ref>{{Chú thích sách|url=https://books.google.com.vn/books?id=EbLzBwAAQBAJ&pg=PR7|title=Unsolved Problems in Number Theory|last=Guy|first=Richard|publisher=Springer|year=2013|isbn=978-0-387-26677-0|series=Problem Books in Mathematics|location=|pages=vii}}</ref> Một trong số đó là [[giả thuyết Goldbach]] cho rằng mọi số nguyên chẵn <math>n</math> lớn hơn 2 có thể được viết thành tổng của hai số nguyên tố.<ref>{{harvnb|Guy|2013}}, [https://books.google.com/books?id=EbLzBwAAQBAJ&pg=PA105 C1 "Goldbach conjecture", tr. 105–107]</ref> 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 <math>n=4\cdot 10^{18}</math>.<ref>{{chú thích tạp chí|last1=Oliveira e Silva|first1=Tomás|last2=Herzog|first2=Siegfried|last3=Pardi|first3=Silvio|date=|year=2014|title=Empirical verification of the even Goldbach conjecture and computation of prime gaps up to <math>4\cdot10^{18}</math>|url=|journal=Mathematics of Computation|volume=83|issue=288|pages=2033–2060|doi=10.1090/S0025-5718-2013-02787-1|mr=3194140|via=}}</ref> 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ố.<ref>{{chú thích sách|title=Poincaré's legacies, pages from year two of a mathematical blog. Part I|last=Tao|first=Terence|publisher=American Mathematical Society|year=2009|isbn=978-0-8218-4883-8|location=Providence, RI|pages=239–247|contribution=3.1 Structure and randomness in the prime numbers|mr=2523047|author-link=Terence Tao|contribution-url=https://books.google.com/books?id=NxnVAwAAQBAJ&pg=PA239}} Đặc biệt xem tr. 239.</ref> Còn theo [[định lý Chen]], một số nguyên 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ố).<ref>{{harvnb|Guy|2013|p=159}}</ref> Đồ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ố.<ref>{{chú thích tạp chí|last=Ramaré|first=Olivier|date=|year=1995|title=On Šnirel'man's constant|url=http://archive.numdam.org/article/ASNSP_1995_4_22_4_645_0.pdf|journal=Annali della Scuola Normale Superiore di Pisa|volume=22|issue=4|pages=645–706|mr=1375315|via=}}</ref> 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ố]].<ref>{{chú thích sách|url=https://books.google.com/books?id=ibwpDwAAQBAJ&pg=PP6|title=Goldbach's Problem: Selected Topics|last=Rassias|first=Michael Th.|publisher=Springer|year=2017|isbn=978-3-319-57912-2|location=Cham|page=vii|doi=10.1007/978-3-319-57914-6|mr=3674356}}</ref>

Một dạng bài toán khác có liên quan đến [[khoảng cách số 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 số nguyên tố lớn tùy ý bằng cách chú ý rằng dãy số <math>n!+2,n!+3,\dots,n!+n</math> chứa <math>n-1</math> hợp số với <math>n</math> là số tự nhiên.<ref>{{Harvnb|Koshy|2002}}, [https://books.google.com/books?id=-9pg-4Pa19IC&pg=PA109 định lý 2.14, tr. 109]. {{Harvnb|Riesel|1994}} cũng có lập luận tương tự sử dụng [[giai thừa nguyên tố]] thay vì giai thừa.</ref> Tuy nhiên, khoảng cách số 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.<ref name="riesel-gaps">{{harvnb|Riesel|1994|p=78–79}}</ref> Chẳng hạn, khoảng cách số nguyên tố đầu tiên với độ dài bằng 8 nằm giữa hai số nguyên tố 89 và 97, nhỏ hơn nhiều so với <math>8!=40320</math>.<ref>{{SloanesRef|sequencenumber=A100964|name=Smallest prime number that begins a prime gap of at least 2n}}</ref> 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à [[Số nguyên tố sinh đôi|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 <math>k</math> 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 <math>2k</math>.<ref name=":4">{{Harvnb|Ribenboim|2004}}, mục "Gaps between primes", tr. 186–192</ref> [[Giả thuyết Andrica]],<ref name=":4" /> [[giả thuyết Brocard]],<ref name="rib-183">{{harvnb|Ribenboim|2004|p=183}}</ref> [[giả thuyết Legendre]]<ref name="chan">{{chú thích tạp chí|last=Chan|first=Joel|date=February 1996|title=Prime time!|journal=Math Horizons|volume=3|issue=3|pages=23–25|doi=10.1080/10724117.1996.11974965|jstor=25678057}} Chú ý rằng Chan viết giả thuyết Legendre thành "tiên đề Sierpinski".</ref> và [[giả thuyết Oppermann]]<ref name="rib-183" /> đều cho rằng khoảng cách lớn nhất giữa các số nguyên tố từ 1 đến <math>n</math> phải là xấp xỉ <math>\sqrt{n}</math>, 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 <math>O((\log n)^2)</math>.<ref name=":4" /> Khoảng cách số nguyên tố có thể được khái quát hóa thành [[Bộ k số nguyên tố|bộ <math>k</math> số nguyên tố]], thể hiện những dãy lặp lại 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 dãy số nguyên tố hành xử 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ố.<ref>{{harvnb|Ribenboim|2004|p=201–202}}</ref>

== 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 liên tục|hàm số liên tục]], [[Giới hạn (toán học)|giới hạn]], [[Chuỗi (toán học)|chuỗi vô hạn]] và các khái niệm liên quan đến [[Vô tậ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 <math>1+\tfrac{1}{4}+\tfrac{1}{9}+\tfrac{1}{16}+\dots</math> mà ngày nay được công nhận là giá trị <math>\zeta(2)</math> 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 <math>\zeta(2)=\pi^2/6</math>.<ref>{{harvnb|Sandifer|2007|p=205–208}}</ref> Nghịch đảo của số đó, <math>6/\pi^2</math>, 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).<ref>{{chú thích sách|url=https://books.google.com/books?id=efbaDLlTXvMC&pg=PA29|title=Excursions in Number Theory|last1=Ogilvy|first1=C.S.|last2=Anderson|first2=J.T.|publisher=Dover Publications Inc.|year=1988|isbn=978-0-486-25778-5|location=|pages=29–35}}</ref>

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 số nguyên tố|công thức cho số nguyên tố thứ <math>n</math>]] đượ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
: <math>p(n) = a + bn</math>
với <math>a</math> và <math>b</math> 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 <math>b</math> 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 ===
[[Tính phân kỳ của tổng nghịch đảo các số nguyên tố|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 phép nhân|nghịch đảo]] các số nguyên tố
: <math>\frac 1 2 + \frac 1 3 + \frac 1 5 + \frac 1 7 + \cdots + \frac 1 p.</math>
Euler chứng minh được rằng với một [[số thực]] <math>x</math> bất kỳ, tồn tại một số nguyên tố <math>p</math> sao cho tổng trên lớn hơn <math>x</math>.<ref>{{harvnb|Apostol|1976}}, mục 1.6, định lý 1.13</ref> 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 <math>x</math>, 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]].<ref>{{harvnb|Apostol|1976}}, mục 4.8, định lý 4.12</ref> Để so sánh, tổng
: <math>\frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + \cdots + \frac 1 {n^2}</math>
không tăng đến vô hạn khi <math>n</math> 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 phương các số tự nhiên, mặc dù cả hai tập hợp đều là vô hạn.<ref name="mtb-invitation">{{chú thích sách|url=https://books.google.com/books?id=kLz4z8iwKiwC&pg=PA43|title=An Invitation to Modern Number Theory|last1=Miller|first1=Steven J.|last2=Takloo-Bighash|first2=Ramin|publisher=Princeton University Press|year=2006|isbn=978-0-691-12060-7|pages=43–44}}</ref> [[Định lý Brun]] phát biểu rằng tổng nghịch đảo các [[số nguyên tố sinh đôi]]
: <math> \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 </math>
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 [[Số nguyên tố sinh đôi|giả thuyết số nguyên tố sinh đôi]] rằng có vô số cặp số nguyên tố sinh đôi.<ref name="mtb-invitation" />

=== Số lượng số nguyên tố nằm dưới một số cho trước ===
{{Chính|Định lý số nguyên tố|Hàm đếm số nguyên tố}}
[[Tập tin:Prime-counting relative error vi.svg|nhỏ|upright=1.6|[[Sai số xấp xỉ|Sai số tương đối]] của <math>\frac{n}{\log n}</math> và tích phân logarit <math>\operatorname{Li}(n)</math>, hai xấp xỉ của [[hàm đếm số nguyên tố]]. Cả hai sai số tương đối đều giảm dần về 0 khi <math>n</math> 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ố]] <math>\pi(n)</math> được định nghĩa là số lượng số nguyên tố không lớn hơn <math>n</math>.<ref>{{chú thích sách|url=https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA6|title=Prime Numbers: A Computational Perspective|last1=Crandall|first1=Richard|last2=Pomerance|first2=Carl|publisher=Springer|year=2005|isbn=978-0-387-25282-7|edition=2 |location=|page=6|pages=}}</ref> Ví dụ, <math>\pi(11)=5</math>, nghĩa là có 5 số nguyên tố nhỏ hơn hoặc bằng 11. Có một số phương pháp để tính giá trị chính xác của <math>\pi(n)</math> nhanh hơn so với khi liệt kê tất cả các số nguyên tố lớn đến <math>n</math>, chẳng hạn như [[thuật toán Meissel–Lehmer]].<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=ZXjHKPS1LEAC&pg=PA152 mục 3.7, "Counting primes", tr. 152–162]</ref> Định lý số nguyên tố phát biểu rằng <math>\pi(n)</math> tiệm cận với <math>n/\log n</math> hay 
:<math>\pi(n) \sim \frac{n}{\log n},</math>
nghĩa là tỉ số giữa <math>\pi(n)</math> và phân số ở vế phải [[Giới hạn của một dãy|tiến về]] 1 khi <math>n</math> tăng đến vô hạn.<ref name="cranpom10">{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA10 tr. 10]</ref> Kéo theo đó, xác suất để một số nhỏ hơn <math>n</math> được chọn ngẫu nhiên là số nguyên tố tỉ lệ nghịch với số chữ số của <math>n</math>.<ref>{{chú thích sách|title=The Number Mysteries: A Mathematical Odyssey through Everyday Life|last=du Sautoy|first=Marcus|publisher=St. Martin's Press|year=2011|isbn=978-0-230-12028-0|pages=50–52|contribution=What are the odds that your telephone number is prime?|authorlink=Marcus du Sautoy|contribution-url=https://books.google.com/books?id=snaUbkIb8SEC&pg=PA50}}</ref> Đồng thời, số nguyên tố thứ <math>n</math> tỉ lệ thuận với <math>n\log n</math> và độ dài trung bình của khoảng cách nguyên tố tỉ lệ thuận với <math>\log n</math>.<ref name="riesel-gaps" /><ref>{{harvnb|Apostol|1976}}, mục 4.6, định lý 4.7</ref> Một xấp xỉ chính xác hơn của <math>\pi(n)</math> được cho bởi [[Hàm tích phân logarit|tích phân logarit bù]]<ref name="cranpom10" />
:<math>\pi(n)\sim \operatorname{Li}(n) = \int_2^n \frac{dt}{\log t}.</math>

=== 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.<ref>{{chú thích sách|url=https://books.google.com/books?id=Z9z7iliyFD0C&pg=PA37|title=Algebra|last1=Gelfand|first1=I.M.|last2=Shen|first2=Alexander|publisher=Springer|year=2003|isbn=978-0-8176-3677-7|page=37|author1-link=Israel Gelfand}}</ref> Chênh lệch đó được gọi là [[Số học mô đun|mô đun]] (công sai) của cấp số cộng.<ref>{{chú thích sách|url=https://books.google.com/books?id=Fsaa3MUUQYkC&pg=PA76|title=Fundamental Number Theory with Applications|last=Mollin|first=Richard A.|publisher=CRC Press|year=1997|isbn=978-0-8493-3987-5|series=Discrete Mathematics and Its Applications|page=76}}</ref> Ví dụ,

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

là cấp số cộng vô hạn với mô đun 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ố nguyên tố duy nhất, đó chính là số 3. Tổng quát, cấp số cộng vô hạn

: <math>a, a+q, a+2q, a+3q, \dots</math>

có thể chứa nhiều hơn một số nguyên tố chỉ khi số dư <math>a</math> và mô đun <math>q</math> 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ố.<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=ZXjHKPS1LEAC&pg=PA12 định lý 1.1.5, tr. 12]</ref>

{{Toàn cảnh|Prime numbers in arithmetic progression mod&nbsp;9 zoom in.png|815px|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ố.<ref name=":5" /><ref>{{chú thích tạp chí|last1=Green|first1=Ben|last2=Tao|first2=Terence|author2-link=Terence Tao|date=|year=2008|title=The primes contain arbitrarily long arithmetic progressions|url=https://archive.org/details/sim_annals-of-mathematics_2008-03_167_2/page/481|journal=Annals of Mathematics|volume=167|issue=2|pages=481–547|arxiv=math.NT/0404188|doi=10.4007/annals.2008.167.481|via=}}</ref>

=== Giá trị nguyên tố của đa thức bậc hai ===
[[Tập tin:Ulam 2.png|nhỏ|upright=1.1|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 <math>4n^2 - 2n + 41</math> được tô màu xanh.]]
Euler nhận thấy rằng hàm
: <math>n^2 - n + 41</math>
cho giá trị là số nguyên tố với <math>1\le n\le 40</math>, mặc dù các giá trị hợp số bắt đầu xuất hiện khi <math>n</math> lớn hơn 40.<ref>{{chú thích sách|title=Additive Theory of Prime Numbers|last1=Hua|first1=L.K.|publisher=American Mathematical Society|year=2009|isbn=978-0-8218-4942-2|series=Translations of Mathematical Monographs|volume=13|location=Providence, RI|pages=176–177|mr=0194404|oclc=824812353|orig-year=1965}}</ref><ref>Dãy các giá trị nguyên tố này, bắt đầu tại <math>n=1</math> thay vì <math>n=0</math>, có trong {{chú thích sách|title=103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea|last1=Lava|first1=Paolo Pietro|last2=Balzarotti|first2=Giorgio|publisher=Ulrico Hoepli Editore S.p.A.|year=2010|isbn=978-88-203-5804-4|location=|page=133|pages=|language=it|contribution=Chapter 33. Formule fortunate|contribution-url=https://books.google.com/books?id=YfsSAAAAQBAJ&pg=PA133}}</ref> 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ố]].<ref>{{chú thích sách|title=Single Digits: In Praise of Small Numbers|last=Chamberland|first=Marc|publisher=Princeton University Press|year=2015|isbn=978-1-4008-6569-7|pages=213–215|contribution=The Heegner numbers|contribution-url=https://books.google.com/books?id=n9iqBwAAQBAJ&pg=PA213}}</ref> [[Xoắn Ulam|Giả thuyết F của Hardy–Littlewood]] dự đoán mật độ số nguyên tố trong các giá trị của [[Hàm số bậc hai|đ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ố.<ref name=":6">{{Harvnb|Guy|2013|p=7–10}}</ref>

[[Xoắn Ulam]]<ref>{{Cite journal |last1=Stein |first1=M.L. |last2=Ulam |first2=S.M. |last3=Wells |first3=M.B. |date=1964 |title=A Visual Display of Some Properties of the Distribution of Primes |url=https://www.jstor.org/stable/2312588 |journal=The American Mathematical Monthly |volume=71 |issue=5 |pages=516–520 |doi=10.2307/2312588|jstor=2312588 }}</ref> 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.<ref name=":6" />

=== Hàm zeta và giả thuyết Riemann ===
{{Chính|Giả thuyết Riemann}}
[[Tập tin:Riemann zeta function absolute value vi.png|nhỏ|upright=1.5|Đồ 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 [[Không điểm của hàm số|nghiệm số]] của [[hàm zeta Riemann]] <math>\zeta(s)</math>. 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 <math>s</math> có phần thực lớn hơn 1, nó bằng một [[Chuỗi (toán học)|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ố:

: <math>\zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s}=\prod_{p \text{ nguyên tố}} \frac 1 {1-p^{-s}}.</math>

Đẳng thức 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]].<ref>{{chú thích sách|url=https://books.google.com/books?id=IdHLCgAAQBAJ&pg=PA1|title=An introduction to the theory of the Riemann zeta-function|last=Patterson|first=S.J.|publisher=Cambridge University Press, Cambridge|year=1988|isbn=978-0-521-33535-5|series=Cambridge Studies in Advanced Mathematics|volume=14|page=1|doi=10.1017/CBO9780511623707|mr=933558}}</ref> 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ố.<ref>{{chú thích sách|url=https://books.google.com/books?id=Qm1aZA-UwX4C&pg=PA10|title=The Riemann hypothesis: A resource for the afficionado and virtuoso alike|last1=Borwein|first1=Peter|last2=Choi|first2=Stephen|last3=Rooney|first3=Brendan|last4=Weirathmueller|first4=Andrea|publisher=Springer|year=2008|isbn=978-0-387-72125-5|series=CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC|location=New York|pages=10–11|doi=10.1007/978-0-387-72126-2|mr=2463715}}</ref> 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 <math>s=1</math> nhưng tổng có tính phân kỳ (đó chính là [[chuỗi điều hòa]] <math>1+\tfrac{1}{2}+\tfrac{1}{3}+\dots</math>) trong khi tích có tính hội tụ (mang giá trị hữu hạn), mâu thuẫn.<ref>{{harvnb|Sandifer|2007}}, [https://books.google.com/books?id=sohHs7ExOsYC&pg=PA191 tr. 191–193]</ref>

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.<ref>{{harvnb|Borwein|Choi|Rooney|Weirathmueller|2008}}, [https://books.google.com/books?id=Qm1aZA-UwX4C&pg=PA15 giả thuyết 2.7 (giả thuyết Riemann), tr. 15]</ref> 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,<ref>{{harvnb|Patterson|1988|p=7}}</ref><ref name="bcrw18">{{harvnb|Borwein|Choi|Rooney|Weirathmueller|2008}}, [https://books.google.com/books?id=Qm1aZA-UwX4C&pg=PA18 tr. 18]</ref> mặc dù còn có thêm một số cách chứng minh cơ bản khác.<ref>{{harvnb|Nathanson|2000}}, [https://books.google.com/books?id=sE7lBwAAQBAJ&pg=PA289 chương 9, "The prime number theorem", tr. 289–324]</ref> Hàm đếm số nguyên tố có thể được biểu diễn bởi [[Công thức tường minh cho hàm L|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 đó.<ref>{{chú thích tạp chí|last=Zagier|first=Don|date=|year=1977|title=The first 50 million prime numbers|url=|journal=The Mathematical Intelligencer|volume=1|issue=S2|pages=7–19|doi=10.1007/bf03351556|via=}} Đặc biệt xem tr. 14–16.</ref> 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ố. 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 <math>x</math> đối với khoảng nằm gần một số <math>x</math>).<ref name="bcrw18" />

== Đại số trừu tượng ==

=== Số học mô đun và trường hữu hạn ===
{{Chính|Số học mô đun}}
Số học mô đun là một dạng khác của số học thông thường chỉ dùng các số <math>\{0, 1, 2, \dots, n - 1\}</math> với một số tự nhiên <math>n</math> được gọi là mô đun. Bất kỳ số tự nhiên nào khác đều có thể được ánh xạ vào hệ thống này bằng cách thay nó bằng số dư của nó khi được chia bởi <math>n</math>.<ref>{{Harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=VG9YBQAAQBAJ&pg=PA96 mệnh đề 5.3], tr. 96</ref> Mô đun tổng, hiệu và tích được tính bằng cách thực hiện phép thế bằng số dư trong phép chia của tổng, hiệu hoặc tích các số nguyên thông thường.<ref>{{chú thích sách|url=https://books.google.com/books?id=GJwxDwAAQBAJ&pg=PA20|title=Algebra in Action: A Course in Groups, Rings, and Fields|last=Shahriari|first=Shahriar|publisher=American Mathematical Society|year=2017|isbn=978-1-4704-2849-5|series=Pure and Applied Undergraduate Texts|volume=27|pages=20–21}}</ref> Sự bằng nhau giữa các số nguyên có liên quan đến khái niệm ''đồng dư'' trong số học mô đun: <math>x</math> và <math>y</math> đồng dư (ký hiệu <math>x\equiv y\bmod{n}</math>) khi phép chia của chúng bởi <math>n</math> cho số dư bằng nhau.<ref>{{Harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA28 định lý 3, tr. 28]</ref> Tuy nhiên, trong hệ thống số đó, chỉ có thể xảy ra [[phép chia]] cho một số khác 0 khi và chỉ khi mô đun là số nguyên tố. Chẳng hạn, với mô đun 7, có thể tồn tại phép chia cho 3: <math>2/3\equiv 3\bmod{7}</math>, vì khi nhân cả hai vế cho 3 thì ta được biểu thức đúng <math>2\equiv 9\bmod{7}</math>. Nhưng với mô đun 6 (là một hợp số), không thể tồn tại phép chia cho 3: phương trình <math>2/3\equiv x\bmod{6}</math> vô nghiệm vì khi nhân cả hai vế cho 3 thì vế trái trở thành số 2 còn vế phải trở thành số 0 hoặc số 3. Trong [[đại số trừu tượng]], khả năng thực hiện phép chia có nghĩa rằng mô đun một số nguyên tố tạo thành một [[Trường (đại số)|trường]] được gọi là [[trường hữu hạn]], trong khi các mô đun khác chỉ tạo ra [[vành]].<ref>{{Harvnb|Shahriari|2017}}, [https://books.google.com/books?id=GJwxDwAAQBAJ&pg=PA27 tr. 27–28]</ref>

Bằng số học mô đun, có thể suy ra được một số định lý về số nguyên tố. Ví dụ, [[định lý nhỏ Fermat]] phát biểu rằng nếu <math>a\not\equiv 0</math> (mod <math>p</math>) thì <math>a^{p-1}\equiv 1</math> (mod <math>p</math>).<ref>{{Harvnb|Ribenboim|2004}}, "Fermat's little theorem and primitive roots modulo a prime", tr. 17–21</ref> Lấy tổng trên tất cả giá trị của <math>a</math>, ta được phương trình
: <math>\sum_{a=1}^{p-1} a^{p-1} \equiv (p-1) \cdot 1 \equiv -1 \pmod p,</math>
đúng khi <math>p</math> là số nguyên tố. [[Giả thuyết Giuga]] cho rằng phương trình này là điều kiện đủ để <math>p</math> là số nguyên tố.<ref>{{Harvnb|Ribenboim|2004}}, "The property of Giuga", tr. 21–22</ref> Theo [[định lý Wilson]], một số nguyên <math>p>1</math> là số nguyên tố khi và chỉ khi giai thừa <math>(p-1)!</math> đồng dư với –1 mod <math>p</math>. Với một hợp số<math>\;n = r\cdot s\;</math>thì định lý này không đúng, vì khi đó có một trong hai thừa số chia hết cả {{mvar|n}} và <math>(n-1)!</math> nên không thể có <math>(n-1)!\equiv -1 \pmod{n}</math>.<ref>{{Harvnb|Ribenboim|2004}}, "The theorem of Wilson", tr. 21</ref>

=== Số ''p''-adic ===
{{Chính|Số p-adic}}
[[Cấp p-adic|Cấp <math>p</math>-adic]] <math>\nu_p(n)</math> của một số nguyên <math>n</math> là số lần xuất hiện của <math>p</math> trong phân tích nguyên tố của <math>n</math>. Khái niệm này có thể được mở rộng cho số hữu tỉ: cấp <math>p</math>-adic của một phân số <math>m/n</math> được xác định là <math>\nu_p(m) - \nu_p(n)</math>. Khi đó, giá trị tuyệt đối <math>p</math>-adic <math>|q|_p</math> của một số hữu tỉ <math>q</math> là <math>|q|_p=p^{-\nu_p(q)}</math>. Khi nhân một số nguyên với giá trị tuyệt đối <math>p</math>-adic của nó thì các thừa số <math>p</math> trong phân tích nguyên tố của số nguyên đó bị khử và chỉ còn lại các thừa số nguyên tố khác. Giống như khi đo khoảng cách giữa hai số thực bằng giá trị tuyệt đối thông thường, khoảng cách giữa hai số hữu tỉ có thể được đo bằng độ dài <math>p</math>-adic, tức là giá trị tuyệt đối <math>p</math>-adic của hiệu hai số đó. Theo định nghĩa khoảng cách đó, hai số được gọi là gần nhau (có khoảng cách nhỏ) khi hiệu giữa chúng có thể chia hết bởi một lũy thừa bậc cao của <math>p</math>. Bằng cùng một cách mà số thực được tạo thành từ số hữu tỉ và khoảng cách giữa chúng cùng một số giá trị giới hạn được thêm vào để hợp lại thành một [[trường đầy đủ]], các số hữu tỉ với khoảng cách <math>p</math> có thể được mở rộng sang một trường đầy đủ khác được gọi là [[Số p-adic|số <math>p</math>-adic]].<ref name="childress">{{citation|last=Childress|first=Nancy|doi=10.1007/978-0-387-72490-4|isbn=978-0-387-72489-8|mr=2462595|pages=8–11|publisher=Springer, New York|series=Universitext|title=Class Field Theory|url=https://books.google.com/books?id=RYdy4PCJYosC&pg=PA8|year=2009}}. Xem thêm tr. 64.</ref><ref>{{chú thích sách|url=https://books.google.com/books?id=QpLwCgAAQBAJ&pg=PA200|title=Introduction to Number Theory|last1=Erickson|first1=Marty|last2=Vazzana|first2=Anthony|last3=Garth|first3=David|publisher=CRC Press|year=2016|isbn=978-1-4987-1749-6|edition=2 |series=Textbooks in Mathematics|location=Boca Raton, FL|page=200|mr=3468748}}</ref>

Các khái niệm về cấp, giá trị tuyệt đối và trường đầy đủ suy ra từ chúng có thể được khái quát hóa cho [[trường số đại số]] cùng với [[Định chuẩn (đại số)|định chuẩn]] (ánh xạ nhất định từ [[nhóm nhân]] của trường đó sang một [[Nhóm được sắp tuyến tính|nhóm cộng được sắp toàn phần]]), [[Giá trị tuyệt đối (đại số)|giá trị tuyệt đối]] (ánh xạ nhân nhất định từ một trường sang số thực),<ref name="childress" /> và place (sự mở rộng sang [[trường đầy đủ]] mà trong đó tập cho trước là một [[tập trù mật]]) của chúng.<ref>{{chú thích sách|url=https://archive.org/details/basicnumbertheor00weil_866|title=Basic Number Theory|last=Weil|first=André|publisher=Springer-Verlag|year=1995|isbn=978-3-540-58655-5|series=Classics in Mathematics|location=Berlin|page=[https://archive.org/details/basicnumbertheor00weil_866/page/n56 43]|pages=|mr=1344916}} Chú ý rằng một số tác giả như {{harvtxt|Childress|2009}} sử dụng thuật ngữ "place" để chỉ một lớp chuẩn tương đương.</ref> Chẳng hạn, sự mở rộng từ tập số hữu tỉ sang tập [[số thực]] là một place mà tại đó khoảng cách giữa hai số là [[giá trị tuyệt đối]] thông thường của hiệu hai số đó. Ánh xạ tương ứng sang một nhóm cộng là [[logarit]] của giá trị tuyệt đối đó, mặc dù nó không thỏa mãn tất cả yêu cầu của một định chuẩn. Theo [[định lý Ostrowski]], số thực và số <math>p</math>-adic cùng cấp và giá trị tuyệt đối của chúng là định chuẩn, giá trị tuyệt đối và place duy nhất trên tập số hữu tỉ xê xích theo khái niệm tự nhiên về tính tương đương.<ref name="childress" /> [[Nguyên lý Hasse]] cho phép giải nhiều bài toán trên số hữu tỉ bằng cách hợp các nghiệm từ mỗi place của chúng lại với nhau, một lần nữa nhấn mạnh tầm quan trọng của số nguyên tố trong lý thuyết số.<ref>{{chú thích sách|url=https://books.google.com/books?id=wt1sCQAAQBAJ&pg=PA136|title=Algebraic Number Theory|last=Koch|first=H.|publisher=Springer-Verlag|year=1997|isbn=978-3-540-63003-6|location=Berlin|page=136|pages=|citeseerx=|doi=10.1007/978-3-642-58095-6|mr=1474965}}</ref>

=== Phần tử nguyên tố trong vành ===
{{Chính|Phần tử nguyên tố|Phần tử tối giản}}
[[Tập tin:Gaussian primes.svg|nhỏ|[[Số nguyên tố Gauss]] với chuẩn nhỏ hơn 500]]
[[Vành giao hoán]] là một [[cấu trúc đại số]] có định nghĩa [[phép cộng]], phép trừ và [[phép nhân]]. Tập số nguyên là một vành và số nguyên tố trong tập đó đã được khái quát hóa sang lý thuyết vành với thuật ngữ ''phần tử nguyên tố'' và ''phần tử tối giản''. Một phần tử <math>p</math> của vành <math>R</math> được gọi là phần tử nguyên tố nếu nó khác 0, không có [[Nghịch đảo phép nhân|nghịch đảo]] (không phải phần tử [[Đơn vị (lý thuyết vành)|đơn vị]]) và thỏa mãn điều kiện: khi <math>p</math> chia hết tích <math>xy</math> gồm hai phần tử trong <math>R</math> thì nó cũng chia hết ít nhất một trong hai phần tử <math>x</math> và <math>y</math>. Một phần tử được gọi là phần tử tối giản nếu nó không phải phần tử đơn vị, cũng không phải là tích của hai phần tử khác phần tử đơn vị. Trong vành số nguyên, các phần tử nguyên tố và tối giản tạo thành cùng một tập hợp
: <math>\{ \dots, -11, -7, -5, -3, -2, 2, 3, 5, 7, 11, \dots \}\, .</math>
Trong một vành bất kỳ, mọi phần tử nguyên tố đều là phần tử tối giản. Phát biểu ngược lại của nó chỉ đúng trong [[miền phân tích nhân tử duy nhất]].<ref>{{chú thích sách|url=https://books.google.com/books?id=BdAbcje-TZUC&pg=PA127|title=Concrete Abstract Algebra: From numbers to Gröbner bases|last=Lauritzen|first=Niels|publisher=Cambridge University Press|year=2003|isbn=978-0-521-53410-9|location=Cambridge|page=127|doi=10.1017/CBO9780511804229|mr=2014325}}</ref>

Định lý cơ bản của số học là đúng (theo định nghĩa) trong miền phân tích nhân tử duy nhất. Ví dụ về một miền như thế là vành [[số nguyên Gauss]] <math>\mathbb{Z}[i]</math>, vành các số phức dạng <math>a+bi</math> với <math>i</math> là [[đơn vị ảo]] và <math>a</math> và <math>b</math> là số nguyên bất kỳ. Các phần tử nguyên tố của vành đó được gọi là [[số nguyên tố Gauss]]. Một số nguyên tố trong vành số nguyên có thể không phải là số nguyên tố trong vành số nguyên Gauss; chẳng hạn, số 2 có thể được viết thành tích của hai số nguyên tố Gauss <math>1+i</math> và <math>1-i</math>. Số nguyên tố hữu tỉ (phần tử nguyên tố trong vành số nguyên) đồng dư với 3 mod 4 là số nguyên tố Gauss, nhưng số nguyên tố hữu tỉ đồng dư với 1 mod 4 không phải vậy.<ref>{{harvnb|Lauritzen|2003}}, hệ quả 3.5.14, tr. 133; bổ đề 3.5.18, tr. 136</ref> Đó là một hệ quả của [[định lý Fermat về tổng của hai số chính phương]], phát biểu rằng một số nguyên tố lẻ <math>p</math> có thể được biểu diễn thành tổng của hai số chính phương, <math>p=x^2+y^2</math>, và do đó có thể được phân tích thành <math>p=(x+iy)(x-iy)</math>, chỉ khi <math>p</math> đồng dư với 1 mod 4.<ref>{{Harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA297 mục 12.1, "Sums of two squares", tr. 297–301]</ref>

=== I-đê-an nguyên tố ===
{{Chính|I-đê-an nguyên tố}}
Không phải mọi vành đều là miền phân tích nhân tử duy nhất. Chẳng hạn, trong vành các số <math>a+b\sqrt{-5}</math> (với <math>a</math> và <math>b</math> là số nguyên), số 21 có hai cách phân tích: <math>21=3\cdot7=(1+2\sqrt{-5})(1-2\sqrt{-5})</math>, trong đó cả bốn thừa số đều là tối giản, nên nó không có một phân tích nhân tử duy nhất. Để mở rộng khái niệm phân tích nhân tử duy nhất sang các lớp vành khác lớn hơn, có thể thay thế thuật ngữ về số bằng thuật ngữ về [[i-đê-an]], một [[Tập hợp con (toán học)|tập hợp con]] của các phần tử trong một vành chứa tổng của mỗi cặp phần tử của nó và tích của mỗi phần tử của nó với một phần tử trong vành. ''I-đê-an nguyên tố'', vốn khái quát hóa phần tử nguyên tố trong trường hợp [[i-đê-an chính]] tạo ra bởi một phần tử nguyên tố là một i-đê-an nguyên tố, là một công cụ quan trọng và chủ đề nghiên cứu chính trong [[đại số giao hoán]], [[lý thuyết số đại số]] và [[hình học đại số]]. Các i-đê-an nguyên tố trong vành số nguyên là (0), (2), (3), (5), (7), (11),... Định lý cơ bản của số học được khái quát hóa thành [[định lý Lasker–Noether]] biểu diễn một i-đê-an bất kỳ trong một [[vành giao hoán]] [[Vành Noether|Noether]] thành giao của các [[i-đê-an sơ cấp]], một dạng khái quát hóa thích hợp của [[lũy thừa nguyên tố]].<ref>{{chú thích sách|title=Commutative Algebra|last1=Eisenbud|first1=David|publisher=Springer-Verlag|year=1995|isbn=978-0-387-94268-1|series=Graduate Texts in Mathematics|volume=150|location=Berlin; New York|pages=|at=Mục 3.3|doi=10.1007/978-1-4612-5350-1|mr=1322960|author1-link=David Eisenbud}}</ref>

[[Phổ của một vành giao hoán|Phổ của một vành]] là một không gian hình học mà các điểm trong đó là các i-đê-an nguyên tố của vành đó.<ref>{{chú thích sách|title=Basic Algebraic Geometry 2: Schemes and Complex Manifolds|last=Shafarevich|first=Igor R.|publisher=Springer, Heidelberg|year=2013|isbn=978-3-642-38009-9|edition=3 |location=|page=5|pages=|contribution=Definition of <math>\operatorname{Spec} A</math>|doi=10.1007/978-3-642-38010-5|mr=3100288|contribution-url=https://books.google.com/books?id=zDW8BAAAQBAJ&pg=PA5}}</ref> Thuật ngữ này giúp ích nhiều cho [[hình học đại số]] và nhiều khái niệm liên quan khác cũng xuất hiện trong hình học và lý thuyết số. Chẳng hạn, sự phân tích hoặc [[Sự phân chia i-đê-an nguyên tố trong mở rộng Galois|phân chia]] i-đê-an nguyên tố khi áp dụng trong một [[mở rộng trường|trường mở rộng]], một bài toán cơ bản của lý thuyết số đại số, thì có tương đồng với [[Không gian phủ nhánh|sự phân chia trong hình học]]. Các khái niệm này thậm chí còn có thể hỗ trợ giải một số bài toán đặc biệt liên quan đến số nguyên trong lý thuyết số. Ví dụ, có thể dùng i-đê-an nguyên tố trong [[vành số nguyên]] của [[trường số bậc hai]] để chứng minh [[luật tương hỗ bậc hai]], một phát biểu về sự tồn tại của biểu thức căn bậc hai mô đun một số nguyên tố nguyên.<ref>{{chú thích sách|title=Algebraic Number Theory|last=Neukirch|first=Jürgen|publisher=Springer-Verlag|year=1999|isbn=978-3-540-65399-8|series=Grundlehren der Mathematischen Wissenschaften [Nguyên tắc cơ bản của khoa học toán học]|volume=322|location=Berlin|pages=50|at=|doi=10.1007/978-3-662-03983-0|mr=1697859}}</ref> Những cố gắng ban đầu để chứng minh [[Định lý lớn Fermat|định lý cuối của Fermat]] đã dẫn đến sự ra đời khái niệm [[số nguyên tố chính quy]], những số nguyên tố nguyên liên quan đến sự không tồn tại phân tích nhân tử duy nhất trong trường [[Trường chia đường tròn|số nguyên chia đường tròn]].<ref>{{harvnb|Neukirch|1999}}, mục I.7, tr. 38</ref> Bài toán có bao nhiêu số nguyên tố nguyên có thể được phân tích thành một tích gồm nhiều i-đê-an nguyên tố trong một trường số đại số được giải quyết bằng [[định lý mật độ Chebotarev]] mà khi được áp dụng cho số nguyên chia đường tròn thì có trường hợp đặc biệt là định lý Dirichlet về số nguyên tố trong cấp số cộng.<ref>{{chú thích tạp chí|last1=Stevenhagen|first1=P.|last2=Lenstra|first2=H.W., Jr.|date=|year=1996|title=Chebotarëv and his density theorem|url=https://archive.org/details/sim_mathematical-intelligencer_spring-1996_18_2/page/26|journal=The Mathematical Intelligencer|volume=18|issue=2|pages=26–37|doi=10.1007/BF03027290|mr=1395088|via=}}</ref>

=== Lý thuyết nhóm ===
Trong lý thuyết [[nhóm hữu hạn]], [[định lý Sylow]] phát biểu rằng nếu lũy thừa của một số nguyên tố <math>p^n</math> chia hết [[Cấp (lý thuyết nhóm)|cấp]] của một nhóm thì nó có một [[nhóm con]] với cấp <math>p^n</math>. Theo [[Định lý Lagrange (lý thuyết nhóm)|định lý Lagrange]], một nhóm với cấp nguyên tố là [[nhóm cyclic]], và theo [[định lý Burnside]] thì một nhóm có cấp chia hết được bởi đúng hai số nguyên tố là [[nhóm giải được]].<ref>{{chú thích sách|url=https://books.google.com/books?id=K8hEDwAAQBAJ|title=The Theory of Groups|last=Hall|first=Marshall|publisher=Courier Dover Publications|year=2018|isbn=978-0-486-81690-6|series=Dover Books on Mathematics|location=|pages=}} Đối với định lý Sylow, xem tr. 43; với định lý Lagrange, xem tr. 12; với định lý Burnside, xem tr. 143.</ref>

== Phương pháp tính ==
[[Tập tin:Gears large.jpg|nhỏ|Bánh răng nhỏ trong một thiết bị nông nghiệp có 13 răng (là số nguyên tố) và bánh răng vừa có 21 răng (nguyên tố cùng nhau với 13).]]
Trong một thời gian dài, lý thuyết số nói chung và ngành nghiên cứu số nguyên tố nói riêng từng được xem là ví dụ kinh điển về toán học thuần túy khi không có ứng dụng nào ngoài phạm vi toán học,{{efn|name="pure"}} ngoại trừ việc dùng các bánh răng với số răng là số nguyên tố để hạn chế mài mòn.<ref>{{chú thích sách|title=How Round is Your Circle?: Where Engineering and Mathematics Meet|url=https://archive.org/details/howroundisyourci0000brya|title-link=|last1=Bryant|first1=John|last2=Sangwin|first2=Christopher J.|publisher=Princeton University Press|year=2008|isbn=978-0-691-13118-4|location=|pages=|at=[https://books.google.com/books?id=iIN_2WjBH1cC&pg=PA178 tr. 178]}}</ref> Thậm chí, một số nhà lý thuyết số như nhà toán học người [[Vương quốc Liên hiệp Anh và Bắc Ireland|Anh]] [[Godfrey Harold Hardy|G. H. Hardy]] còn tự hào về chính họ khi làm những công trình nghiên cứu hoàn toàn không có ý nghĩa quân sự gì.<ref>{{chú thích sách|title=A Mathematician's Apology|last1=Hardy|first1=Godfrey Harold|publisher=Cambridge University Press|year=2012|isbn=978-0-521-42706-7|location=|page=[https://books.google.com/books?id=EkY2im6xkVkC&pg=PA140 140]|pages=|oclc=922010634|quote=No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.|author1-link=G. H. Hardy|orig-year=1940}}</ref>

Góc nhìn này đã bị xóa bỏ vào những năm 1970, khi số nguyên tố đã có thể được dùng làm cơ sở để tạo ra các thuật toán [[mật mã hóa khóa công khai]].<ref name="ent-7" /> Những ứng dụng này đã góp phần đẩy mạnh hoạt động nghiên cứu [[thuật toán]] thực hiện phép tính trên số nguyên tố và các phương pháp [[kiểm tra tính nguyên tố]] của một số. Thuật toán kiểm tra tính nguyên tố cơ bản nhất, giải thuật chia thử, quá chậm đối với số rất lớn. Một nhóm thuật toán hiện đại có thể áp dụng được cho một số bất kỳ, trong khi còn có các thuật toán hiệu quả hơn dành cho các nhóm số đặc biệt. Đa số thuật toán kiểm tra tính nguyên tố chỉ cho biết đầu vào của chúng có phải là số nguyên tố hay không. Một số đoạn chương trình khác còn xuất ra một (hoặc tất cả) thừa số nguyên tố từ đầu vào là hợp số và được gọi là thuật toán [[phân tích số nguyên]]. Số nguyên tố cũng có ứng dụng trong điện toán như [[giá trị tổng kiểm]], [[bảng băm]] và [[bộ sinh số giả ngẫu nhiên]].

=== Giải thuật chia thử ===
{{Chính|Chia thử}}
Phương pháp cơ bản nhất để kiểm tra tính nguyên tố của một số nguyên <math>n</math> cho trước được gọi là ''[[chia thử]]''. Thuật toán này chia <math>n</math> cho tất cả số nguyên từ 2 đến [[căn bậc hai]] của <math>n</math>. Khi có bất kỳ số nguyên nào chia hết <math>n</math> thì <math>n</math> là hợp số, ngược lại thì nó là số nguyên tố. Các số lớn hơn căn bậc hai đó không cần được kiểm tra, vì khi <math>n = a\cdot b</math> thì một trong hai thừa số <math>a</math> và <math>b</math> nhỏ hơn hoặc bằng căn bậc hai của <math>n</math>. Một dạng tối ưu khác là chỉ kiểm tra các thừa số nguyên tố trong khoảng đó.<ref>{{chú thích sách|url=https://archive.org/details/primesprogrammin0000gibl|title=Primes and Programming|last=Giblin|first=Peter|publisher=Cambridge University Press|year=1993|isbn=978-0-521-40988-9|location=|page=[https://archive.org/details/primesprogrammin0000gibl/page/39 39]|pages=}}</ref> Chẳng hạn, để kiểm tra xem 37 có phải là số nguyên tố hay không, thuật toán này chia nó cho các số nguyên tố trong khoảng từ 2 đến {{radic|37}}, đó là số 2, 3 và 5. Cả ba phép chia đều có số dư khác 0 nên 37 chính là số nguyên tố.

Phương pháp này có thể được mô tả một cách đơn giản, nhưng không thực tế khi kiểm tra tính nguyên tố của các số nguyên lớn, vì số phép chia nó thực hiện [[Tăng trưởng theo cấp số nhân|tăng dần theo cấp số nhân]] khi số chữ số của số nguyên đó càng nhiều.<ref>{{harvnb|Giblin|1993}}, [https://archive.org/details/primesprogrammin0000gibl/page/54 tr. 54]</ref> Tuy nhiên, giải thuật chia thử vẫn được sử dụng để tìm nhanh hợp số với thừa số nhỏ trước khi áp dụng những phương pháp phức tạp hơn đối với các số vượt qua được giải thuật đó.<ref name=":7">{{harvnb|Riesel|1994}}, [https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA220 tr. 220]</ref>

=== Sàng ===
{{chính|Sàng Eratosthenes}}
:[[Tập tin:Animation Sieb des Eratosthenes (vi).gif|nhỏ|phải|662x662px| [[Sàng Eratosthenes]] bắt đầu với tất cả các số đều không được đánh dấu (màu xám). Sàng này tìm số đầu tiên không được đánh dấu (màu tối) và đánh dấu bình phương của nó và tất cả các bội lớn hơn sau đó là hợp số (màu sáng hơn). Sau khi đã đánh dấu các bội của 2 (đỏ), 3 (lục), 5 (lam) và 7 (vàng), tất cả các số nguyên tố lớn đến căn bậc hai của kích thước bảng đều đã được xét, và tất cả các số còn lại chưa được đánh dấu (11, 13,...) đều là số nguyên tố (màu tím).]]
Trước khi máy tính ra đời, nhiều bảng số liệt kê tất cả số nguyên tố hoặc phân tích nguyên tố đến một giới hạn cho trước đã được phát hành rộng rãi.<ref>{{chú thích tạp chí|last=Bullynck|first=Maarten|year=2010|title=A history of factor tables with notes on the birth of number theory 1657–1817|url=https://hal-univ-paris8.archives-ouvertes.fr/hal-01103903/|journal=Revue d'Histoire des Mathématiques|volume=16|issue=2|pages=133–216}}</ref> Phương pháp cổ xưa nhất để lập danh sách số nguyên tố được gọi là sàng Eratosthenes.<ref>{{chú thích sách|url=https://books.google.com/books?id=rowCAQAAQBAJ&pg=PA191|title=The Joy of Factoring|last=Wagstaff|first=Samuel S. Jr.|publisher=American Mathematical Society|year=2013|isbn=978-1-4704-1048-3|series=Student mathematical library|volume=68|location=|page=191|pages=}}</ref> Hình minh họa bên phải cho thấy một dạng tối ưu của phương pháp này.<ref>{{harvnb|Crandall|Pomerance|2005|p=121}}</ref> Một sàng khác hiệu quả hơn để giải quyết bài toán đó là [[sàng Atkin]].<ref>{{cite conference|last1=Farach-Colton|contribution=On the complexity of computing prime tables|volume=9472|title=Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings|series=Lecture Notes in Computer Science|publisher=Springer|pages=677–688|doi=10.1007/978-3-662-48971-0_57|arxiv=1504.05240|first1=Martín|editor2-first=Kazuhisa|editor2-last=Makino|editor1-first=Khaled|editor1-last=Elbassioni|first2=Meng-Tsung|last2=Tsai|year=2015}}</ref> Trong toán học nâng cao, [[lý thuyết sàng]] áp dụng các phương pháp tương tự vào nhiều bài toán khác.<ref>{{chú thích sách|url=https://books.google.com/books?id=G0TtCAAAQBAJ&pg=PA1|title=Sieves in Number Theory|last=Greaves|first=George|publisher=Springer|year=2013|isbn=978-3-662-04658-6|series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge)|volume=43|page=1}}</ref>

=== Kiểm tra tính nguyên tố và chứng minh tính nguyên tố ===
Một số thuật toán hiện đại nhanh nhất để giải quyết bài toán về tính nguyên tố của một số <math>n</math> bất kỳ cho trước là các thuật toán [[Thuật toán ngẫu nhiên|xác suất]] ([[Thuật toán Monte Carlo|Monte Carlo]]), nghĩa là nó có một khả năng nhỏ ngẫu nhiên cho câu trả lời sai.<ref name="hromkovic">{{chú thích sách|title=Algorithmics for Hard Problems|last=Hromkovič|first=Juraj|publisher=Springer-Verlag, Berlin|year=2001|isbn=978-3-540-66860-2|series=Texts in Theoretical Computer Science. An EATCS Series|location=|pages=383–385|contribution=5.5 Bibliographic Remarks|doi=10.1007/978-3-662-04616-6|mr=1843669|contribution-url=https://books.google.com/books?id=nkeqCAAAQBAJ&pg=PA383}}</ref> Chẳng hạn, [[Kiểm tra Solovay-Strassen|kiểm tra Solovay–Strassen]] với một số cho trước <math>p</math> chọn ngẫu nhiên một số <math>a</math> trong khoảng từ 2 đến <math>p - 2</math> và sử dụng [[lũy thừa mô đun]] để kiểm tra xem <math>a^{(p-1)/2}\pm 1</math> có chia hết được bởi <math>p</math> hay không.{{efn|Trong kiểm tra này, số hạng <math>\pm 1</math> là âm nếu <math>a</math> là một số chính phương mô đun số (giả sử) nguyên tố <math>p</math> đã cho, và là dương trong trường hợp còn lại. Tổng quát hơn, với giá trị <math>p</math> không nguyên tố, số hạng <math>\pm 1</math> là [[ký hiệu Jacobi]] (phủ định), có thể được tính bằng [[luật tương hỗ bậc hai]].}} Nếu đúng là như vậy thì nó trả lời "có" và ngược lại thì nó trả lời "không". Nếu <math>p</math> đúng là số nguyên tố thì nó luôn trả lời "có", nhưng nếu <math>p</math> là hợp số thì nó trả lời "có" với xác suất lớn nhất là 1/2 và "không" với xác suất nhỏ nhất là 1/2.<ref name="koblitz">{{chú thích sách|title=A Course in Number Theory and Cryptography|last=Koblitz|first=Neal|publisher=Springer-Verlag, New York|year=1987|isbn=978-0-387-96576-5|series=Graduate Texts in Mathematics|volume=114|location=|pages=112–149|contribution=Chapter V. Primality and Factoring|doi=10.1007/978-1-4684-0310-7_5|mr=910297}}</ref> Nếu thuật toán này được lặp lại <math>n</math> lần trong cùng một số, xác suất lớn nhất để một hợp số vượt qua được thuật toán mọi lần là <math>1/2^n</math>. Vì xác suất đó giảm dần theo cấp số nhân khi số lần thực hiện kiểm tra tăng dần nên nó dẫn đến khả năng cao (nhưng không chắc chắn) rằng một số vượt qua được thuật toán lặp lại đó là số nguyên tố. Mặt khác, nếu một số không vượt qua được kiểm tra thì nó chắc chắn là hợp số.<ref>{{chú thích sách|title=Fundamentals of Computer Security|last1=Pieprzyk|first1=Josef|last2=Hardjono|first2=Thomas|last3=Seberry|first3=Jennifer|publisher=Springer|year=2013|isbn=978-3-662-07324-7|location=|pages=51–52|contribution=2.3.9 Probabilistic Computations|contribution-url=https://books.google.com/books?id=BG2rCAAAQBAJ&pg=PA51}}</ref> Một hợp số vượt qua được một kiểm tra như thế được gọi là [[số giả nguyên tố]].<ref name="koblitz" />

Ngược lại, một số thuật toán khác đảm bảo rằng câu trả lời luôn luôn đúng: số nguyên tố sẽ luôn luôn được xác định là số nguyên tố và hợp số sẽ luôn luôn được xác định là hợp số. Chẳng hạn, phát biểu này là đúng đối với giải thuật chia thử. Những thuật toán với đầu ra đảm bảo chính xác bao gồm [[thuật toán tất định]] như [[phép kiểm tra tính nguyên tố AKS]],<ref name="tao-aks">{{chú thích sách|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117|location=Providence, RI|pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|authorlink=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}</ref> và các [[thuật toán Las Vegas]] ngẫu nhiên mà trong đó những lựa chọn ngẫu nhiên của thuật toán không ảnh hưởng gì đến kết quả cuối cùng, chẳng hạn như một số dạng của [[phép chứng minh tính nguyên tố bằng đường cong elliptic]].<ref name="hromkovic" /> Khi phương pháp đường cong elliptic kết luận rằng một số là số nguyên tố, nó cũng xuất ra một [[chứng nhận tính nguyên tố]] có thể được xác nhận nhanh chóng.<ref name="atkin-morain" /> Kỹ thuật đường cong elliptic là nhanh nhất trong số các thuật toán với độ chính xác tuyệt đối, nhưng thời gian thực thi chỉ được đo dựa trên [[Luận cứ heuristic|thực nghiệm]] thay vì lập luận chứng minh. [[Phép kiểm tra tính nguyên tố AKS|Kiểm tra AKS]] có độ phức tạp tính toán được chứng minh bằng lập luận toán học nhưng hoạt động chậm hơn so với kỹ thuật đường cong elliptic.<ref name="morain">{{chú thích tạp chí|last=Morain|first=F.|date=|year=2007|title=Implementing the asymptotically fast version of the elliptic curve primality proving algorithm|url=|journal=Mathematics of Computation|volume=76|issue=257|pages=493–505|arxiv=math/0502097|bibcode=2007MaCom..76..493M|doi=10.1090/S0025-5718-06-01890-4|mr=2261033|via=}}</ref> Các phương pháp này có thể được dùng để tạo ra các số nguyên tố lớn bằng cách tạo và kiểm tra các số ngẫu nhiên đến khi tìm được một số nguyên tố; khi đó, một thuật toán kiểm tra xác suất có thể nhanh chóng loại đi phần lớn hợp số trước khi một thuật toán "chắc chắn đúng" được dùng để xác thực lại rằng các số còn lại là số nguyên tố.{{efn|Thật vậy, đa số phân tích về phép chứng minh tính nguyên tố bằng đường cong elliptic đều dựa trên giả thiết rằng đầu vào của nó đã vượt qua được một thuật toán xác suất.<ref name = "atkin-morain">{{chú thích tạp chí | last1 = Atkin | first1 = A. O. L. | last2 = Morain | first2 = F. | doi =  10.1090/s0025-5718-1993-1199989-x| issue = 203 | journal = Mathematics of Computation | mr = 1199989 | pages = 29–68 | title = Elliptic curves and primality proving | volume = 61 | year = 1993| jstor = 2152935 |url = https://www.ams.org/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718-1993-1199989-X.pdf }}</ref>}}

Bảng dưới đây liệt kê một số thuật toán như vậy. Thời gian hoạt động được cho theo số được kiểm tra <math>n</math> và số vòng lặp <math>k</math> (đối với thuật toán xác suất). Đồng thời, <math>\varepsilon</math> là một số dương nhỏ bất kỳ và <math>\log</math> là [[logarit]] cơ số không xác định. [[Kí hiệu O lớn|Ký hiệu O lớn]] nghĩa là mỗi khoảng thời gian phải được nhân lên bởi một [[Kí hiệu O lớn|hằng số tỉ lệ]] để chuyển nó từ một đại lượng vô hướng sang đơn vị thời gian; hằng số này phụ thuộc vào thông số kỹ thuật chẳng hạn như loại máy tính được dùng để thực hiện thuật toán, nhưng không phụ thuộc vào tham số đầu vào <math>n</math> và <math>k</math>.

{| class="wikitable" style="text-align:center; margin:1em auto 1em auto;"
|-
! scope="col"|Thuật toán
! scope="col"|Năm phát triển
! scope="col"|Dạng
! scope="col"|Độ phức tạp thời gian
! scope="col"|Ghi chú
! scope="col"|Chú thích
|-
| style="text-align:left;"|[[Phép kiểm tra tính nguyên tố AKS|Kiểm tra AKS]]
| 2002
| tất định
| <math>O((\log n)^{6+\varepsilon})</math>
|
|<ref name="tao-aks" /><ref>{{cite paper|last1=Lenstra|first1=Jr., H.W.|last2=Pomerance|first2=Carl|date=2019|title=Primality testing with Gaussian periods|url=https://math.dartmouth.edu/~carlp/aksfinal.pdf|journal=Journal of the European Mathematical Society|volume=21|issue=4|pages=1229–1269|doi=10.4171/JEMS/861|mr=3941463|via=}}</ref>
|-
| style="text-align:left;"|[[Phép chứng minh tính nguyên tố bằng đường cong elliptic|Chứng minh đường cong elliptic]]
| 1986
| Las Vegas
| <math>O((\log n)^{4+\varepsilon})</math><br>(theo thực nghiệm)
|
|<ref name="morain" />
|-
| style="text-align:left;"|[[Kiểm tra Baillie–PSW]]
| 1980
| Monte Carlo
| <math>O((\log n)^{2+\varepsilon})</math>
|
|<ref name="PSW">{{chú thích tạp chí|author1=Pomerance|first=Carl|author2=Selfridge|first2=John L.|author3=Wagstaff|first3=Samuel S. Jr.|date=July 1980|title=The pseudoprimes to 25·10<sup>9</sup>|url=https://math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–1026|doi=10.1090/S0025-5718-1980-0572872-7|jstor=2006210|via=}}</ref><ref name="lpsp">{{chú thích tạp chí|author1=Baillie|first=Robert|author2=Wagstaff|first2=Samuel S. Jr.|date=October 1980|title=Lucas Pseudoprimes|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|journal=Mathematics of Computation|volume=35|issue=152|pages=1391–1417|doi=10.1090/S0025-5718-1980-0583518-6|jstor=2006406|mr=583518|via=}}</ref>
|-
| style="text-align:left;"|[[Kiểm tra Miller-Rabin|Kiểm tra Miller–Rabin]]
| 1980
| Monte Carlo
| <math>O(k(\log n)^{2+\varepsilon})</math>
| style="text-align:left;"|xác suất sai số <math>4^{-k}</math>
|<ref name="monier">{{chú thích tạp chí|last=Monier|first=Louis|date=|year=1980|title=Evaluation and comparison of two efficient probabilistic primality testing algorithms|url=|journal=Theoretical Computer Science|volume=12|issue=1|pages=97–108|doi=10.1016/0304-3975(80)90007-9|mr=582244|via=}}</ref>
|-
| style="text-align:left;"|[[Kiểm tra Solovay-Strassen|Kiểm tra Solovay–Strassen]]
| 1977
| Monte Carlo
| <math>O(k(\log n)^{2+\varepsilon})</math>
| style="text-align:left;"|xác suất sai số <math>2^{-k}</math>
|<ref name="monier" />
|}

=== Các thuật toán đặc biệt và số nguyên tố lớn nhất đã biết ===
{{Xem thêm|Danh sách số nguyên tố}}
Cùng với các thuật toán nói trên áp dụng được cho bất kỳ số tự nhiên nào, một vài số với dạng đặc biệt còn có thể được kiểm tra tính nguyên tố nhanh hơn. Ví dụ, [[Kiểm tra Lucas-Lehmer|kiểm tra Lucas–Lehmer]] có thể xác định được một [[Số nguyên tố Mersenne|số Mersenne]] (lũy thừa của 2 trừ 1) có phải là số nguyên tố hay không một cách tất định với thời gian bằng với một vòng lặp của kiểm tra Miller–Rabin.<ref>{{Harvnb|Tao|2009|p=36–41}}</ref> Đó là lý do kể từ năm 1992 (tính đến tháng 10 năm 2024) [[số nguyên tố lớn nhất đã biết]] luôn là một số nguyên tố Mersenne.<ref>{{Harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA41 tr. 41]</ref> Có giả thuyết cho rằng có vô số số nguyên tố Mersenne.<ref>Chẳng hạn xem {{Harvnb|Guy|2013}}, [https://books.google.com/books?id=1BnoBwAAQBAJ&pg=PA13 A3 "Mersenne primes. Repunits. Fermat numbers. Primes of shape <math>k\cdot 2^n+1</math>", tr. 13–21].</ref>

Bảng dưới đây liệt kê các số nguyên tố lớn nhất đã biết theo nhiều dạng khác nhau. Một vài trong số đó được tìm thấy qua [[điện toán phân tán]]. Năm 2009, dự án [[Great Internet Mersenne Prime Search]] đã được trao giải thưởng 100.000&nbsp;[[đô la Mỹ|USD]] cho số nguyên tố đầu tiên có ít nhất 10 triệu chữ số thập phân.<ref>{{Chú thích web|url=https://www.eff.org/press/archives/2009/10/14-0|tựa đề=Record 12-Million-Digit Prime Number Nets $100,000 Prize|tác giả=|họ=|tên=|ngày=2009-10-14|website=|nhà xuất bản=Tổ chức Biên giới Điện tử|url lưu trữ=https://web.archive.org/web/20091017012456/https://www.eff.org/press/archives/2009/10/14-0|ngày lưu trữ=2009-10-17|url hỏng=không|ngày truy cập=2020-08-03}}</ref> [[Tổ chức Biên giới Điện tử]] cũng có giải thưởng lần lượt là 150.000 và 250.000&nbsp;USD dành cho số nguyên tố có ít nhất 100 triệu và 1 tỷ chữ số.<ref>{{Chú thích web|url=https://www.eff.org/awards/coop|tựa đề=EFF Cooperative Computing Awards|tác giả=|họ=|tên=|ngày=2008-02-29|website=|nhà xuất bản=Tổ chức Biên giới Điện tử|url lưu trữ=https://web.archive.org/web/20080313113923/https://www.eff.org/awards/coop|ngày lưu trữ=2008-03-13|url hỏng=không|ngày truy cập=2020-08-03}}</ref>

{| class="wikitable" style="text-align:center; margin:1em auto 1em auto;"
|-
! scope="col"|Dạng số nguyên tố
! scope="col"|Số nguyên tố
! scope="col"|Số chữ số
! scope="col"|Thời gian
! scope="col"|Tìm ra bởi
|-
| style="text-align:left;"|[[Số nguyên tố Mersenne|Mersenne]]
| style="text-align:left;"|2<sup>136.279.841</sup> − 1
| style="text-align:right;"|41.024.320
| style="text-align:left;"|12 tháng 10 năm 2024<ref name="GIMPS-2024">{{chú thích web|url=https://www.mersenne.org/primes/?press=M136279841|title=GIMPS Project Discovers Largest Known Prime Number: 2<sup>136,279,841</sup>-1|tác giả=|họ=|tên=|date=2024-10-21|work=Mersenne Research, Inc.|url lưu trữ=https://web.archive.org/web/20181221183807/https://www.mersenne.org/primes/?press=M136279841|ngày lưu trữ=2024-10-21|url hỏng=không|access-date = 2024-10-21}}</ref>
| style="text-align:left;"|Luke Durant, Great Internet Mersenne Prime Search
|-
| style="text-align:left;"|[[Số nguyên tố Proth|Proth]]
| style="text-align:left;"|10.223 × 2<sup>31.172.165</sup> + 1
| style="text-align:right;"|9.383.761
| style="text-align:left;"|31 tháng 10 năm 2016<ref>{{chú thích web|url=https://www.primegrid.com/download/SOB-31172165.pdf|title=PrimeGrid's Seventeen or Bust Subproject|ngày=|website=|url lưu trữ=https://web.archive.org/web/20161112051125/https://www.primegrid.com/download/SOB-31172165.pdf|ngày lưu trữ=2016-11-12|url hỏng=không|access-date = 2020-08-03}}</ref>
| style="text-align:left;"|Péter Szabolcs, [[PrimeGrid]]<ref name="toptwenty">{{chú thích web|url=http://primes.utm.edu/top20/page.php?id=3|title=The Top Twenty: Largest Known Primes|tác giả=|last=Caldwell|first=Chris K.|date=|website=The Prime Pages|url lưu trữ=|ngày lưu trữ=|url hỏng=|access-date = 2020-08-03}}</ref>
|-
| style="text-align:left;"|[[Số nguyên tố giai thừa|Giai thừa]]
| style="text-align:left;"|422.429! − 1
| style="text-align:right;"|2.193.027
| style="text-align:left;"|Tháng 2 năm 2022
| style="text-align:left;"|Ryan Propper<ref>{{chú thích web|url=http://primes.utm.edu/top20/page.php?id=30|title=The Top Twenty: Factorial|tác giả=|last=Caldwell|first=Chris K.|date=|website=The Prime Pages|url lưu trữ=|ngày lưu trữ=|url hỏng=|access-date = 2020-08-03}}</ref>
|-
| style="text-align:left;"|[[Số nguyên tố giai thừa nguyên tố|Giai thừa nguyên tố]]{{efn|Hàm [[giai thừa nguyên tố]] của <math>n</math>, ký hiệu là <math>n\#</math>, cho giá trị tích của các số nguyên tố lớn đến <math>n</math>, và một [[số nguyên tố giai thừa nguyên tố]] là số nguyên tố thuộc một trong các dạng <math>n\#\pm 1</math>.<ref name="Ribenboim2004" />}}
| style="text-align:left;"|6.369.619# − 1
| style="text-align:right;"|2.765.105
| style="text-align:left;"|Tháng 8 năm 2024
| style="text-align:left;"|Nick Merrylees, PrimeGrid<ref>{{chú thích web|url=http://primes.utm.edu/top20/page.php?id=5|title=The Top Twenty: Primorial|tác giả=|last=Caldwell|first=Chris K.|date=|website=The Prime Pages|url lưu trữ=|ngày lưu trữ=|url hỏng=|access-date = 2020-08-03}}</ref>
|-
| style="text-align:left;"|[[Số nguyên tố sinh đôi|Sinh đôi]]
| style="text-align:left;"|2.996.863.034.895 × 2<sup>1.290.000</sup> ± 1
| style="text-align:right;"|388.342
| style="text-align:left;"|Tháng 9 năm 2016
| style="text-align:left;"|Tom Greer, PrimeGrid<ref>{{chú thích web|url=http://primes.utm.edu/top20/page.php?id=1|title=The Top Twenty: Twin Primes|tác giả=|last=Caldwell|first=Chris K.|date=|website=The Prime Pages|url lưu trữ=|ngày lưu trữ=|url hỏng=|access-date = 2020-08-03}}</ref>
|-
|}

=== Phân tích số nguyên ===
{{Chính|Phân tích số nguyên}}
Cho một hợp số <math>n</math>, công việc xuất ra một (hoặc tất cả) thừa số nguyên tố được gọi là ''phân tích'' của <math>n</math>. Công việc này khó hơn đáng kể so với kiểm tra tính nguyên tố,<ref>{{Harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA275 tr. 275]</ref> và mặc dù tồn tại nhiều thuật toán phân tích nhưng chúng đều chậm hơn so với các phương pháp nhanh nhất để kiểm tra tính nguyên tố. Giải thuật chia thử và [[thuật toán RHO]] có thể được dùng để tìm các nhân tử rất nhỏ của <math>n</math>,<ref name=":7" /> và thuật toán [[Phân tích số nguyên bằng đường elip|phân tích bằng đường cong elliptic]] có thể hiệu quả khi <math>n</math> có các nhân tử lớn vừa phải.<ref>{{chú thích sách|url=https://books.google.com/books?id=cbl_BAAAQBAJ&pg=PA329|title=An Introduction to Mathematical Cryptography|last1=Hoffstein|first1=Jeffrey|last2=Pipher|first2=Jill|last3=Silverman|first3=Joseph H.|publisher=Springer|year=2014|isbn=978-1-4939-1711-2|edition=2 |series=Undergraduate Texts in Mathematics|location=|page=329|pages=}}</ref> Một số phương pháp phù hợp đối với số lớn bất kỳ không phụ thuộc vào độ lớn của nhân tử bao gồm [[sàng cấp hai]] và [[sàng trường số thông thường]]. Giống như kiểm tra tính nguyên tố, có một số thuật toán phân tích yêu cầu đầu vào có dạng đặc biệt, trong đó có [[sàng trường số đặc biệt]].<ref>{{chú thích tạp chí|last=Pomerance|first=Carl|date=|year=1996|title=A tale of two sieves|url=|journal=Notices of the American Mathematical Society|volume=43|issue=12|pages=1473–1485|mr=1416721|via=}}</ref> Tính đến tháng 2 năm 2020 [[Kỷ lục phân tích số nguyên|số lớn nhất được phân tích]] bằng một thuật toán thông thường là [[Số RSA|RSA-250]], một số có 250 chữ số (829 bit) và là tích của hai số nguyên tố lớn.<ref>{{Chú thích danh sách thư|url=https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html|title=Factorization of RSA-250|access-date=2020-08-03|first=Paul|last=Zimmermann|date=2020-02-28|mailing-list=cado-nfs-discuss|archive-date=2020-02-28|archive-url=https://web.archive.org/web/20200228234716/https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html|url-status=dead}}</ref>

[[Thuật toán Shor]] cho phép phân tích bất kỳ số nguyên nào với số bước đa thức trong một [[máy tính lượng tử]].<ref>{{chú thích sách|title=Quantum Computing: A Gentle Introduction|last1=Rieffel|first1=Eleanor G.|last2=Polak|first2=Wolfgang H.|publisher=MIT Press|year=2011|isbn=978-0-262-01506-6|location=|pages=163–176|contribution=Chapter 8. Shor's Algorithm|contribution-url=https://books.google.com/books?id=iYX6AQAAQBAJ&pg=PA163}}</ref> Tuy nhiên, với công nghệ hiện nay thì thuật toán này chỉ hoạt động được với các số rất nhỏ. Tính đến tháng 10 năm 2012 số lớn nhất được phân tích bằng thuật toán Shor trong một máy tính lượng tử là 21.<ref>{{chú thích tạp chí|last1=Martín-López|first1=Enrique|last2=Laing|first2=Anthony|last3=Lawson|first3=Thomas|last4=Alvarez|first4=Roberto|last5=Zhou|first5=Xiao-Qi|last6=O'Brien|first6=Jeremy L.|date=ngày 12 tháng 10 năm 2012|title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal=Nature Photonics|volume=6|issue=11|pages=773–776|arxiv=1111.4147|bibcode=2012NaPho...6..773M|doi=10.1038/nphoton.2012.259}}</ref>

=== Ứng dụng khác trong điện toán ===
Một số thuật toán [[mật mã hóa khóa công khai]], chẳng hạn như [[RSA (mã hóa)|RSA]] và [[Trao đổi khóa Diffie-Hellman|trao đổi khóa Diffie−Hellman]] được dựa trên số nguyên tố lớn (phổ biến nhất là số nguyên tố 2048 [[bit]]).<ref>{{chú thích báo|url=https://www.theregister.com/2016/10/09/crypto_needs_more_transparency_researchers_warn/|title=Crypto needs more transparency, researchers warn|last=Chirgwin|first=Richard|date=2016-10-09|newspaper=The Register|archive-url=https://web.archive.org/web/20161011163742/https://www.theregister.co.uk/2016/10/09/crypto_needs_more_transparency_researchers_warn/|archive-date=2016-10-11|access-date = 2020-08-03|url-status=live}}</ref> RSA dựa vào giả thiết rằng thực hiện phép nhân hai số lớn <math>x</math> và <math>y</math> dễ hơn nhiều so với khi tính <math>x</math> và <math>y</math> (giả sử là hai [[số nguyên tố cùng nhau]]) nếu chỉ biết một tích <math>xy</math>.<ref name="ent-7" /> Trao đổi khóa Diffie−Hellman dựa vào thực tế rằng có một số thuật toán hiệu quả đối với lũy thừa mô đun (tính <math>a^b\bmod{c}</math>), trong khi phép tính ngược lại ([[Lôgarit rời rạc|logarit rời rạc]]) được cho là một bài toán khó.<ref>{{harvnb|Hoffstein|Pipher|Silverman|2014}}, mục 2.3, "Diffie–Hellman key exchange", tr. 65–67.</ref>

Số nguyên tố được sử dụng thường xuyên trong [[bảng băm]]. Chẳng hạn phương pháp ban đầu của Carter và Wegman đối với [[băm phổ quát]] được dựa vào việc tính hàm băm bằng cách chọn ngẫu nhiên [[Hàm số bậc nhất|hàm tuyến tính]] mô đun số nguyên tố lớn. Carter và Wegman đã khái quát hóa phương pháp này cho [[Băm k-độc lập|băm <math>k</math>-độc lập]] bằng cách sử dụng đa thức bậc cao mô đun số nguyên tố lớn.<ref>{{chú thích sách|title=Introduction to Algorithms|url=https://archive.org/details/introductiontoal00corm_691|last=Cormen|first=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|publisher=MIT Press và McGraw-Hill|year=2001|isbn=0-262-03293-7|edition=2 |location=|pages=[https://archive.org/details/introductiontoal00corm_691/page/n254 232]–236|chapter=11.3 Universal hashing|orig-year=1990}} Đối với băm <math>k</math>-độc lập xem bài toán 11–4, tr. 251. Đối với phần ghi công Carter và Wegman xem chú thích chương, tr. 252.</ref> Cũng như trong hàm băm, số nguyên tố được dùng trong kích thước của bảng băm dựa trên [[dò cấp hai]] để đảm bảo rằng chuỗi dò bao phủ hết bảng đó.<ref>{{chú thích sách|title=Data Structures & Algorithms in Java|url=https://archive.org/details/datastructuresal0004edgood|last1=Goodrich|first1=Michael T.|last2=Tamassia|first2=Roberto|publisher=John Wiley & Sons|year=2006|isbn=978-0-471-73884-8|edition=4 |location=|pages=}} Xem "Quadratic probing", tr. 382, và bài tập C–9.9, tr. 415.</ref>

Một số phương pháp [[giá trị tổng kiểm]] được dựa trên kiến thức toán học về số nguyên tố. Chẳng hạn giá trị tổng kiểm dùng trong [[ISBN]] được xác định bằng cách lấy tổng của tất cả các chữ số (ngoài chữ số cuối cùng) mô đun 11. Vì 11 là số nguyên tố nên phương pháp này có thể phát hiện các chữ số bị sai và chuyển vị của các chữ số liền kề nhau.<ref>{{chú thích sách|url=https://books.google.com/books?id=Z8eka35WUb8C&pg=PA43|title=Identification Numbers and Check Digit Schemes|last=Kirtland|first=Joseph|publisher=Mathematical Association of America|year=2001|isbn=978-0-88385-720-5|series=Classroom Resource Materials|volume=18|pages=43–44}}</ref> [[Adler-32]], một công cụ kiểm tra tổng kiểm khác, sử dụng số học mô đun 65521, số nguyên tố lớn nhất nhỏ hơn <math>2^{16}</math>.<ref>{{chú thích sách|url=http://www.rfc-editor.org/rfc/rfc1950.txt|title=ZLIB Compressed Data Format Specification version 3.3|last=Deutsch|first=P.|publisher=Network Working Group|year=1996|isbn=|series=[[Request for Comments]]|volume=1950|location=|pages=}}</ref> Số nguyên tố cũng được dùng trong [[bộ sinh số giả ngẫu nhiên]], trong đó có [[bộ sinh số đồng dư tuyến tính]]<ref>{{chú thích sách|title=The Art of Computer Programming, Vol. 2: Seminumerical algorithms|title-link=The Art of Computer Programming|last=Knuth|first=Donald E.|publisher=Addison-Wesley|year=1998|isbn=978-0-201-89684-8|edition=3 |pages=10–26|contribution=3.2.1 The linear congruential model|authorlink=Donald Knuth}}</ref> và [[Mersenne Twister]].<ref>{{chú thích tạp chí|last1=Matsumoto|first1=Makoto|last2=Nishimura|first2=Takuji|date=|year=1998|title=Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator|url=|journal=ACM Transactions on Modeling and Computer Simulation|volume=8|issue=1|pages=3–30|doi=10.1145/272991.272995|via=}}</ref>

== Các ứng dụng khác ==
Số nguyên tố là chủ đề trọng tâm của lý thuyết số và có nhiều ứng dụng trong các lĩnh vực khác của toán học, trong đó có [[đại số trừu tượng]] và hình học cơ bản. Ví dụ, có thể đặt một số lượng số nguyên tố các điểm trên mặt phẳng hai chiều sao cho [[Bài toán không có ba điểm thẳng hàng|không có ba điểm nào thẳng hàng]], hoặc sao cho một tam giác bất kỳ với ba đỉnh là ba trong số các điểm đó [[Bài toán tam giác Heilbronn|có kích thước lớn]].<ref>{{chú thích tạp chí|last=Roth|first=K.F.|date=|year=1951|title=On a problem of Heilbronn|url=|journal=Journal of the London Mathematical Society|series=Second Series|volume=26|issue=3|pages=198–204|doi=10.1112/jlms/s1-26.3.198|mr=0041889|via=}}</ref> Một ví dụ khác là [[tiêu chuẩn Eisenstein]], dùng để kiểm tra xem một [[Đa thức tối giản|đa thức có tối giản]] hay không dựa vào tính chia hết của các hệ số cho một số nguyên tố và bình phương của nó.<ref>{{chú thích tạp chí|last=Cox|first=David A.|date=|year=2011|title=Why Eisenstein proved the Eisenstein criterion and why Schönemann discovered it first|url=https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Cox-2012.pdf|journal=[[American Mathematical Monthly]]|volume=118|issue=1|pages=3–31|doi=10.4169/amer.math.monthly.118.01.003|via=|access-date=2020-08-03|archive-date=2023-03-26|archive-url=https://web.archive.org/web/20230326032030/https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Cox-2012.pdf}}</ref>
[[Tập tin:Sum of knots3.svg|nhỏ|Tổng liên kết của hai nút thắt nguyên tố]]
Khái niệm số nguyên tố quan trọng đến mức nó đã được khái quát hóa sang các nhánh khác của toán học. Thông thường, "nguyên tố" có nghĩa là "tối thiểu" hoặc "không khai triển, phân tích được" trong trường hợp thích hợp. Ví dụ, [[trường nguyên tố]] của một trường cho trước là trường con nhỏ nhất của trường đã cho có chứa cả 0 và 1. Nó có thể là trường số hữu tỉ hoặc một [[trường hữu hạn]] có số lượng phần tử là số nguyên tố.<ref>{{chú thích sách|title=Algebra|last1=Lang|first1=Serge|publisher=[[Springer-Verlag]]|year=2002|isbn=978-0-387-95385-4|series=Graduate Texts in Mathematics|volume=211|location=Berlin; New York|pages=90|doi=10.1007/978-1-4613-0041-0|mr=1878556}}</ref> Một nghĩa thứ hai ám chỉ rằng bất kỳ đối tượng nào cũng đều có một cách phân tích duy nhất thành các thành phần nguyên tố. Chẳng hạn, trong [[lý thuyết nút thắt]], [[nút thắt nguyên tố]] là một [[Nút thắt (toán học)|nút thắt]] không phân tích được, nghĩa là nó không thể được viết thành [[tổng liên kết]] của hai nút thắt không tầm thường. Mỗi nút thắt bất kỳ có một cách biểu diễn duy nhất thành tổng liên kết của các nút thắt nguyên tố.<ref>{{chú thích tạp chí|last=Schubert|first=Horst|year=1949|title=Die eindeutige Zerlegbarkeit eines Knotens in Primknoten|journal=S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl.|volume=1949|issue=3|pages=57–104|mr=0031733}}</ref> [[Phân tích nguyên tố (3-đa tạp)|Phân tích nguyên tố của 3-đa tạp]] là ví dụ khác của dạng này.<ref>{{chú thích tạp chí|last=Milnor|first=J.|authorlink=John Milnor|year=1962|title=A unique decomposition theorem for 3-manifolds|url=https://archive.org/details/sim_american-journal-of-mathematics_1962-01_84_1/page/n8|journal=American Journal of Mathematics|volume=84|issue=1|pages=1–7|doi=10.2307/2372800|jstor=2372800|mr=0142125}}</ref>

Cùng với toán học và điện toán, số nguyên tố có mối liên hệ với [[cơ học lượng tử]] và là hình ảnh ẩn dụ trong nghệ thuật và văn học. Chúng cũng có ứng dụng trong [[sinh học tiến hóa]] để giải thích vòng đời của liên họ [[Ve sầu]].

=== Đa giác vẽ được và phân chia đa giác ===
[[Tập tin:Pentagon construct.gif|nhỏ|Một ngũ giác đều được vẽ bằng thước thẳng và compa. Tính chất này do 5 là số nguyên tố Fermat.]]
[[Số Fermat]] là những số có dạng
: <math>F_k = 2^{2^k}+1,</math>
với <math>k</math> là số nguyên không âm.<ref>{{harvtxt|Boklan|Conway|2017}} còn liệt kê thêm số <math> 2^0 + 1 = 2</math>, một số không theo đúng dạng số Fermat.</ref> Chúng được đặt tên theo [[Pierre de Fermat]], người đã dự đoán rằng tất cả các số dạng này đều là số nguyên tố. Năm số Fermat đầu tiên – 3, 5, 17, 257 và 65.537 – đều là số nguyên tố,<ref name="kls">{{chú thích sách|url=https://books.google.com/books?id=hgfSBwAAQBAJ&pg=PA1|title=17 Lectures on Fermat Numbers: From Number Theory to Geometry|last1=Křížek|first1=Michal|last2=Luca|first2=Florian|last3=Somer|first3=Lawrence|publisher=Springer-Verlag|year=2001|isbn=978-0-387-95332-8|series=CMS Books in Mathematics|volume=9|location=New York|pages=1–2|doi=10.1007/978-0-387-21850-2|mr=1866957}}</ref> nhưng <math>F_5</math> là hợp số và tương tự với tất cả các số Fermat khác (tính đến năm 2017).<ref name=":8">{{chú thích tạp chí|last1=Boklan|first1=Kent D.|last2=Conway|first2=John H.|date=January 2017|title=Expect at most one billionth of a new Fermat prime!|url=|journal=The Mathematical Intelligencer|volume=39|issue=1|pages=3–5|arxiv=1605.01371|doi=10.1007/s00283-016-9644-3|via=}}</ref> Một [[Đa giác đều|<math>n</math>-giác đều]] có thể [[Đa thức vẽ được|vẽ được bằng thước thẳng và compa]] khi và chỉ khi tập hợp các thừa số nguyên tố lẻ của [[Đa giác đều|<math>n</math>]] (nếu có) chỉ gồm các số nguyên tố Fermat.<ref name=":8" /> Tương tự, một [[Đa giác đều|<math>n</math>]]-giác đều có thể vẽ được bằng thước, compa và [[thước góc phần ba]] khi và chỉ khi tập hợp các thừa số nguyên tố của [[Đa giác đều|<math>n</math>]] có chứa số 2 hoặc số 3 cùng một tập hợp (có thể rỗng) các [[số nguyên tố Pierpont]], số nguyên tố có dạng <math>2^a3^b+1</math>.<ref>{{chú thích tạp chí|last=Gleason|first=Andrew M.|date=|year=1988|title=Angle trisection, the heptagon, and the triskaidecagon|url=https://archive.org/details/sim_american-mathematical-monthly_1988-03_95_3/page/185|journal=[[American Mathematical Monthly]]|volume=95|issue=3|pages=185–194|doi=10.2307/2323624|jstor=2323624|mr=935432|via=}}</ref>

Có thể chia một đa giác lồi bất kỳ thành [[Đa giác đều|<math>n</math>]] đa giác lồi nhỏ hơn với diện tích và chu vi bằng nhau khi [[Đa giác đều|<math>n</math>]] là [[Lũy thừa nguyên tố|lũy thừa của một số nguyên tố]], nhưng chưa rõ tính chất này ra sao với các giá trị khác của [[Đa giác đều|<math>n</math>]].<ref>{{chú thích tạp chí|last=Ziegler|first=Günter M.|authorlink=Günter M. Ziegler|year=2015|title=Cannons at sparrows|journal=European Mathematical Society Newsletter|issue=95|pages=25–31|mr=3330472}}</ref>

=== Cơ học lượng tử ===
Bắt đầu từ công trình của [[Hugh Lowell Montgomery|Hugh Montgomery]] và [[Freeman Dyson]] vào những năm 1970, nhiều nhà toán học và vật lý suy đoán rằng nghiệm số của hàm zeta Riemann có liên hệ với [[mức năng lượng]] của [[Cơ học lượng tử|hệ thống lượng tử]].<ref>{{chú thích web|url=http://www.maa.org/mathland/mathtrek_6_28_99.html|title=The Return of Zeta|tác giả=|last=Peterson|first=Ivars|date = 1999-06-28 |work=MAA Online|archiveurl=https://web.archive.org/web/19991105061741/http://www.maa.org/mathland/mathtrek_6_28_99.html|archive-date = 1999-11-05 |url hỏng=|access-date = 2020-08-03}}</ref><ref>{{Chú thích tạp chí|last=Hayes|first=Brian|date=2003|title=Computing science: The spectrum of Riemannium|url=|journal=American Scientist|volume=91|issue=4|pages=296–300|doi=10.1511/2003.26.3349|jstor=27858239|via=}}</ref> Số nguyên tố cũng có ý nghĩa quan trọng trong [[khoa học thông tin lượng tử]] nhờ vào các cấu trúc toán học như [[cơ sở không lệch qua lại]] và [[SIC-POVM]] ([[độ đo]] giá trị toán tử dương đối xứng đầy đủ thông tin).<ref>{{chú thích sách|title=Geometry of Quantum States: An Introduction to Quantum Entanglement|last=Bengtsson|first=Ingemar|last2=Życzkowski|first2=Karol|publisher=[[Cambridge University Press]]|others=|year=2017|isbn=978-1-107-02625-4|edition=2 |location=Cambridge|pages=313–354|oclc=967938939}}</ref><ref>{{Chú thích tạp chí|last=Zhu|first=Huangjun|date=|year=2010|title=SIC POVMs and Clifford groups in prime dimensions|url=https://arxiv.org/pdf/1003.3591.pdf|journal=Journal of Physics A: Mathematical and Theoretical|volume=43|issue=30|pages=305305|arxiv=1003.3591|bibcode=2010JPhA...43D5305Z|doi=10.1088/1751-8113/43/30/305305|via=}}</ref>

=== Sinh học ===
Chu kỳ tiến hóa của liên họ [[ve sầu]] chi ''[[Magicicada]]'' ở [[Bắc Mỹ]] có liên quan đến số nguyên tố.<ref>{{chú thích tạp chí|last=Goles|first=E.|last2=Schulz|first2=O.|last3=Markus|first3=M.|date=|year=2001|title=Prime number selection of cycles in a predator-prey model|url=|journal=Complexity|volume=6|issue=4|pages=33–38|bibcode=2001Cmplx...6d..33G|doi=10.1002/cplx.1040|via=}}</ref> Các côn trùng này sống phần lớn cuộc đời dưới dạng [[ấu trùng]] dưới lòng đất. Chúng chỉ phát triển dần và chui lên mặt đất sau 7, 13 hoặc 17 năm, từ đó chúng bay, sinh sản và chết sau nhiều nhất vài tuần. Các nhà sinh học giả thiết rằng tính nguyên tố của chu kỳ sinh sản là để tránh đồng bộ với chu kỳ của động vật ăn thịt.<ref>{{chú thích tạp chí|last1=Campos|first1=Paulo R.A.|last2=de Oliveira|first2=Viviane M.|last3=Giro|first3=Ronaldo|last4=Galvão|first4=Douglas S.|year=2004|title=Emergence of prime numbers as the result of evolutionary strategy|journal=[[Physical Review Letters]]|volume=93|issue=9|page=098107|arxiv=q-bio/0406017|bibcode=2004PhRvL..93i8107C|doi=10.1103/PhysRevLett.93.098107|pmid=15447148}}</ref><ref>{{chú thích báo|url=http://economist.com/PrinterFriendly.cfm?Story_ID=2647052|title=Invasion of the Brood|last=|first=|date = 2004-05-06 |work=[[The Economist]]|archive-url=https://web.archive.org/web/20060515184334/http://economist.com/PrinterFriendly.cfm?Story_ID=2647052|archive-date=2006-05-15|access-date = 2020-08-03}}</ref> Ngược lại, chu kỳ ra hoa nhiều năm của [[tre]] được cho là [[số nhẵn]], chỉ có các thừa số nguyên tố nhỏ trong phân tích của nó.<ref>{{cite magazine|last1=Zimmer|first1=Carl|date = 2015-05-15 |title=Bamboo Mathematicians|url=https://www.nationalgeographic.com/science/phenomena/2015/05/15/bamboo-mathematicians/|department=Phenomena: The Loom|journal=[[National Geographic]]|volume=|pages=|doi=|pmid=|access-date = 2020-08-03|archive-url=https://web.archive.org/web/20150517210059/http://phenomena.nationalgeographic.com/2015/05/15/bamboo-mathematicians/|archive-date=2015-05-17|url-status=live|via=|magazine=}}</ref>

=== Nghệ thuật và văn học ===
Số nguyên tố đã làm ảnh hưởng đến nhiều nghệ sĩ và nhà văn. [[Nhà soạn nhạc]] người [[Pháp]] [[Olivier Messiaen]] sử dụng số nguyên tố để sáng tác nhạc qua "hiện tượng tự nhiên". Trong một số sáng tác như ''La Nativité du Seigneur'' (1935) và ''Quatre études de rythme'' (1949–1950), ông đồng thời áp dụng nhạc tố với độ dài cho bởi các số nguyên tố khác nhau để tạo những nhịp điệu đặc biệt: số 41, 43, 47 và 53 xuất hiện trong [[khúc luyện]] thứ ba "Neumes rythmiques". Theo Messiaen, phong cách sáng tác này "lấy cảm hứng từ vận động tự nhiên, vận động theo hướng tự do và khác biệt".<ref>{{chú thích sách|url=https://books.google.com/books?id=7ag3ymWqvfgC&pg=PT225|title=The Messiaen companion|publisher=Amadeus Press|year=1995|isbn=978-0-931340-95-6|editor1-last=Hill|editor1-first=Peter Jensen|location=Portland, OR|at=Ex. 13.2 ''Messe de la Pentecôte'' 1 'Entrée'}}</ref>

Trong tiểu thuyết khoa học viễn tưởng ''[[Contact (tiểu thuyết)|Contact]]'' (1985), nhà khoa học [[Carl Sagan]] gợi ý rằng phân tích nguyên tố có thể được dùng để tạo mặt phẳng ảnh hai chiều khi liên lạc với [[Sự sống ngoài Trái Đất|người ngoài hành tinh]], một ý tưởng mà ông cùng nhà thiên văn người [[Hoa Kỳ]] [[Frank Drake]] phát triển từ năm 1975.<ref>{{chú thích sách|title=Mathematical Adventures for Students and Amateurs|last=Pomerance|first=Carl|publisher=Mathematical Association of America|year=2004|isbn=978-0-88385-548-5|editor1-last=Hayes|editor1-first=David F.|series=MAA Spectrum|location=Washington, DC|pages=3–6|contribution=Prime Numbers and the Search for Extraterrestrial Intelligence|mr=2085842|editor2-last=Ross|editor2-first=Peter|contribution-url=https://math.dartmouth.edu/~carlp/PDF/extraterrestrial.pdf}}</ref> Trong tiểu thuyết ''[[The Curious Incident of the Dog in the Night-Time]]'' (''Bí ẩn về con chó lúc nửa đêm'') của [[Mark Haddon]], tác giả đánh số các mục của câu chuyện bằng các số nguyên tố liên tiếp để truyền đạt trạng thái tinh thần của nhân vật chính, một cậu bé có năng khiếu toán học mắc [[hội chứng Asperger]].<ref>{{chú thích báo|url=https://www.theguardian.com/science/punctuated-equilibrium/2010/sep/16/curious-incident-dog-night-time|title=The Curious Incident of the Dog in the Night-Time|author=GrrlScientist|first=|date = 2010-09-16 |newspaper=[[The Guardian]]|access-date = 2020-08-03 |archive-url=https://web.archive.org/web/20100922003733/https://guardian.co.uk/science/punctuated-equilibrium/2010/sep/16/curious-incident-dog-night-time|archive-date=2010-09-22|department=Science|url-status=live}}</ref> Số nguyên tố là hình ảnh ẩn dụ cho sự cô đơn trong tiểu thuyết ''[[La Solitudine dei Numeri Primi (tiểu thuyết)|La Solitudine dei Numeri Primi]]'' (''Nỗi cô đơn của các số nguyên tố'') của [[Paolo Giordano]], ở đó chúng được mô tả là "người ngoài cuộc" trong các số nguyên.<ref>{{chú thích báo|url=https://www.nytimes.com/2010/04/11/books/review/Schillinger-t.html|title=Counting on Each Other|last=Schillinger|first=Liesl|date=2010-04-09|newspaper=[[The New York Times]]|department=Sunday Book Review|archive-url=https://web.archive.org/web/20100412160158/https://www.nytimes.com/2010/04/11/books/review/Schillinger-t.html|archive-date=2010-04-12|access-date=2022-11-06}}</ref>

== Xem thêm ==
{{Chủ đề|Toán học}}
{{cols|colwidth=16em}}
*[[Số tự nhiên]]
*[[Số chẵn]]
*[[Số lẻ]]
*[[Số nguyên]]
*[[Phân tích số nguyên]]
*[[Phân số]]
*[[Số vô tỉ]]
*[[Số hữu tỉ]]
*[[Số phức]]
*[[Số nguyên Gauss]]
{{colend}}
== Ghi chú ==
{{Notelist|30em}}
== Chú thích ==
{{Tham khảo|30em}}
== Liên kết ngoài ==
{{thể loại Commons|Prime numbers}}
* {{springer|title=Prime number|id=Prime_number|first=|last=}}
* {{Britannica|476309|Prime (number)}}
* {{In Our Time|Prime Numbers|p003hyf5}}
* Caldwell, Chris, ''The Prime Pages'' tại [http://primes.utm.edu/ primes.utm.edu]
* {{TĐBKVN|28067|Bảng số nguyên tố}}
* [http://www.primos.mat.br/indexen.html Các số nguyên tố đến 1 nghìn tỷ]. {{Webarchive|url=https://web.archive.org/web/20210227001026/http://www.primos.mat.br/indexen.html |date=2021-02-27 }}

{{Phân loại các số nguyên tố}}
{{Lý thuyết số}}
{{Kiểm soát tính nhất quán}}
{{Sao bài viết tốt|phiên bản được chọn=63747875|thời gian=3 tháng 9 năm 2020}}

[[Thể loại:Số nguyên tố]]
[[Thể loại:Lý thuyết số]]
[[Thể loại:Chuỗi số nguyên]]