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

[[Tập tin:Primes-vs-composites.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ỏ| Các số nguyên tố là các số tự nhiên lớn hơn 1 và không phải là tích của hai số tự nhiên nhỏ hơn.]]
'''Số nguyên tố''' là [[số tự nhiên]] lớn hơn 1 không thể được hình thành bằng cách nhân hai số tự nhiên nhỏ hơn. Số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là [[hợp số]]. Ví dụ: 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ó số hạng 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}}) đều nhỏ hơn 6. Các [[Lý thuyết số|số]] [[Định lý cơ bản của số học|nguyên tố]] là trung tâm trong [[lý thuyết số]] vì [[định lý cơ bản của số học]]: mọi số tự nhiên lớn hơn 1 đều là số nguyên tố hoặc có thể được [[phân tích nhân tử]] thành tích của các số nguyên tố mà là duy nhất theo thứ tự của chúng.

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

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

Một số câu hỏi lịch sử liên quan đến số nguyên tố vẫn chưa được giải quyết. Chúng bao gồm [[Giả thuyết Goldbach|giả thuyết của Goldbach]], rằng mọi số nguyên chẵn lớn hơn 2 có thể được biểu diễn dưới dạng tổng của hai số nguyên tố và phỏng đoán [[Số nguyên tố sinh đôi|nguyên tố sinh đôi]], rằng có vô số cặp số nguyên tố chỉ có một số chẵn giữa chúng. Những câu hỏi như vậy đã thúc đẩy sự phát triển của các nhánh khác nhau của lý thuyết số, tập trung vào các khía cạnh phân tích hoặc [[Lý thuyết số đại số|đại số]] của các con số. Các số nguyên tố được sử dụng trong một số quy trình trong [[công nghệ thông tin]], chẳng hạn như [[Mật mã hóa khóa công khai|mật mã khóa công khai]], dựa trên khó khăn trong việc [[Phân tích số nguyên|phân tích]] các số nguyên lớn thành các nhân tử của chúng. Trong [[đại số trừu tượng]], các đối tượng hành xử theo cách tổng quát như số nguyên tố bao gồm các phần tử nguyên tố và ideal nguyên tố.

==Danh sách==
{{bài chi tiết|Danh sách số nguyên tố}} 
Các số nguyên tố từ 2 đến 100:
<!--Do not add 1 to this list. Its exclusion from the list is addressed in the "History of prime numbers" section below.-->:[[2]], [[3]], [[5]], [[7]], [[11]], [[13]], [[17]], [[19]], [[23]], [[29]], [[31]], [[37]], [[41]], [[43]], [[47]], [[53]], [[59]], [[61]], [[67]], [[71]], [[73]], [[79]], [[83]], [[89]], [[97]].<ref>{{OEIS|id=A000040}}.</ref>

Số 2 là số nguyên tố nhỏ nhất, và cũng là số nguyên tố chẵn duy nhất. Thật vậy, nếu tồn tại một số nguyên tố chẵn khác, gọi là <math>p\;\;(p>2)</math>, thì ta sẽ có <math>2\mid p</math>, theo định nghĩa số chẵn. Rõ ràng 1,2,p là các số đôi một phân biệt nên p phải có ít nhất ba ước số, đó là 1,2,p, mâu thuẫn.

== Tính chất ==
Ký hiệu "<math>b\mid a </math>" nghĩa là <math>b </math> là ước của <math>a </math>.

'''1.''' [[Ước số|Ước]] tự nhiên khác <math>1</math> nhỏ nhất của một số tự nhiên là số nguyên tố.

Chứng minh: Giả sử <math>d\mid a </math>; <math>d </math> nhỏ nhất; <math>d\ne1</math>.

Nếu <math>d </math> không nguyên tố <math>\Rightarrow d=d_1d_2;\;d_1,d_2>1.</math>

<math>\Rightarrow d_1\mid a</math> với <math>d_1<d</math>: mâu thuẫn với <math>d </math> nhỏ nhất. Vậy <math>d </math> là nguyên tố.

'''2.''' Cho <math>p</math> là số nguyên tố; <math>a\in\mathbb{N};a\ne0</math>. Khi đó
:<math>(a,p)=p\Leftrightarrow p\mid a</math>
:<math>(a,p)=1\Leftrightarrow p\not\mid a</math>

'''3.''' Nếu tích của nhiều số chia hết cho một số nguyên tố <math>p</math> thì có ít nhất một thừa số chia hết cho <math>p</math>.

:[[Tập tin:Animation Sieb des Eratosthenes (vi).gif|nhỏ|phải|662x662px| Hình minh họa cho thấy thuật toán đơn giản để tìm số nguyên tố và các bội số<br /> Các số tô màu giống nhau là cùng một họ mà dẫn đầu (đậm hơn) sẽ là số nguyên tố]]
::<math>p\mid\prod_{i=1}^N a_i\Rightarrow(\exists a_i\Rightarrow p\mid a_i)</math>

'''4.''' Ước số dương bé nhất khác <math>1</math> của một hợp số <math>a </math> là một số nguyên tố không vượt quá <math>\sqrt{a}</math>

