Mở trình đơn chính
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
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ố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, 1 × 5 hoặc 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ố (2 × 3) đều nhỏ hơn 6. Các số nguyên tố là trung tâm trong lý thuyết sốđị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à . Các thuật toán nhanh hơn bao gồm 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ư các số nguyen tố Mersenne. Tính đến tháng 12 năm 2018 số nguyên tố lớn nhất được biết có 23 249 425 chữ số.

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 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 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 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 đạ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ã khóa công khai, dựa trên khó khăn trong việc 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áchSửa đổi

Các số nguyên tố từ   đến  :

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.[1]

Số   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à  , thì ta sẽ có  , theo định nghĩa số chẵn. Rõ ràng   là các số đôi một phân biệt nên   phải có ít nhất ba ước số, đó là  , mâu thuẫn.

Tính chấtSửa đổi

Ký hiệu " " nghĩa là   là ước của  .

1. Ước tự nhiên khác   nhỏ nhất của một số tự nhiên là số nguyên tố.

Chứng minh: Giả sử  ;   nhỏ nhất;  .

Nếu   không nguyên tố  

  với  : mâu thuẫn với   nhỏ nhất. Vậy   là nguyên tố.

2. Cho   là số nguyên tố;  . Khi đó

 
 

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

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

4. Ước số dương bé nhất khác   của một hợp số   là một số nguyên tố không vượt quá  

5.   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ố: p1 < p2 <... < pn

Xét a = p1.p2.... pn+1

Ta có: a > 1 và a khác pi với mọi i từ 1 đến n => a là hợp số => a có ước nguyên tố pi hay a chia hết cho pi, mà p1p2...pn chia hết chi pi => 1 chia hết cho pi, mâu thuẫn vì pi 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 EratostheneSửa đổi

Sàng EratostheneSửa đổi

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

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

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

Định lý cơ bản của số họcSửa đổi

Phát biểu định lý: "Mọi số tự nhiên lớn hơn   đề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à:

 

Trong đó  , là các số nguyên tố đôi một khác nhau. Ta có   chia hết cho   số tự nhiên. Ví dụ:

 

  chia hết cho   số tự nhiên.

Đây cũng là công thức tính số các ước của số tự nhiên  : Số các ước  

Số nguyên tố Fermat và MersenneSửa đổi

Sự tồn tại của số nguyên tố lớn nhấtSửa đổi

  1. Giả thiết 1: Không có số nguyên dương   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ó   sẽ buộc phải chia hết cho các số nguyên nhỏ hơn hoặc bằng  
  2. Giả thiết 2: số vô cùng lớn   không thể xác định là số nguyên tố hay hợp số
  3. 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ứ   với   chữ số:[2]

 

Giả thiết Goldbach - EulerSửa đổi

Năm 1742, nhà toán học Đức Christian Goldbach viết thư cho 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   đề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   đề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  , ta sẽ chứng minh rằng   viết được dưới dạng tổng của 3 số nguyên tố. Xét:

  1. Trường hợp 1: Nếu   chẵn thì   với   chẵn và lớn hơn  . vì số chẵn lớn hơn   kế tiếp là   nên dù là   thì   vẫn viết được dưới dạng tổng 2 số nguyên tố.
  2. Trường hợp 2: nếu   lẻ thì   với   chẵn và lớn hơn  . Theo mệnh đề Euler, do   chẵn và lớn hơn   nên   có thể viết được dưới dạng tổng hai số nguyên tố. Do đó   viết được dưới dạng tổng của 3 số nguyên tố.

Chú thíchSửa đổi

  1. ^ (dãy số A000040 trong bảng OEIS).
  2. ^ “List of known Mersenne prime numbers”. Truy cập ngày 6 tháng 1 năm 2018. 

Xem thêmSửa đổi

Liên kết ngoàiSửa đổi