Số nguyên tố

là số tự nhiên chỉ chia hết cho 1 và chính nó

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

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.

Ký hiệu "b mid a" nghĩa là b là ước của a, ký hiệu a vdots b nghĩa là a chia hết cho b.

1. Ước tự nhiên khác 1 nhỏ nhất của một số tự nhiên là 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 đó

3. Nếu tích của nhiều số 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.

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

5. 2 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 ¹ 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. Lưu ý khái niệm đếm được trong toán học khác với ngôn ngữ đời thường, một tập hợp có vô hạn phần tử vẫn có khả năng đếm đượ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. Ta có n chia hết cho (k1+1)(k2+1)...(km+1) số tự nhiên. Ví dụ:

300 = 22.52.3

300 chia hết cho (2+1)(2+1)(1+1)=18 số tự nhiên.

1. Giả thiết 1: Không có số nguyên dương X 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ó Y > X sẽ buộc phải chia hết cho các số nguyên nhỏ hơn hoặc bằng X

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ính được đến tháng 9 năm 2008 là số nguyên tố Mersenne thứ 45 (hay 46 nếu tính cả số 1) với 12,978,189 chữ số[3]:

243,112,609 − 1..

Năm 1742, nhà toán học Đức 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 5 đề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 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ô 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, bài toán Goldbach-Euler vẫn chưa giải được hoàn toàn. Nếu mệnh đề của Euler là đúng, hãy chứng minh mệnh đề Goldbach. 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:

1. Trường hợp 1: Nếu n chẵn thì n=2+m với m chẵn, m>3. vì số chẵn >2 kế tiếp là 4 nên dù là m>3 thì m vẫn viết được dưới dạnng tổng 2 số nguyên tố.

2. Trường hợp 2: nếu n lẻ thì n=3+m với m chẵn, m>2. Theo mệnh đề Euler, 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ố.

• Hợp số
• Định lý Wilson
• Kiểm tra tính nguyên tố
• Định lý nhỏ Fermat
• Fermat
• Mersenne
• Ramanujan
• Giả thiết Goldbach-Euler
• Định lý cơ bản của số học
• Bảng số nguyên tố
• Số siêu phức