Bài viết thảo luận về khái niệm số nguyên tố và hợp số. Định nghĩa của những con số như vậy được đưa ra với các ví dụ. Chúng tôi trình bày một chứng minh rằng số lượng số nguyên tố là không giới hạn và chúng tôi sẽ ghi nó vào bảng số nguyên tố bằng phương pháp của Eratosthenes. Bằng chứng sẽ được đưa ra để xác định xem một số là số nguyên tố hay hợp số.
Yandex.RTB RA-339285-1
Số nguyên tố và số tổng hợp - Định nghĩa và ví dụ
Số nguyên tố và số tổng hợp được phân loại là số nguyên dương. Họ phải lớn hơn một. Các ước số cũng được chia thành đơn giản và tổng hợp. Để hiểu khái niệm hợp số, trước tiên bạn phải nghiên cứu khái niệm về ước số và bội số.
Định nghĩa 1
Số nguyên tố là số nguyên lớn hơn 1 và có hai ước số dương là chính nó và 1.
Định nghĩa 2
Số tổng hợp là số nguyên lớn hơn một và có ít nhất ba ước số dương.
Một không phải là số nguyên tố cũng không phải là số tổng hợp. Nó chỉ có một ước số dương nên nó khác với mọi số dương khác. Tất cả các số nguyên dương được gọi là số tự nhiên, nghĩa là được sử dụng trong việc đếm.
Định nghĩa 3
số nguyên tố là các số tự nhiên chỉ có hai ước số dương.
Định nghĩa 4
Hợp số là số tự nhiên có nhiều hơn hai ước số dương.
Bất kỳ số nào lớn hơn 1 đều là số nguyên tố hoặc hợp số. Từ tính chất chia hết ta có 1 và số a sẽ luôn là ước của mọi số a, nghĩa là nó sẽ chia hết cho chính nó và cho 1. Hãy đưa ra định nghĩa về số nguyên.
Định nghĩa 5
Các số tự nhiên không phải là số nguyên tố gọi là hợp số.
Các số nguyên tố: 2, 3, 11, 17, 131, 523. Chúng chỉ chia hết cho chính nó và 1. Số tổng hợp: 6, 63, 121, 6697. Tức là số 6 có thể phân tách thành 2 và 3, 63 thành 1, 3, 7, 9, 21, 63 và 121 thành 11, 11, tức là các ước của nó sẽ là 1, 11, 121. Số 6697 được phân tách thành 37 và 181. Lưu ý rằng khái niệm số nguyên tố và số nguyên tố cùng nhau là những khái niệm khác nhau.
Để sử dụng số nguyên tố dễ dàng hơn, bạn cần sử dụng bảng:
Một bảng cho tất cả các số tự nhiên hiện có là không thực tế, vì chúng có vô số số tự nhiên. Khi các con số đạt kích thước 10000 hoặc 1000000000 thì bạn nên cân nhắc sử dụng Sàng Eratosthenes.
Hãy xem xét định lý giải thích phát biểu cuối cùng.
Định lý 1
Ước số dương nhỏ nhất khác 1 của số tự nhiên lớn hơn 1 là số nguyên tố.
Bằng chứng 1
Giả sử a là số tự nhiên lớn hơn 1, b là ước số nhỏ nhất không phải một của a. Cần chứng minh b là số nguyên tố bằng phương pháp phản chứng.
Giả sử b là hợp số. Từ đây chúng ta có ước số cho b, nó khác với 1 cũng như với b. Số chia như vậy được ký hiệu là b 1. Cần có điều kiện 1< b 1 < b đã hoàn thành.
Từ điều kiện rõ ràng a chia hết cho b, b chia hết b 1, nghĩa là khái niệm chia hết được thể hiện như sau: a = bq và b = b 1 · q 1 , từ đó a = b 1 · (q 1 · q) , trong đó q và q 1 là số nguyên. Theo quy tắc nhân các số nguyên, ta có tích của các số nguyên là một số nguyên có đẳng thức có dạng a = b 1 · (q 1 · q) . Có thể thấy rằng b 1 là ước số của số a. Bất bình đẳng 1< b 1 < b Không tương ứng, vì ta thấy b là ước số dương nhỏ nhất và khác 1 của a.
Định lý 2
Có vô số số nguyên tố.
Bằng chứng 2
Giả sử chúng ta lấy một số hữu hạn các số tự nhiên n và ký hiệu chúng là p 1, p 2, …, p n. Hãy xem xét tùy chọn tìm số nguyên tố khác với số được chỉ định.
Ta xét số p, nó bằng p 1, p 2, ..., p n + 1. Nó không bằng mỗi số tương ứng với các số nguyên tố có dạng p 1, p 2, ..., p n. Số p là số nguyên tố. Khi đó định lý được coi là đã được chứng minh. Nếu là hợp số thì cần lấy ký hiệu pn + 1 và chứng minh rằng số chia không trùng với bất kỳ p 1, p 2, ..., p n nào.
Nếu không thì dựa vào tính chất chia hết của tích p 1, p 2, ..., p n , chúng ta thấy rằng nó sẽ chia hết cho p n + 1. Lưu ý rằng biểu thức p n + 1 chia số p bằng tổng p 1, p 2, ..., p n + 1. Chúng ta thu được biểu thức p n + 1 Số hạng thứ hai của tổng này, bằng 1, phải được chia, nhưng điều này là không thể.
Có thể thấy rằng bất kỳ số nguyên tố nào cũng có thể được tìm thấy trong số bất kỳ số nguyên tố đã cho nào. Suy ra có vô số số nguyên tố.
Vì có rất nhiều số nguyên tố nên các bảng được giới hạn ở các số 100, 1000, 10000, v.v.
Khi biên soạn một bảng số nguyên tố, bạn nên lưu ý rằng tác vụ đó yêu cầu kiểm tra tuần tự các số, bắt đầu từ 2 đến 100. Nếu không có ước số thì ghi vào bảng; nếu là hợp số thì không đưa vào bảng.
Chúng ta hãy nhìn vào nó từng bước một.
Nếu bắt đầu bằng số 2 thì nó chỉ có 2 ước: 2 và 1, tức là có thể nhập vào bảng. Tương tự với số 3. Số 4 là hợp số; nó phải được phân tách thành 2 và 2. Số 5 là số nguyên tố, nghĩa là nó có thể được ghi vào bảng. Làm như vậy cho đến số 100.
Phương pháp này bất tiện và tốn thời gian. Có thể tạo một bảng, nhưng bạn sẽ phải mất rất nhiều thời gian. Cần sử dụng tiêu chí chia hết sẽ đẩy nhanh quá trình tìm ước số.
Phương pháp sử dụng sàng Eratosthenes được coi là thuận tiện nhất. Hãy xem các bảng dưới đây làm ví dụ. Để bắt đầu, các số 2, 3, 4, ..., 50 được viết ra.
Bây giờ bạn cần gạch bỏ tất cả các số là bội số của 2. Thực hiện các đòn tấn công liên tiếp. Chúng tôi nhận được một bảng như:
Chúng ta chuyển sang gạch bỏ các số là bội số của 5. Chúng tôi nhận được:
Gạch bỏ các số là bội số của 7, 11. Cuối cùng, cái bàn trông giống như
Chúng ta hãy chuyển sang việc xây dựng định lý.
Định lý 3
Ước số dương nhỏ nhất và khác 1 của số cơ sở a không vượt quá a, trong đó a là căn số học của số đã cho.
Bằng chứng 3
Cần ký hiệu b là ước số nhỏ nhất của hợp số a. Tồn tại một số nguyên q, trong đó a = b · q, và ta có b ≤ q. Sự bất bình đẳng về hình thức là không thể chấp nhận được b > q, vì điều kiện bị vi phạm. Cả hai vế của bất đẳng thức b ≤ q phải được nhân với bất kỳ số dương b nào không bằng 1. Chúng ta nhận được b · b ≤ b · q, trong đó b 2 ≤ a và b ≤ a.
Từ định lý đã được chứng minh, rõ ràng việc gạch bỏ các số trong bảng dẫn đến việc cần phải bắt đầu bằng một số bằng b 2 và thỏa mãn bất đẳng thức b 2 ≤ a. Nghĩa là, nếu bạn gạch bỏ các số là bội số của 2 thì quá trình bắt đầu bằng 4 và bội số của 3 với 9, v.v. cho đến 100.
Việc biên soạn một bảng như vậy bằng định lý Eratosthenes cho thấy rằng khi tất cả các hợp số bị gạch bỏ, các số nguyên tố sẽ vẫn không vượt quá n. Trong ví dụ có n = 50, chúng ta có n = 50. Từ đó ta thấy sàng Eratosthenes sàng lọc ra tất cả các hợp số có giá trị không lớn hơn giá trị căn bậc 50. Việc tìm kiếm số được thực hiện bằng cách gạch bỏ.
Trước khi giải, bạn cần tìm hiểu xem số đó là số nguyên tố hay hợp số. Tiêu chí phân chia thường được sử dụng. Hãy xem xét điều này trong ví dụ dưới đây.
ví dụ 1
Chứng minh rằng số 898989898989898989 là hợp số.
Giải pháp
Tổng các chữ số của một số đã cho là 9 8 + 9 9 = 9 17. Điều này có nghĩa là số 9 · 17 chia hết cho 9, dựa trên phép thử chia hết cho 9. Theo sau đó nó là hỗn hợp.
Những dấu hiệu như vậy không thể chứng minh được tính nguyên tố của một số. Nếu cần xác minh thì cần thực hiện các hành động khác. Cách phù hợp nhất là liệt kê các con số. Trong quá trình này, số nguyên tố và số tổng hợp có thể được tìm thấy. Nghĩa là, các số không được vượt quá giá trị a. Nghĩa là số a phải được phân tích thành thừa số nguyên tố. nếu điều này được thỏa mãn thì số a có thể được coi là số nguyên tố.
Ví dụ 2
Xác định hợp số hoặc số nguyên tố 11723.
Giải pháp
Bây giờ bạn cần tìm tất cả các ước số của số 11723. Cần đánh giá 11723.
Từ đây chúng ta thấy rằng 11723< 200 , то 200 2 = 40 000 và 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Để ước tính chính xác hơn số 11723, bạn cần viết biểu thức 108 2 = 11 664 và 109 2 = 11 881 , Cái đó 108 2 < 11 723 < 109 2 . Theo đó 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Khi khai triển ta thấy 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, 101, 103, 107 đều là số nguyên tố. Toàn bộ quá trình này có thể được mô tả dưới dạng chia theo một cột. Tức là chia 11723 cho 19. Số 19 là một trong những thừa số của nó, vì chúng ta có phép chia không có số dư. Hãy biểu diễn phép chia dưới dạng một cột:
Theo đó, 11723 là một số tổng hợp, vì ngoài chính nó và 1, nó còn có ước số là 19.
Trả lời: 11723 là một số tổng hợp.
Nếu bạn thấy văn bản có lỗi, vui lòng đánh dấu nó và nhấn Ctrl+Enter
số nguyên tố là số tự nhiên (số nguyên dương), chỉ chia hết cho hai số tự nhiên: cho và bởi chính nó. Nói cách khác, số nguyên tố có đúng hai ước số tự nhiên: và chính số đó.
Theo định nghĩa, tập hợp tất cả các ước số của một số nguyên tố là hai phần tử, tức là đại diện cho một bộ.
Tập hợp tất cả các số nguyên tố được ký hiệu bằng ký hiệu. Như vậy, theo định nghĩa của tập hợp số nguyên tố, ta có thể viết: .
Chuỗi số nguyên tố trông như thế này:
Định lý cơ bản của số học
Định lý cơ bản của số học phát biểu rằng mọi số tự nhiên lớn hơn một có thể được biểu diễn dưới dạng tích của các số nguyên tố và theo một cách duy nhất, tùy theo thứ tự của các thừa số. Vì vậy, số nguyên tố là “khối xây dựng” cơ bản của tập hợp số tự nhiên.
Tiêu đề mở rộng số tự nhiên="Được kết xuất bởi QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} kinh điển:
đâu là số nguyên tố, và . Ví dụ: khai triển chuẩn của một số tự nhiên trông như thế này: .
Biểu diễn một số tự nhiên dưới dạng tích các số nguyên tố còn gọi là phân tích một số.
Thuộc tính của số nguyên tố
Sàng Eratosthenes
Một trong những thuật toán nổi tiếng nhất để tìm kiếm và nhận dạng số nguyên tố là sàng Eratosthenes. Vì vậy thuật toán này được đặt theo tên của nhà toán học Hy Lạp Eratosthenes ở Cyrene, người được coi là tác giả của thuật toán.
Để tìm tất cả các số nguyên tố nhỏ hơn một số cho trước, theo phương pháp của Eratosthenes, bạn cần làm theo các bước sau:
Bước 1. Viết tất cả các số tự nhiên từ 2 đến , tức là .
Bước 2. Gán cho biến giá trị , tức là giá trị bằng số nguyên tố nhỏ nhất.
Bước 3. Gạch bỏ trong danh sách tất cả các số từ đến đó là bội số của , tức là các số: .
Bước 4. Tìm số không bị gạch chéo đầu tiên trong danh sách lớn hơn , và gán giá trị của số này cho một biến.
Bước 5. Lặp lại bước 3 và 4 cho đến khi đạt được số lượng.
Quá trình áp dụng thuật toán sẽ như thế này:
Tất cả các số chưa gạch chéo còn lại trong danh sách khi kết thúc quá trình áp dụng thuật toán sẽ là tập hợp các số nguyên tố từ đến .
giả thuyết Goldbach
Bìa cuốn sách “Chú Petros và giả thuyết Goldbach”
Mặc dù thực tế là các số nguyên tố đã được các nhà toán học nghiên cứu từ khá lâu nhưng cho đến nay vẫn còn nhiều vấn đề liên quan chưa được giải quyết. Một trong những vấn đề chưa được giải quyết nổi tiếng nhất là Giả thuyết của Goldbach, được biểu diễn như sau:
- Có đúng là mọi số chẵn lớn hơn hai đều có thể được biểu diễn dưới dạng tổng của hai số nguyên tố (giả thuyết nhị phân của Goldbach) không?
- Có đúng là mọi số lẻ lớn hơn 5 đều có thể được biểu diễn dưới dạng tổng của ba số nguyên tố (giả thuyết ba số của Goldbach) không?
Cần phải nói rằng giả thuyết Goldbach bậc ba là trường hợp đặc biệt của giả thuyết Goldbach nhị phân, hay như các nhà toán học nói, giả thuyết Goldbach bậc ba yếu hơn giả thuyết Goldbach nhị phân.
Giả thuyết của Goldbach được biết đến rộng rãi bên ngoài cộng đồng toán học vào năm 2000 nhờ vào chiến dịch tiếp thị quảng cáo của các công ty xuất bản Bloomsbury USA (Mỹ) và Faber và Faber (Anh). Các nhà xuất bản này sau khi phát hành cuốn sách “Giả thuyết của Bác Petros và Goldbach” hứa sẽ trao giải thưởng trị giá 1 triệu đô la Mỹ cho bất kỳ ai chứng minh được giả thuyết của Goldbach trong vòng 2 năm kể từ ngày xuất bản cuốn sách. Đôi khi giải thưởng được đề cập từ các nhà xuất bản bị nhầm lẫn với giải thưởng giải quyết các vấn đề về Giải thưởng Thiên niên kỷ. Đừng nhầm lẫn, giả thuyết của Goldbach không được Viện Clay xếp vào loại “thách thức thiên niên kỷ”, mặc dù nó có liên quan mật thiết đến giả thuyết Riemann- một trong những “thách thức thiên niên kỷ”.
Cuốn sách “Số nguyên tố. Con đường dài đến vô tận"
Bìa cuốn sách “Thế giới toán học. Số nguyên tố. Con đường dài đến vô tận"
Ngoài ra, tôi khuyên bạn nên đọc một cuốn sách khoa học phổ thông hấp dẫn, có chú thích: “Việc tìm kiếm số nguyên tố là một trong những bài toán nghịch lý nhất trong toán học. Các nhà khoa học đã cố gắng giải quyết nó trong nhiều thiên niên kỷ, nhưng ngày càng có nhiều phiên bản và giả thuyết mới, bí ẩn này vẫn chưa được giải đáp. Sự xuất hiện của các số nguyên tố không phụ thuộc vào bất kỳ hệ thống nào: chúng xuất hiện một cách tự phát trong chuỗi số tự nhiên, bỏ qua mọi nỗ lực của các nhà toán học nhằm xác định các mẫu trong chuỗi của chúng. Cuốn sách này sẽ cho phép người đọc theo dõi sự tiến triển của các khái niệm khoa học từ thời cổ đại cho đến ngày nay và giới thiệu những lý thuyết thú vị nhất về việc tìm kiếm số nguyên tố.”
Ngoài ra, tôi sẽ trích dẫn phần mở đầu chương hai của cuốn sách này: “Số nguyên tố là một trong những chủ đề quan trọng đưa chúng ta trở lại nguồn gốc của toán học, và sau đó, theo con đường ngày càng phức tạp, đưa chúng ta đi đầu trong lĩnh vực toán học.” Khoa học hiện đại. Vì vậy, sẽ rất hữu ích khi theo dõi lịch sử hấp dẫn và phức tạp của lý thuyết số nguyên tố: chính xác nó đã phát triển như thế nào, chính xác các sự kiện và sự thật hiện được chấp nhận rộng rãi đã được thu thập như thế nào. Trong chương này chúng ta sẽ thấy các thế hệ nhà toán học đã nghiên cứu cẩn thận các số tự nhiên như thế nào để tìm kiếm một quy tắc dự đoán sự xuất hiện của các số nguyên tố - một quy tắc ngày càng trở nên khó nắm bắt khi quá trình tìm kiếm tiến triển. Chúng ta cũng sẽ xem xét chi tiết bối cảnh lịch sử: các điều kiện làm việc của các nhà toán học và mức độ công việc của họ liên quan đến các thực hành thần bí và bán tôn giáo, hoàn toàn khác với các phương pháp khoa học được sử dụng trong thời đại chúng ta. Tuy nhiên, dần dần và đầy khó khăn, nền tảng đã được chuẩn bị cho những quan điểm mới truyền cảm hứng cho Fermat và Euler trong thế kỷ 17 và 18.”
Các số khác nhau: tự nhiên, hữu tỉ, hữu tỉ, số nguyên và phân số, dương và âm, phức và nguyên tố, lẻ và chẵn, thực, v.v. Từ bài viết này, bạn có thể tìm ra số nguyên tố là gì.
Những con số nào được gọi là “đơn giản” trong tiếng Anh?
Rất thường xuyên, học sinh thoạt nhìn không biết cách trả lời một trong những câu hỏi đơn giản nhất trong toán học, về số nguyên tố là gì. Họ thường nhầm lẫn số nguyên tố với số tự nhiên (nghĩa là những con số mà mọi người sử dụng khi đếm các đồ vật, trong khi ở một số nguồn, chúng bắt đầu bằng 0 và ở những nguồn khác là một). Nhưng đây hoàn toàn là hai khái niệm khác nhau. Số nguyên tố là số tự nhiên, tức là số nguyên và số dương lớn hơn một và chỉ có 2 ước số tự nhiên. Hơn nữa, một trong những ước số này là số đã cho và số thứ hai là một. Ví dụ: số ba là số nguyên tố vì nó không thể chia không có dư cho bất kỳ số nào ngoài chính nó và một.
Hợp sô
Ngược lại với số nguyên tố là hợp số. Chúng cũng tự nhiên, cũng lớn hơn một, nhưng không có hai mà có số ước lớn hơn. Vì vậy, ví dụ, các số 4, 6, 8, 9, v.v. là số tự nhiên, hợp số nhưng không phải là số nguyên tố. Như bạn có thể thấy, đây hầu hết là những số chẵn, nhưng không phải tất cả. Nhưng “hai” là số chẵn và là “số đầu tiên” trong dãy số nguyên tố.
Tiếp theo
Để xây dựng một chuỗi số nguyên tố, cần phải chọn từ tất cả các số tự nhiên, có tính đến định nghĩa của chúng, nghĩa là bạn cần hành động bằng mâu thuẫn. Cần xét từng số tự nhiên dương xem nó có nhiều hơn hai ước số hay không. Hãy thử xây dựng một chuỗi (chuỗi) bao gồm các số nguyên tố. Danh sách bắt đầu bằng hai, tiếp theo là ba, vì nó chỉ chia hết cho chính nó và một. Hãy xem xét số bốn. Nó có các ước số khác ngoài bốn và một không? Vâng, số đó là 2. Vậy 4 không phải là số nguyên tố. Năm cũng là số nguyên tố (nó không chia hết cho bất kỳ số nào khác, ngoại trừ 1 và 5), nhưng sáu thì chia hết. Và nói chung, nếu bạn theo dõi tất cả các số chẵn, bạn sẽ nhận thấy rằng ngoại trừ số “hai”, không có số nào là số nguyên tố. Từ đó chúng ta kết luận rằng các số chẵn, ngoại trừ hai, không phải là số nguyên tố. Một khám phá khác: tất cả các số chia hết cho ba, ngoại trừ chính ba số đó, dù chẵn hay lẻ, cũng không phải là số nguyên tố (6, 9, 12, 15, 18, 21, 24, 27, v.v.). Điều tương tự cũng áp dụng cho các số chia hết cho năm và bảy. Tất cả vô số của họ cũng không đơn giản. Hãy tóm tắt. Vì vậy, các số có một chữ số đơn giản bao gồm tất cả các số lẻ ngoại trừ một và chín, và thậm chí “hai” là số chẵn. Bản thân các số hàng chục (10, 20,... 40, v.v.) không hề đơn giản. Các số nguyên tố có hai chữ số, ba chữ số, v.v. có thể được xác định dựa trên các nguyên tắc trên: nếu chúng không có ước số nào khác ngoài chính chúng và một.
Các lý thuyết về tính chất của số nguyên tố
Có một ngành khoa học nghiên cứu tính chất của số nguyên, trong đó có số nguyên tố. Đây là một nhánh của toán học được gọi là cao hơn. Ngoài các tính chất của số nguyên, cô còn xử lý các số đại số và số siêu việt, cũng như các hàm có nguồn gốc khác nhau liên quan đến số học của các số này. Trong những nghiên cứu này, ngoài các phương pháp cơ bản và đại số, các phương pháp phân tích và hình học cũng được sử dụng. Cụ thể, “Lý thuyết số” đề cập đến việc nghiên cứu các số nguyên tố.
Số nguyên tố là “khối xây dựng” của số tự nhiên
Trong số học có một định lý gọi là định lý cơ bản. Theo đó, bất kỳ số tự nhiên nào, ngoại trừ một số, đều có thể được biểu diễn dưới dạng tích, các thừa số của nó là số nguyên tố và thứ tự của các thừa số là duy nhất, nghĩa là phương pháp biểu diễn cũng là duy nhất. Người ta gọi là phân tích một số tự nhiên thành thừa số nguyên tố. Có một tên khác cho quá trình này - phân tích các số. Dựa vào đó, số nguyên tố có thể được gọi là “vật liệu xây dựng”, “khối” để xây dựng số tự nhiên.
Tìm kiếm số nguyên tố. Kiểm tra đơn giản
Nhiều nhà khoa học ở các thời điểm khác nhau đã cố gắng tìm ra một số nguyên tắc (hệ thống) để tìm danh sách các số nguyên tố. Khoa học biết đến các hệ thống gọi là sàng Atkin, sàng Sundartham và sàng Eratosthenes. Tuy nhiên, chúng không tạo ra bất kỳ kết quả quan trọng nào và một phép thử đơn giản được sử dụng để tìm các số nguyên tố. Các nhà toán học cũng tạo ra các thuật toán. Chúng thường được gọi là kiểm tra tính nguyên thủy. Ví dụ, có một bài kiểm tra do Rabin và Miller phát triển. Nó được sử dụng bởi các nhà mật mã. Ngoài ra còn có bài kiểm tra Kayal-Agrawal-Sasquena. Tuy nhiên, mặc dù có đủ độ chính xác nhưng rất khó tính toán, làm giảm ý nghĩa thực tiễn của nó.
Tập hợp số nguyên tố có giới hạn không?
Nhà khoa học Hy Lạp cổ đại Euclid đã viết trong cuốn sách “Các phần tử” của mình rằng tập hợp các số nguyên tố là vô cùng. Anh ấy nói thế này: “Chúng ta hãy tưởng tượng một chút rằng các số nguyên tố có giới hạn. Sau đó, hãy nhân chúng với nhau và thêm một vào tích số. Số thu được là kết quả của những hành động đơn giản này không thể chia cho bất kỳ chuỗi số nguyên tố nào, vì phần còn lại sẽ luôn là một. Điều này có nghĩa là còn một số khác chưa có trong danh sách các số nguyên tố. Do đó, giả định của chúng tôi là không đúng và tập hợp này không thể có giới hạn. Bên cạnh chứng minh của Euclid, còn có một công thức hiện đại hơn được đưa ra bởi nhà toán học Thụy Sĩ thế kỷ 18 Leonhard Euler. Theo đó, tổng nghịch đảo của tổng n số đầu tiên tăng vô hạn khi số n tăng lên. Và đây là công thức của định lý liên quan đến phân bố của các số nguyên tố: (n) tăng dần theo n/ln (n).
Số nguyên tố lớn nhất là gì?
Leonard Euler cũng đã có thể tìm ra số nguyên tố lớn nhất vào thời của ông. Đây là 2 31 - 1 = 2147483647. Tuy nhiên, đến năm 2013, một số lớn nhất chính xác nhất khác trong danh sách các số nguyên tố đã được tính - 2 57885161 - 1. Nó được gọi là số Mersenne. Nó chứa khoảng 17 triệu chữ số thập phân. Như bạn có thể thấy, con số được tìm thấy bởi một nhà khoa học thế kỷ 18 nhỏ hơn con số này vài lần. Lẽ ra nó phải như vậy, bởi vì Euler thực hiện phép tính này một cách thủ công, trong khi người đương thời của chúng ta có lẽ đã được máy tính trợ giúp. Hơn nữa, con số này được lấy tại Khoa Toán học của một trong các khoa của Mỹ. Những con số được đặt theo tên nhà khoa học này đã vượt qua bài kiểm tra tính nguyên tố Luc-Lemaire. Tuy nhiên, khoa học không muốn dừng lại ở đó. Tổ chức Biên giới Điện tử, được thành lập vào năm 1990 tại Hoa Kỳ (EFF), đã đưa ra phần thưởng bằng tiền cho việc tìm ra các số nguyên tố lớn. Và nếu cho đến năm 2013, giải thưởng được trao cho những nhà khoa học tìm ra chúng trong số 1 và 10 triệu số thập phân thì ngày nay con số này đã lên tới từ 100 triệu đến 1 tỷ. Giải thưởng dao động từ 150 đến 250 nghìn đô la Mỹ.
Tên các số nguyên tố đặc biệt
Những con số được tìm thấy nhờ thuật toán do một số nhà khoa học tạo ra và vượt qua bài kiểm tra tính đơn giản được gọi là số đặc biệt. Dưới đây là một số trong số họ:
1. Merssen.
4. Cullen.
6. Mills và cộng sự.
Tính đơn giản của những con số này, được đặt theo tên của các nhà khoa học trên, được xác lập bằng các thử nghiệm sau:
1. Luc-Lemaire.
2. Pepina.
3. Riesel.
4. Billhart - Lemaire - Selfridge và những người khác.
Khoa học hiện đại không dừng lại ở đó, và có lẽ trong tương lai gần thế giới sẽ biết đến tên của những người đã có thể nhận được giải thưởng 250.000 USD khi tìm ra số nguyên tố lớn nhất.
Đếm các ước số. Theo định nghĩa, số N chỉ là số nguyên tố nếu nó không chia hết cho 2 và các số nguyên khác ngoại trừ 1 và chính nó. Công thức trên loại bỏ các bước không cần thiết và tiết kiệm thời gian: ví dụ: sau khi kiểm tra xem một số có chia hết cho 3 hay không, không cần kiểm tra xem số đó có chia hết cho 9 hay không.
- Hàm Floor(x) làm tròn x đến số nguyên gần nhất nhỏ hơn hoặc bằng x.
Tìm hiểu về số học mô-đun. Phép toán "x mod y" (mod là tên viết tắt của từ "modulo" trong tiếng Latin, nghĩa là "mô-đun") có nghĩa là "chia x cho y và tìm phần còn lại." Nói cách khác, trong số học mô đun, khi đạt đến một giá trị nhất định, giá trị đó được gọi là mô-đun, các con số lại “chuyển” về 0. Ví dụ: một chiếc đồng hồ giữ thời gian với hệ số 12: nó hiển thị 10, 11 và 12 giờ rồi quay về 1.
- Nhiều máy tính có phím mod. Phần cuối của phần này cho thấy cách đánh giá thủ công hàm này cho số lượng lớn.
Tìm hiểu về những cạm bẫy của Định lý nhỏ Fermat. Tất cả các số không đáp ứng điều kiện kiểm tra đều là hợp số, nhưng các số còn lại chỉ là số có lẽđược xếp vào loại đơn giản. Nếu bạn muốn tránh kết quả sai, hãy tìm N trong danh sách "số Carmichael" (số hỗn hợp thỏa mãn bài kiểm tra này) và "số Fermat giả nguyên tố" (những số này chỉ đáp ứng điều kiện kiểm tra đối với một số giá trị Một).
Nếu thuận tiện, hãy sử dụng phép thử Miller-Rabin. Mặc dù phương pháp này khá phức tạp khi tính toán bằng tay nhưng nó thường được sử dụng trong các chương trình máy tính. Nó cung cấp tốc độ chấp nhận được và tạo ra ít lỗi hơn phương pháp của Fermat. Hợp số sẽ không được chấp nhận là số nguyên tố nếu phép tính được thực hiện với hơn ¼ giá trị Một. Nếu bạn chọn ngẫu nhiên các giá trị khác nhau Một và đối với tất cả chúng, bài kiểm tra sẽ cho kết quả khả quan, chúng ta có thể giả định với mức độ tin cậy khá cao rằng N là một số nguyên tố.
Đối với số lượng lớn, sử dụng số học mô-đun. Nếu bạn không có sẵn máy tính có mod hoặc máy tính của bạn không được thiết kế để xử lý những số lớn như vậy, hãy sử dụng các thuộc tính lũy thừa và số học mô-đun để thực hiện các phép tính dễ dàng hơn. Dưới đây là một ví dụ cho 3 50 (\displaystyle 3^(50)) mod 50:
- Viết lại biểu thức ở dạng thuận tiện hơn: mod 50. Khi thực hiện các phép tính thủ công, có thể cần đơn giản hóa hơn nữa.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Ở đây chúng ta đã tính đến tính chất của phép nhân môđun.
- 3 25 (\displaystyle 3^(25)) mod 50 = 43.
- (3 25 (\displaystyle (3^(25)) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
- = 1849 (\displaystyle =1849) mod 50.
- = 49 (\displaystyle =49).