'''5.''' <math>2</math> là số nguyên tố nhỏ nhất và cũng là số nguyên tố chẵn duy nhất

'''6.''' Tập hợp các số nguyên tố là vô hạn (tương đương với việc không có số nguyên tố lớn nhất).

Chứng minh: Giả sử có hữu hạn số nguyên tố: p<sub>1</sub> < p<sub>2</sub> <... < p<sub>n</sub>

Xét a = p<sub>1</sub>.p<sub>2</sub>.... p<sub>n</sub>+1

Ta có: a > 1 và a khác p<sub>i</sub> với mọi i từ 1 đến n 
=> a là hợp số => a có ước nguyên tố p<sub>i</sub> hay a chia hết cho p<sub>i</sub>, mà p<sub>1</sub>p<sub>2</sub>...p<sub>n</sub> chia hết chi p<sub>i</sub> => 1 chia hết cho p<sub>i</sub>, mâu thuẫn vì p<sub>i</sub> là số nguyên tố.

Vậy [[tập hợp]] các số nguyên tố là vô hạn.

== Bảng số nguyên tố-sàng Eratosthene ==
=== Sàng Eratosthene ===
{{chính|Sàng Eratosthenes}}
[[Sàng Eratosthenes]] là một [[thuật toán|giải thuật]] cổ xưa để lập bảng tất cả các số nguyên tố nhỏ hơn một số <math>n </math> cho trước. Giải thuật dựa trên tính chất: mọi hợp số <math>n </math> đều có ước nguyên tố không vượt quá căn của chính nó (<math>\sqrt{n} </math>).
Giải thuật đầu tiên xóa số 1 ra khỏi tập các số nguyên tố.
Số tiếp theo số 1 là số 2, là số nguyên tố.
Bắt đầu từ số 2 xoá tất cả các bội của 2 ra khỏi bảng.
Số đầu tiên không bị xoá sau số 2 (số 3) là số nguyên tố.
Tiếp theo lại xoá các bội của 3...
Giải thuật tiếp tục cho đến khi găp số nguyên tố lớn hơn hoặc bằng sqrt(n) thì dừng lại. Tất cả các số chưa bị xoá là số nguyên tố.
Theo ngôn ngữ thuật toán ta có thể diễn đạt giải thuật sàng Eratosthene như sau:
<code>
 '''Eratosthene'''(n) 
 Var ''List'' Prime[''1..n''] 
 ''Int'' i,j,k 
 for i:=1 to n Prime[''i'']:=True
 Prime[1]:=false
 k=0
 while k < sqrt(n) {
 i=k+1
 while Prime[i]=False i:=i+1
 k=i
 j=2
 while k*j<=n { 
 Prime[k*j]:= False
 j:=j+1
 }
 } 
</code>

== Định lý cơ bản của số học==
{{Bài chi tiết|Định lý cơ bản của số học}}
Phát biểu định lý: "Mọi số tự nhiên lớn hơn <math>1</math> đều phân tích được thành tích những thừa số nguyên tố, và sự phân tích này là duy nhất nếu không kể đến thứ tự của các thừa số."

Từ đó có dạng phân tích tiêu chuẩn của một số tự nhiên bất kỳ là:
:: <math>n = p_1^{k_1}p_2^{k_2}...p_m^{k_m}</math>
Trong đó <math>p_1,p_2,...,p_m</math>, là các số nguyên tố đôi một khác nhau. Ta có <math>n </math> [[chia hết]] cho <math>\prod_{i=1}^{m}\left(k_i+1\right)=(k_1+1)(k_2+1)...(k_m+1)</math> [[số tự nhiên]].
Ví dụ:
::<math>300 = 2^2.5^2.3</math>
<math>300</math> chia hết cho <math>(2+1)(2+1)(1+1)=18</math> số tự nhiên.

Đây cũng là công thức tính số các ước của số tự nhiên <math>n </math>: Số các ước <math>=\prod_{i=1}^{m}\left(k_i+1\right)</math>

== Số nguyên tố Fermat và Mersenne ==
Xem bài viết ở:

[[Số Fermat]]

[[Số nguyên tố Mersenne]]

