Số nguyên tố
Bách khoa toàn thư mở Wikipedia
Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chia hết cho chính nó.
- Ví dụ: 2, 3, 5, 7, 11..
Mục lục |
[sửa] Tính chất
Ký hiệu "b a" nghĩa là b là ước của a, ký hiệu a
b nghĩa là a chia hết cho b.
1. Ước số nhỏ nhất khác 1 của một số tự nhiên a > 1 là một số nguyên tố.
Chứng minh: Giả sử d a; d nhỏ nhất; d
1.
Nếu d không nguyên tố d = d1.d2; d1, d2 > 1
d1|a với d1 < d: mâu thuẫn với d nhỏ nhất. Vậy d là nguyên tố.
2. Cho p là số nguyên tố; a N; a
0. Khi đó
- (a,p) = p
(a
p)
- (a,p) = 1
(a
p)
3. Nếu tích chia hết cho một số nguyên tố p thì có ít nhất một thừa số chia hết cho p.
-
-
p
ai
p
-
4. Ước số dương bé nhất khác 1 của một hợp số a > 1 là một số nguyên tố không vượt quá .
Chứng minh: Giả sử p là ước dương bé nhất khác 1 của a. Theo tính chất 2 Þ p là nguyên tố. Ta lại có: a = p.a1, do a1 là một ước dương của a Þ a1 ³ p.
Þ a = p.a1 ³ p2 Þ p £ .
5. Tập hợp các số nguyên tố là vô hạn.
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 ¹ pi; "i = Þ a là hợp số Þ a có ước nguyên tố pi,
hay aMpi và ( pi) M pi Þ 1M pi: mâu thuẫn.
Vậy tập hợp các số nguyên tố là vô hạn.
- Tuy nhiên, vì tập hợp số nguyên tố là tập con của số tự nhiên, mà tập hợp số tự nhiên là đếm được nên tập hợp các số nguyên tố là đếm được.
[sửa] Bảng số nguyên tố-sàng Eratosthene
[sửa] Sàng Eratosthene
Sàng Eratosthene là một giải thuật cổ xưa để lập bảng tất cả các số nguyên tố nhỏ hơn một số n cho trước. Giải thuật dựa trên tính chất: mọi hợp số m đều có ước nguyên tố không vượt quá . 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ố
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 Prime[k]:= True while k*j<=n { Prime[k*j]:= False j:=j+1 } } }
[sửa] Lịch sử các bảng số nguyên tố
[sửa] Đị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 1 đề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 đó p1,p2,...,pm, là các số nguyên tố đôi một khác nhau. Ví dụ:
-
- 300 = 22.52.3
[sửa] Bài toán xác định số nguyên tố thứ n
[sửa] Số nguyên tố thứ n
[sửa] Định lý số nguyên tố
[sửa] Sự phân bố số nguyên tố
[sửa] Số nguyên tố Fermat và Mersenne
[sửa] Giả thiết Goldbach - Euler
Năm 1742, nhà toán học Đức Goldbach viết thư cho Ơ-le 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 5 đều biểu diễn được dưới dạng tổng của 3 số nguyên tố. Ơ-le trả lời rằng theo ông, mọi số chẵn lớn hơn 2 đề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ô Vi-nô-gra-đốp đã 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, bài toán Goldbach-Euler vẫn chưa giải được hoàn toàn. Nếu mệnh đề của Ơ-le là đúng, hãy chứng minh mệnh đề Gôn-bách. Giải: Cho số tự nhiên n>5, ta sẽ chứng minh rằng n 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 n chẵn thì n=2+m với m chẵn, m>3.
- Trường hợp 2: nếu n lẻ thì n=2+m với m chẵn, m>2. Theo mệnh đề Ơ-le, m chẵn, m>2 nên m viết được dưới dạng tổng hai số nguyên tố. Do đó n viết được dưới dạng tổng của 3 số nguyên tố.
[sửa] Xem thêm
- Hợp số
- Định lý Wilson
- Kiểm tra tính nguyên tố
- Định lý nhỏ Fermat
- Số nguyên tố Fermat
- Số nguyên tố Mersenne
- Số nguyên tố Ramanujan
- Giả thiết Goldbach-Euler
- Định lý cơ bản của số học
- Bảng số nguyên tố
[sửa] Liên kết ngoài
- Bài giảng lý thuyết số nguyên tố của Bùi Anh Kiệt tại trường Đại học Cần Thơ
- Trang web số nguyên tố
- Lịch sử nghiên cứu số nguyên tố
- Prime Number Generator - Generate a given number of primes above a given start number.
- 15, 000, 000 số nguyên tố đầu tiên
- The prime puzzles
- Phiên bản tiếng Anh của định lý Euclid về giới hạn số nguyên tố
- Số nguyên tố trên WIMS
- Vòng số với họa tiết tạo bởi phân bố số nguyên tố
- An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier
- Factorizer Windows software to find prime numbers and pairs of prime numbers less than 2,147,483,646.
- A fast, downloadable prime number calculator written in Visual Basic 6