== Sự tồn tại của số nguyên tố lớn nhất ==
# Giả thiết 1: Không có số nguyên dương <math>X </math> nào là số nguyên tố lớn nhất, nghĩa là không [[tồn tại]] số mà các số lớn hơn nó <math>Y>X </math> sẽ buộc phải chia hết cho các số nguyên nhỏ hơn hoặc bằng <math>X </math>
# Giả thiết 2: số vô cùng lớn <math>\infty</math> không thể xác định là số nguyên tố hay hợp số
# Giả thiết 3: Lực lượng của tập hợp số nguyên tố là vô hạn đếm được
Với 3 giả thiết trên thì việc xác định số nguyên tố lớn nhất là không thể được; tuy nhiên, với khả năng tính toán của máy tính, người ta có thể tính ra được số nguyên tố (số nguyên chắc chắn là số nguyên tố) lớn nhất tìm được bằng thuật toán chạy trên máy tính. Cho đến tháng 1 năm [[2018]], số nguyên tố lớn nhất là [[số nguyên tố Mersenne]] thứ <math>50</math> với <math>23\;249\;425 </math> chữ số:<ref>{{cite web|url=https://www.mersenne.org/primes/|title=List of known Mersenne prime numbers|accessdate=6 January 2018}}</ref>
:<math>M_{50}=2^{77\;232\;917}-1 </math>

== Giả thiết Goldbach - Euler ==
Năm [[1742]], [[danh sách nhà toán học|nhà toán học]] [[Đức]] [[Christian Goldbach]] viết thư cho [[Leonhard Euler|Euler]] biết rằng ông mạo hiểm đưa ra bài toán: Mọi số tự nhiên lớn hơn <math>5 </math> đều biểu diễn được dưới dạng tổng của 3 số nguyên tố. Euler trả lời rằng theo ông, mọi số chẵn lớn hơn <math>2 </math> đều biểu diễn được dưới dạng tổng của 2 số nguyên tố.
Nếu chứng minh được một trong hai mệnh đề thì sẽ chứng minh được mệnh đề còn lại. 200 năm sau, đến năm 1937, nhà toán học [[Liên Xô]] [[Vinogradov]] đã giải quyết gần trọn vẹn bài toán đó bằng cách chứng minh rằng mọi số lẻ đủ lớn đều có thể biểu diễn được dưới dạng tổng của 3 số nguyên tố.

Cho đến nay, [[Giả thuyết Goldbach-Euler]] vẫn chưa giải được hoàn toàn.

Ta xét bài toán: Nếu mệnh đề của Euler là đúng, hãy chứng minh mệnh đề Goldbach. Lời giải cho bài toán trên như sau:

Giải: Cho số tự nhiên <math>n>5 </math>, ta sẽ chứng minh rằng <math>n </math> viết được dưới dạng tổng của 3 số nguyên tố. Xét:
# Trường hợp 1: Nếu <math>n </math> chẵn thì <math>n=2+m </math> với <math>m </math> chẵn và lớn hơn <math>3 </math>. vì số chẵn lớn hơn <math>2 </math> kế tiếp là <math>4 </math> nên dù là <math>m>3 </math> thì <math>m </math> vẫn viết được dưới dạng tổng 2 số nguyên tố.
# Trường hợp 2: nếu <math>n </math> lẻ thì <math>n=3+m </math> với <math>m </math> chẵn và lớn hơn <math>2 </math>. Theo mệnh đề Euler, do <math>m </math> chẵn và lớn hơn <math>2 </math> nên <math>m </math> có thể viết được dưới dạng tổng hai số nguyên tố. Do đó <math>n </math> viết được dưới dạng tổng của 3 số nguyên tố.

== Chú thích ==
{{Tham khảo}}
==Xem thêm==
* [[Số tự nhiên]]
* [[Số chẵn]]
* [[Số lẻ]]
* [[Số nguyên]]
* [[Phân tích số nguyên]] (ra thừa số nguyên tố)
* [[Phân số]]
* [[Số vô tỉ|Số vô tỷ]]
* [[Số hữu tỉ|Số hữu tỷ]]
* [[Số phức]]
* [[Số nguyên Gauss]]
* [[Số nguyên Eisenstein]]
* [[Số vô tỷ Quadratic]]
* [[Căn của đơn vị]]
* [[Gaussian period]]
* [[Số Pisot-Vijayaraghavan]]
* [[Số Salem]]

== Liên kết ngoài ==
{{thể loại Commons|Prime numbers}}
[[Tiếng Anh]]:
* {{Britannica|476309|Prime (number)}}
* [http://primes.utm.edu/ Trang web số nguyên tố]
* [http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html Lịch sử nghiên cứu số nguyên tố]
* [http://publicliterature.org/tools/prime_number_generator Prime Number Generator] - Generate a given number of primes above a given start number.
* [http://primes.utm.edu/lists/small/millions/ 15, 000, 000 số nguyên tố đầu tiên]
* [http://www.primepuzzles.net/ The prime puzzles]
* [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html Phiên bản tiếng Anh của định lý Euclid về giới hạn số nguyên tố]
* [http://wims.unice.fr/wims/wims.cgi?module=tool/number/primes.en Số nguyên tố trên WIMS]
* [http://www.numberspiral.com/index.html Vòng số với họa tiết tạo bởi phân bố số nguyên tố]
* [http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier]
* [http://www.hermetic.ch/factors/factors.htm Factorizer] Windows software to find prime numbers and pairs of prime numbers less than 2.147.483.646.
* [http://1falsemove.50megs.com/primespage.html A fast, downloadable prime number calculator written in Visual Basic 6]
* {{PlanetMath|prime}}
* {{MathWorld |title=Prime Number |urlname=PrimeNumber}}
{{Vi}}
* {{TĐBKVN|28067|Bảng số nguyên tố}}
{{Phân loại các số nguyên tố}}
{{Lý thuyết số}}
{{Kiểm soát tính nhất quán}}

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