Bài viết đề cập đến khái niệm số nguyên tố và hợp số. Định nghĩa của những con số như vậy với các ví dụ được đưa ra. Chúng tôi đưa ra một bằng chứng rằng số lượng các số nguyên tố là không giới hạn và tạo một mục trong bảng các số nguyên tố bằng phương pháp Eratosthenes. Các chứng minh sẽ được đưa ra về việc một số là số nguyên tố hay hợp số.
Yandex.RTB R-A-339285-1
Số nguyên tố và hỗn hợp - Định nghĩa và Ví dụ
Các số nguyên tố và hợp số được phân loại là số nguyên dương. Chúng phải lớn hơn một. Các bộ chia cũng được chia thành đơn giản và hợp chất. Để hiểu khái niệm hợp số, trước hết cần nghiên cứu khái niệm ước và bội.
Định nghĩa 1
Số nguyên tố là các số nguyên lớn hơn một và có hai ước số dương, đó là chính chúng và 1.
Định nghĩa 2
Số tổng hợp là các 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ố hay hợp số. Nó chỉ có một ước số dương, vì vậy nó khác với tất cả các số dương khác. Tất cả các số nguyên dương được gọi là tự nhiên, nghĩa là, được sử dụng để đế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ố- Cái này 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 của phép chia hết, chúng ta có 1 và số a sẽ luôn là ước cho bất kỳ số a nào, tức là nó sẽ chia hết cho chính nó và cho 1. Chúng tôi đư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ố được 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 chúng và 1. Các số tổng hợp: 6, 63, 121, 6697. Nghĩa là, số 6 có thể được chia thành 2 và 3, và 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 sẽ phân hủy thành 37 và 181. Lưu ý rằng các khái niệm về số nguyên tố và số tương đối là các 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ì có vô số số trong số chúng. Khi con số đạt đến kích thước 10000 hoặc 1000000000, thì bạn nên nghĩ đến việc sử dụng sàng của Eratosthenes.
Hãy xem xét mộ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 của một số tự nhiên lớn hơn 1 khác 1 là một 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 nhỏ nhất của a. Chúng ta phải chứng minh rằng b là một số nguyên tố bằng cách sử dụng phương pháp mâu thuẫn.
Giả sử b là hợp số. Từ đây ta có một ước cho b, khác 1 cũng như b. Một ước số như vậy được ký hiệu là b 1. Điều kiện cần là 1< b 1 < b đã được hoàn thành.
Từ điều kiện a chia hết cho b, b chia hết cho b 1, nghĩa là khái niệm chia hết được diễn đạt theo cách sau: a = b q và b = b 1 q 1, khi a = b 1 (q 1 q), trong đó q và q 1 là các số nguyên. Theo quy tắc nhân các số nguyên, ta có tích các số nguyên là một số nguyên có đẳng thức a = b 1 · (q 1 · q). Có thể thấy rằng b 1 là ước của a. Bất đẳng thức 1< b 1 < b không phải phù hợp, bởi vì ta nhận được rằng b là ước số dương nhỏ nhất khác 1 của a.
Định lý 2
Có vô hạn 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 là p 1, p 2,…, p n. Hãy xem xét một biến thể của việc tìm kiếm một số nguyên tố khác với những số đã chỉ ra.
Xét số p, tương đương với 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 nó là hợp, thì chúng ta cần lấy ký hiệu p n + 1 và hiển thị số chia không khớp với bất kỳ số nào trong số p 1, p 2,…, p n.
Nếu điều này không đúng, thì dựa trên thuộc tính chia hết của tích p 1, p 2,…, p n , chúng ta nhận được rằng nó sẽ chia hết cho p n + 1. Lưu ý rằng biểu thức p n + 1 số p bị chia bằng tổng p 1, p 2,…, p n + 1. Ta nhận được rằng 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 trong số các số nguyên tố đã cho thì có thể tìm được một số nguyên tố bất kỳ. Theo đó có vô hạn số nguyên tố.
Vì có rất nhiều số nguyên tố, 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 các số nguyên tố, người ta nên tính đến thực tế là công việc như vậy 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ó số bị chia thì nó được ghi trong bảng; nếu là số hợp thì nó không được nhập vào bảng.
Chúng ta hãy xem xét từng bước một.
Nếu bạn bắt đầu bằng số 2, thì nó chỉ có 2 ước số: 2 và 1, có nghĩa là nó có thể được nhập vào bảng. Với số 3 cũng vậy. Số 4 là hợp, nên tách thành 2 và 2. Số 5 là số nguyên tố, có nghĩa là nó có thể được cố định trong bảng. Làm điều này cho đến số 100.
Phương pháp này khó chịu và lâu. Bạn có thể làm một cái bàn, nhưng bạn phải chi một số lượng lớn thời gian. Cần sử dụng tiêu chí chia hết, điều này sẽ đẩy nhanh quá trình tìm số chia.
Phương pháp sử dụng sàng của Eratosthenes được coi là tiện lợi nhất. Hãy cùng xem các bảng dưới đây. Để bắt đầu, các số 2, 3, 4, ..., 50 được viết.
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 gạch ngang liên tiếp. Chúng tôi nhận được một bảng có dạng:
Hãy chuyển sang gạch bỏ các số là bội số của 5. Chúng tôi nhận được:
Chúng tôi gạch bỏ các số là bội số của 7, 11. Cuối cùng bảng trông như thế nào
Chúng ta hãy chuyển sang công thức của định lý.
Định lý 3
Ước số dương nhỏ nhất và không phải là 1 của số cơ số a không vượt quá a, trong đó a là căn số học của một số đã cho.
Bằng chứng 3
Cần thiết phải chỉ định b ước số nhỏ nhất hợp số a. Có một số nguyên q, trong đó a = b · q, và chúng ta có b ≤ q. Một bất đẳng thức có dạng b> q bởi vì điều kiện bị vi phạm. Cả hai vế của bất đẳng thức b ≤ q nên nhân với bất kỳ số dương b nào không bằng 1. Ta nhận được rằng b b ≤ b q, trong đó b 2 ≤ a và b ≤ a.
Có thể thấy từ định lý đã được chứng minh rằng việc xóa các số trong bảng dẫn đến việc phải bắt đầu bằng một số có giá trị 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 từ 4 và những số là bội số của 3 bắt đầu từ 9, và cứ tiếp tục lên đến 100.
Việc biên soạn một bảng như vậy bằng cách sử dụng định lý Eratosthenes nói rằng khi tất cả các số tổng hợp bị gạch bỏ, sẽ vẫn còn những số nguyên tố không vượt quá n. Trong ví dụ với n = 50, chúng ta có n = 50. Từ đây, chúng ta nhận được rằng sàng của Eratosthenes sẽ lọc ra tất cả các số tổng hợp không có giá trị lớn hơn giá trị của căn là 50. Việc tìm kiếm các số được thực hiện bằng cách gạch bỏ.
Trước khi giải, cần tìm xem số đó là số nguyên tố hay hợp số. Tiêu chí chia hết 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 89898989898989898989 là hợp số.
Quyết định
Tổng các chữ số của số đã cho là 9 8 + 9 9 = 9 17. Vậy số 9 17 chia hết cho 9 dựa vào dấu hiệu chia hết cho 9. Theo đó, nó là hỗn hợp.
Những dấu hiệu như vậy không thể chứng minh tính nguyên tố của một số. Nếu cần xác minh, các bước khác nên được thực hiện. Hầu hết cách thích hợp- Đó là một loạt các con số. Trong quá trình này, các số nguyên tố và hợp số có thể được tìm thấy. Nghĩa là, các số có giá trị không được vượt quá a. Tức là, số a phải được phân tách thành các thừa số nguyên tố. nếu điều này đúng, 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.
Quyết định
Bây giờ bạn cần tìm tất cả các ước cho 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 ít hơn số 200 .
Để ước lượng chính xác hơn số 11723, cần viết biểu thức 108 2 = 11 664, và 109 2 = 11 881 , sau đó 108 2 < 11 723 < 109 2 . Nó tiếp theo từ điều này mà 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Khi phân rã, chúng ta nhận được rằng 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à các số nguyên tố. Toàn bộ quá trình này có thể được mô tả như một sự phân chia theo một cột. Tức là, chia 11723 cho 19. Con số 19 là một trong những yếu tố của nó, vì chúng ta nhận được phép chia không có phần dư. Hãy mô tả sự phân chia theo 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ó một ước số 19.
Trả lời: 11723 là một số tổng hợp.
Nếu bạn nhận thấy lỗi trong văn bản, vui lòng đánh dấu nó và nhấn Ctrl + Enter
Trong bài này, chúng ta sẽ nghiên cứu số nguyên tố và hợp số. Đầu tiên, chúng tôi đưa ra các định nghĩa về số nguyên tố và hợp số, đồng thời đưa ra các ví dụ. Sau đó, ta chứng minh rằng có vô hạn số nguyên tố. Tiếp theo, chúng ta viết một bảng các số nguyên tố, và xem xét các phương pháp để lập một bảng các số nguyên tố, chúng ta sẽ đặc biệt chú ý đến phương pháp được gọi là sàng của Eratosthenes. Tóm lại, chúng tôi nêu ra những điểm chính cần lưu ý khi chứng minh rằng một số đã cho là số nguyên tố hay hợp số.
Điều hướng trang.
Số nguyên tố và hỗn hợp - Định nghĩa và Ví dụ
Các khái niệm về số nguyên tố và hợp số dùng để chỉ những số lớn hơn một. Các số nguyên như vậy, tùy thuộc vào số ước số dương của chúng, được chia thành các số nguyên tố và hợp số. Vì vậy, để hiểu định nghĩa về số nguyên tố và hợp số, bạn cần phải biết rõ về \ u200b \ u200bộ chia và bội là gì.
Sự định nghĩa.
số nguyên tố là các số nguyên, lớn hơn một, chỉ có hai ước số dương, cụ thể là chính chúng và 1.
Sự định nghĩa.
Hợp sô là các số nguyên lớn hơn một có ít nhất ba ước số dương.
Riêng biệt, chúng tôi lưu ý rằng số 1 không áp dụng cho cả số nguyên tố hoặc hợp số. Đơn vị chỉ có một ước số dương, chính là số 1. Điều này phân biệt số 1 với tất cả các số nguyên dương khác có ít nhất hai ước số dương.
Cho rằng số nguyên dương là và đơn vị chỉ có một ước số dương, có thể đưa ra các công thức khác của các định nghĩa hữu hạn về số nguyên tố và hợp số.
Sự định nghĩa.
số nguyên tố là các số tự nhiên chỉ có hai ước số dương.
Sự định nghĩa.
Hợp sô là các số tự nhiên có nhiều hơn hai ước số dương.
Lưu ý rằng mọi số nguyên dương lớn hơn một đều là số nguyên tố hoặc hợp số. Nói cách khác, không có một số nguyên nào không phải là số nguyên tố hay hợp số. Điều này xuất phát từ thuộc tính chia hết, cho biết rằng các số 1 và a luôn là ước của bất kỳ số nguyên a nào.
Dựa vào thông tin ở đoạn trước, chúng ta có thể đưa ra định nghĩa sau đây về hợp số.
Sự định nghĩa.
Các số tự nhiên không phải là số nguyên tố được gọi là thành phần.
Hãy mang theo ví dụ về số nguyên tố và hợp số.
Ví dụ về các số tổng hợp, chúng tôi đưa ra 6, 63, 121 và 6697. Tuyên bố này cũng cần một lời giải thích. Số 6, ngoài các ước số dương 1 và 6, còn có các ước số 2 và 3, vì 6 \ u003d 2 3, do đó 6 thực sự là một số hợp. Các ước số dương của 63 là các số 1, 3, 7, 9, 21 và 63. Số 121 bằng tích của 11 11 nên các ước số dương của nó là 1, 11 và 121. Và số 6697 là hợp số, vì các ước số dương của nó, ngoài 1 và 6697, còn là các số 37 và 181.
Trong phần kết luận của đoạn này, tôi cũng muốn lưu ý đến thực tế là số nguyên tố và số nguyên tố khác xa nhau.
Bảng số nguyên tố
Để thuận tiện cho việc sử dụng, các số nguyên tố được ghi lại trong một bảng, được gọi là bảng các số nguyên tố. Dưới là bảng số nguyên tố lên đến 1 000.
Một câu hỏi logic được đặt ra: “Tại sao chúng ta chỉ điền vào bảng các số nguyên tố đến 1.000, không thể lập một bảng gồm tất cả các số nguyên tố hiện có”?
Chúng ta hãy trả lời phần đầu tiên của câu hỏi này trước. Đối với hầu hết các bài toán liên quan đến số nguyên tố, số nguyên tố lên đến một nghìn là đủ. Trong các trường hợp khác, rất có thể, bạn sẽ phải dùng đến một số kỹ thuật giải pháp đặc biệt. Tất nhiên, mặc dù chúng ta có thể tạo một bảng các số nguyên tố lên đến một số nguyên cuối cùng lớn tùy ý số dương, có thể là 10.000 hoặc 1.000.000.000, trong phần tiếp theo chúng ta sẽ nói về các phương pháp lập bảng các số nguyên tố, cụ thể là chúng ta sẽ phân tích phương pháp được gọi là.
Bây giờ chúng ta hãy xem xét khả năng (hay nói đúng hơn là không thể) lập một bảng gồm tất cả các số nguyên tố hiện có. Chúng ta không thể lập một bảng tất cả các số nguyên tố vì có vô số số nguyên tố. Phát biểu cuối cùng là một định lý mà chúng ta sẽ chứng minh sau định lý bổ trợ sau đây.
Định lý.
Ước số dương nhỏ nhất của một số tự nhiên lớn hơn 1 khác 1 là một số nguyên tố.
Bằng chứng.
Để cho được a là số tự nhiên lớn hơn một và b là ước số không dương nhỏ nhất của a. Hãy chứng minh rằng b là một số nguyên tố bằng cách mâu thuẫn.
Giả sử b là hợp số. Khi đó, có một ước của số b (hãy ký hiệu là b 1), khác với cả 1 và b. Nếu chúng ta cũng tính đến giá trị tuyệt đối của số bị chia không vượt quá giá trị tuyệt đối của số bị chia (chúng ta biết điều này từ các thuộc tính của phép chia hết), thì điều kiện 1
Vì số a chia hết cho b theo điều kiện, và chúng ta đã nói rằng b chia hết cho b 1, nên khái niệm chia hết cho phép chúng ta nói về sự tồn tại của các số nguyên q và q 1 sao cho a = b q và b = b 1 q 1, khi đó a = b 1 · (q 1 · q). Từ đó suy ra rằng tích của hai số nguyên là một số nguyên, thì đẳng thức a = b 1 · (q 1 · q) chỉ ra rằng b 1 là một ước của số a. Tính đến các bất đẳng thức trên 1
Bây giờ chúng ta có thể chứng minh rằng có vô hạn số nguyên tố.
Định lý.
Có vô hạn số nguyên tố.
Bằng chứng.
Hãy giả sử nó không phải. Tức là, giả sử rằng chỉ có n số nguyên tố và các số nguyên tố này là p 1, p 2,…, p n. Hãy để chúng tôi chứng minh rằng chúng tôi luôn có thể tìm thấy một số nguyên tố khác với những số được chỉ ra.
Xét một số p bằng p 1 · p 2 ·… · p n +1. Rõ ràng là số này khác với mỗi số nguyên tố p 1, p 2,…, p n. Nếu số p là số nguyên tố thì định lý được chứng minh. Nếu số này là hợp, thì theo định lý trước, có một ước nguyên tố của số này (hãy ký hiệu là p n + 1). Hãy chứng tỏ rằng ước số này không trùng với bất kỳ số nào trong số p 1, p 2,…, p n.
Nếu điều này không đúng, thì theo tính chất của phép chia hết, tích p 1 · p 2 ·… · p n sẽ chia hết cho p n + 1. Nhưng số p cũng chia hết cho p n + 1, bằng tổng p 1 · p 2 ·… · p n +1. Điều này ngụ ý rằng số hạng thứ hai của tổng này, bằng một, phải chia hết cho p n + 1, và điều này là không thể.
Do đó, người ta chứng minh rằng luôn luôn có thể tìm thấy một số nguyên tố mới, số này không nằm trong số các số nguyên tố đã cho trước. Do đó, tồn tại vô hạn số nguyên tố.
Vì vậy, do có vô hạn số nguyên tố nên khi lập bảng các số nguyên tố, chúng luôn tự giới hạn từ trên xuống một số nào đó, thường là 100, 1.000, 10.000, v.v.
Sàng Eratosthenes
Bây giờ chúng ta sẽ thảo luận về các cách lập bảng các số nguyên tố. Giả sử chúng ta cần lập một bảng các số nguyên tố có đến 100.
Phương pháp rõ ràng nhất để giải quyết vấn đề này là kiểm tra tuần tự các số nguyên dương, bắt đầu bằng 2 và kết thúc bằng 100, xem sự hiện diện của một ước số dương lớn hơn 1 và nhỏ hơn số đang được kiểm tra (từ các tính chất của phép chia hết, chúng tôi biết rằng giá trị tuyệt đối của số bị chia không vượt quá giá trị tuyệt đối của số bị chia, khác 0). Nếu không tìm thấy ước số như vậy, thì số đang được kiểm tra là số nguyên tố và nó được nhập vào bảng các số nguyên tố. Nếu tìm thấy một ước số như vậy, thì số đang được kiểm tra là hợp số, nó KHÔNG được nhập vào bảng các số nguyên tố. Sau đó, có một sự chuyển đổi sang số tiếp theo, tương tự như vậy được kiểm tra sự hiện diện của một số chia.
Hãy mô tả một số bước đầu tiên.
Chúng tôi bắt đầu với số 2. Số 2 không có ước số dương nào khác 1 và 2. Do đó, nó là số nguyên tố, do đó, ta điền nó vào bảng các số nguyên tố. Ở đây cần nói rằng 2 là số nguyên tố nhỏ nhất. Hãy chuyển sang số 3. Ước số dương có thể có của nó khác 1 và 3 là 2. Nhưng 3 không chia hết cho 2 nên 3 là số nguyên tố và cũng cần điền vào bảng các số nguyên tố. Hãy chuyển sang số 4. Các ước số dương của nó khác 1 và 4 có thể là 2 và 3, hãy kiểm tra chúng. Số 4 chia hết cho 2 nên 4 là hợp số và không cần điền vào bảng số nguyên tố. Lưu ý rằng 4 là số tổng hợp nhỏ nhất. Hãy chuyển sang số 5. Chúng ta kiểm tra xem có ít nhất một trong các số 2, 3, 4 là ước của nó hay không. Vì 5 không chia hết cho 2 hoặc 3 hoặc 4 nên nó là số nguyên tố và nó phải được viết trong bảng các số nguyên tố. Sau đó, có sự chuyển đổi sang các số 6, 7, và cứ như vậy cho đến 100.
Cách tiếp cận này để biên dịch một bảng các số nguyên tố không phải là lý tưởng. Bằng cách này hay cách khác, anh ta có quyền tồn tại. Lưu ý rằng với phương pháp xây dựng bảng các số nguyên này, bạn có thể sử dụng tiêu chí chia hết, điều này sẽ đẩy nhanh quá trình tìm ước một chút.
Có một cách thuận tiện hơn để biên dịch một bảng các số nguyên tố được gọi là. Từ “sàng” xuất hiện trong tên gọi không phải ngẫu nhiên, vì các hành động của phương pháp này, giống như nó, giúp “sàng” qua sàng các số nguyên Eratosthenes, các đơn vị lớn, để tách đơn giản khỏi các số phức hợp.
Hãy cho thấy sự sàng lọc của Eratosthenes khi biên soạn một bảng các số nguyên tố lên đến 50.
Đầu tiên, chúng ta viết ra các số 2, 3, 4, ..., 50 theo thứ tự.
Số đầu tiên viết được 2 là số nguyên tố. Bây giờ, từ số 2, chúng ta tuần tự di chuyển sang bên phải hai số và gạch bỏ các số này cho đến khi chúng ta đến cuối bảng số đã tổng hợp. Vì vậy, tất cả các số là bội số của hai sẽ bị gạch bỏ.
Số đầu tiên không bị gạch chéo sau 2 là 3. Số này là số nguyên tố. Bây giờ, từ số 3, chúng ta tuần tự di chuyển sang bên phải ba số (có tính đến các số đã bị gạch bỏ) và gạch bỏ chúng. Vì vậy, tất cả các số là bội số của ba sẽ bị gạch bỏ.
Số đầu tiên không bị gạch chéo sau 3 là 5. Số này là số nguyên tố. Bây giờ, từ số 5, chúng ta tuần tự di chuyển sang phải 5 số (chúng ta cũng tính đến các số bị gạch bỏ trước đó) và gạch bỏ chúng. Vì vậy, tất cả các số là bội số của năm sẽ bị gạch bỏ.
Tiếp theo, chúng ta gạch bỏ các số là bội số của 7, sau đó là bội số của 11, v.v. Quá trình kết thúc khi không còn số nào để gạch bỏ. Dưới đây là bảng hoàn chỉnh các số nguyên tố lên đến 50 thu được bằng cách sử dụng sàng của Eratosthenes. Tất cả các số không bị gạch chéo đều là số nguyên tố và tất cả các số bị gạch chéo là tổng hợp.
Hãy xây dựng và chứng minh một định lý sẽ đẩy nhanh quá trình lập bảng các số nguyên tố bằng cách sử dụng sàng Eratosthenes.
Định lý.
Ước số không dương nhỏ nhất của một số tổng hợp a không vượt quá, lấy từ a.
Bằng chứng.
Chúng ta ký hiệu bằng chữ b là ước số nhỏ nhất của hợp số a khác với ước số nguyên (số b là số nguyên tố, theo định lý được chứng minh ở đầu đoạn trước). Khi đó, tồn tại một số nguyên q sao cho a = b q (ở đây q là một số nguyên dương, tuân theo quy tắc nhân các số nguyên) và (khi b> q, điều kiện b là ước nhỏ nhất của a bị vi phạm, vì q cũng là ước của a do đẳng thức a = q b). Nhân cả hai vế của bất đẳng thức với một dương và lớn hơn một số nguyên b (chúng tôi được phép làm điều này), chúng tôi nhận được, khi đó và.
Định lý đã được chứng minh cho chúng ta điều gì về sàng của Eratosthenes?
Đầu tiên, việc xóa các hợp số là bội của một số nguyên tố b phải bắt đầu bằng một số bằng (điều này xuất phát từ bất đẳng thức). Ví dụ: gạch bỏ các số là bội số của hai nên bắt đầu bằng số 4, bội số của ba - với số 9, bội số của năm - với số 25, v.v.
Thứ hai, việc biên soạn một bảng các số nguyên tố đến số n bằng cách sử dụng sàng của Eratosthenes có thể được coi là hoàn thành khi tất cả các hợp số là bội số của các số nguyên tố không vượt quá đều bị gạch bỏ. Trong ví dụ của chúng ta, n = 50 (vì chúng ta đang lập bảng các số nguyên tố lên đến 50) và, do đó, sàng của Eratosthenes phải loại bỏ tất cả các bội số tổng hợp của các số nguyên tố 2, 3, 5 và 7 không vượt quá căn bậc hai số học là 50 . Nghĩa là, chúng ta không còn cần phải tìm kiếm và gạch bỏ các số là bội số của các số nguyên tố 11, 13, 17, 19, 23, v.v. cho đến 47, vì chúng đã bị gạch bỏ dưới dạng bội số của các số nguyên tố nhỏ hơn 2, 3, 5 và 7.
Số này là số nguyên tố hay hợp số?
Một số nhiệm vụ yêu cầu tìm hiểu xem một số đã cho là số nguyên tố hay hợp số. Trong trường hợp chung, nhiệm vụ này không đơn giản, đặc biệt là đối với các số có bản ghi bao gồm một số lượng lớn các ký tự. Trong hầu hết các trường hợp, bạn phải tìm kiếm một số cách cụ thể để giải quyết nó. Tuy nhiên, chúng tôi sẽ cố gắng đưa ra hướng suy nghĩ cho những trường hợp đơn giản.
Không nghi ngờ gì nữa, người ta có thể thử sử dụng tiêu chí chia hết để chứng minh rằng một số đã cho là hợp số. Ví dụ, nếu một số tiêu chí về tính chia hết cho thấy rằng một số đã cho chia hết cho một số nguyên dương lớn hơn một, thì số ban đầu là hợp số.
Ví dụ.
Chứng minh rằng số 898 989 898 989 898 989 là hợp số.
Quyết định.
Tổng các chữ số của số này là 9 8 + 9 9 = 9 17. Vì số bằng 9 17 chia hết cho 9 nên theo tiêu chuẩn của phép chia hết cho 9 có thể lập luận rằng số ban đầu cũng chia hết cho 9. Do đó, nó là hỗn hợp.
Một hạn chế đáng kể của phương pháp này là các tiêu chuẩn về tính chia hết không cho phép chúng ta chứng minh tính đơn giản của một số. Do đó, khi kiểm tra một số xem nó là số nguyên tố hay hợp số, bạn cần tiến hành theo cách khác.
Cách tiếp cận hợp lý nhất là liệt kê tất cả các ước số có thể có của một số nhất định. Nếu không có ước số nào là ước số thực của một số nhất định, thì số đó là số nguyên tố, ngược lại, nó là hợp số. Từ các định lý đã được chứng minh trong đoạn trước, ta thấy rằng các ước của một số cho trước a phải được tìm trong các số nguyên tố không vượt quá. Vì vậy, số a đã cho có thể chia liên tiếp cho các số nguyên tố (thuận tiện lấy từ bảng các số nguyên tố), cố gắng tìm ước của số a. Nếu một số chia được tìm thấy, thì số a là hợp số. Nếu trong các số nguyên tố không vượt quá, không có ước nào của số a thì số a là số nguyên tố.
Ví dụ.
Con số 11 723 đơn giản hay hợp chất?
Quyết định.
Hãy cùng tìm hiểu xem các ước của số 11 723 có thể là số nguyên tố nào. Đối với điều này, chúng tôi ước tính.
Rõ ràng là 
, kể từ 200 2 \ u003d 40 000 và 11 723<40 000
(при необходимости смотрите статью so sánh số). Do đó, các ước số nguyên tố có thể có của 11,723 nhỏ hơn 200. Điều này đã đơn giản hóa rất nhiều nhiệm vụ của chúng tôi. Nếu chúng ta không biết điều này, thì chúng ta sẽ phải sắp xếp tất cả các số nguyên tố không đến 200 mà lên đến số 11 723.
Nếu muốn, bạn có thể ước tính chính xác hơn. Vì 108 2 \ u003d 11 664 và 109 2 \ u003d 11 881 nên 108 2<11 723<109 2
, следовательно, 
. Do đó, bất kỳ số nguyên tố nào nhỏ hơn 109 đều có khả năng là ước nguyên tố của số 11,723 đã cho.
Bây giờ chúng ta sẽ chia tuần tự số 11 723 thành các số nguyên tố 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. Nếu số 11 723 chia hết cho một trong các số nguyên tố đã viết thì nó sẽ là hợp số. Nếu nó không chia hết cho bất kỳ số nguyên tố nào đã viết, thì số ban đầu là số nguyên tố.
Chúng tôi sẽ không mô tả toàn bộ quá trình phân chia đơn điệu và đơn điệu này. Hãy chỉ nói rằng 11 723
Bảng các số nguyên tố từ 1 đến 10000. Bảng các số nguyên tố từ 1 đến 1000
Dưới đây là bảng các số nguyên tố từ 2 đến 10000 (1229 mảnh). Đơn vị không được bao gồm, xin lỗi. Một số cảm thấy rằng đơn vị này không được bao gồm vì… cô ấy không thể ở đó. " Một số nguyên tố là một số có hai ước: một và chính nó."Và số 1 chỉ có một ước số, nó không áp dụng cho cả số nguyên tố hoặc hợp số. (Một ghi chú giải thích từ Olga vào ngày 21/09/12) Tuy nhiên, chúng tôi nhớ rằng các số nguyên tố đôi khi được giới thiệu như thế này: " Số nguyên tố là số chia hết cho một và chính nó."Trong trường hợp này, một rõ ràng là một số nguyên tố.
Bảng các số nguyên tố từ 2 đến 1000. Bảng các số nguyên tố từ 2 đến 1000 bị tô xám.
| 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 | 109 | 113 | 127 | 131 | 137 | 139 | 149 | 151 |
| 157 | 163 | 167 | 173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
| 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
| 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 | 359 |
| 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 | 419 | 421 | 431 | 433 |
| 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 | 503 |
| 509 | 521 | 523 | 541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 |
| 599 | 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 | 659 |
| 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 | 733 | 739 | 743 |
| 751 | 757 | 761 | 769 | 773 | 787 | 797 | 809 | 811 | 821 | 823 | 827 |
| 829 | 839 | 853 | 857 | 859 | 863 | 877 | 881 | 883 | 887 | 907 | 911 |
| 919 | 929 | 937 | 941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
| 1009 | 1013 | 1019 | 1021 | 1031 | 1033 | 1039 | 1049 | 1051 | 1061 | 1063 | 1069 |
| 1087 | 1091 | 1093 | 1097 | 1103 | 1109 | 1117 | 1123 | 1129 | 1151 | 1153 | 1163 |
| 1171 | 1181 | 1187 | 1193 | 1201 | 1213 | 1217 | 1223 | 1229 | 1231 | 1237 | 1249 |
| 1259 | 1277 | 1279 | 1283 | 1289 | 1291 | 1297 | 1301 | 1303 | 1307 | 1319 | 1321 |
| 1327 | 1361 | 1367 | 1373 | 1381 | 1399 | 1409 | 1423 | 1427 | 1429 | 1433 | 1439 |
| 1447 | 1451 | 1453 | 1459 | 1471 | 1481 | 1483 | 1487 | 1489 | 1493 | 1499 | 1511 |
| 1523 | 1531 | 1543 | 1549 | 1553 | 1559 | 1567 | 1571 | 1579 | 1583 | 1597 | 1601 |
| 1607 | 1609 | 1613 | 1619 | 1621 | 1627 | 1637 | 1657 | 1663 | 1667 | 1669 | 1693 |
| 1697 | 1699 | 1709 | 1721 | 1723 | 1733 | 1741 | 1747 | 1753 | 1759 | 1777 | 1783 |
| 1787 | 1789 | 1801 | 1811 | 1823 | 1831 | 1847 | 1861 | 1867 | 1871 | 1873 | 1877 |
| 1879 | 1889 | 1901 | 1907 | 1913 | 1931 | 1933 | 1949 | 1951 | 1973 | 1979 | 1987 |
| 1993 | 1997 | 1999 | 2003 | 2011 | 2017 | 2027 | 2029 | 2039 | 2053 | 2063 | 2069 |
| 2081 | 2083 | 2087 | 2089 | 2099 | 2111 | 2113 | 2129 | 2131 | 2137 | 2141 | 2143 |
| 2153 | 2161 | 2179 | 2203 | 2207 | 2213 | 2221 | 2237 | 2239 | 2243 | 2251 | 2267 |
| 2269 | 2273 | 2281 | 2287 | 2293 | 2297 | 2309 | 2311 | 2333 | 2339 | 2341 | 2347 |
| 2351 | 2357 | 2371 | 2377 | 2381 | 2383 | 2389 | 2393 | 2399 | 2411 | 2417 | 2423 |
| 2437 | 2441 | 2447 | 2459 | 2467 | 2473 | 2477 | 2503 | 2521 | 2531 | 2539 | 2543 |
| 2549 | 2551 | 2557 | 2579 | 2591 | 2593 | 2609 | 2617 | 2621 | 2633 | 2647 | 2657 |
| 2659 | 2663 | 2671 | 2677 | 2683 | 2687 | 2689 | 2693 | 2699 | 2707 | 2711 | 2713 |
| 2719 | 2729 | 2731 | 2741 | 2749 | 2753 | 2767 | 2777 | 2789 | 2791 | 2797 | 2801 |
| 2803 | 2819 | 2833 | 2837 | 2843 | 2851 | 2857 | 2861 | 2879 | 2887 | 2897 | 2903 |
| 2909 | 2917 | 2927 | 2939 | 2953 | 2957 | 2963 | 2969 | 2971 | 2999 | 3001 | 3011 |
| 3019 | 3023 | 3037 | 3041 | 3049 | 3061 | 3067 | 3079 | 3083 | 3089 | 3109 | 3119 |
| 3121 | 3137 | 3163 | 3167 | 3169 | 3181 | 3187 | 3191 | 3203 | 3209 | 3217 | 3221 |
| 3229 | 3251 | 3253 | 3257 | 3259 | 3271 | 3299 | 3301 | 3307 | 3313 | 3319 | 3323 |
| 3329 | 3331 | 3343 | 3347 | 3359 | 3361 | 3371 | 3373 | 3389 | 3391 | 3407 | 3413 |
| 3433 | 3449 | 3457 | 3461 | 3463 | 3467 | 3469 | 3491 | 3499 | 3511 | 3517 | 3527 |
| 3529 | 3533 | 3539 | 3541 | 3547 | 3557 | 3559 | 3571 | 3581 | 3583 | 3593 | 3607 |
| 3613 | 3617 | 3623 | 3631 | 3637 | 3643 | 3659 | 3671 | 3673 | 3677 | 3691 | 3697 |
| 3701 | 3709 | 3719 | 3727 | 3733 | 3739 | 3761 | 3767 | 3769 | 3779 | 3793 | 3797 |
| 3803 | 3821 | 3823 | 3833 | 3847 | 3851 | 3853 | 3863 | 3877 | 3881 | 3889 | 3907 |
| 3911 | 3917 | 3919 | 3923 | 3929 | 3931 | 3943 | 3947 | 3967 | 3989 | 4001 | 4003 |
| 4007 | 4013 | 4019 | 4021 | 4027 | 4049 | 4051 | 4057 | 4073 | 4079 | 4091 | 4093 |
| 4099 | 4111 | 4127 | 4129 | 4133 | 4139 | 4153 | 4157 | 4159 | 4177 | 4201 | 4211 |
| 4217 | 4219 | 4229 | 4231 | 4241 | 4243 | 4253 | 4259 | 4261 | 4271 | 4273 | 4283 |
| 4289 | 4297 | 4327 | 4337 | 4339 | 4349 | 4357 | 4363 | 4373 | 4391 | 4397 | 4409 |
| 4421 | 4423 | 4441 | 4447 | 4451 | 4457 | 4463 | 4481 | 4483 | 4493 | 4507 | 4513 |
| 4517 | 4519 | 4523 | 4547 | 4549 | 4561 | 4567 | 4583 | 4591 | 4597 | 4603 | 4621 |
| 4637 | 4639 | 4643 | 4649 | 4651 | 4657 | 4663 | 4673 | 4679 | 4691 | 4703 | 4721 |
| 4723 | 4729 | 4733 | 4751 | 4759 | 4783 | 4787 | 4789 | 4793 | 4799 | 4801 | 4813 |
| 4817 | 4831 | 4861 | 4871 | 4877 | 4889 | 4903 | 4909 | 4919 | 4931 | 4933 | 4937 |
| 4943 | 4951 | 4957 | 4967 | 4969 | 4973 | 4987 | 4993 | 4999 | 5003 | 5009 | 5011 |
| 5021 | 5023 | 5039 | 5051 | 5059 | 5077 | 5081 | 5087 | 5099 | 5101 | 5107 | 5113 |
| 5119 | 5147 | 5153 | 5167 | 5171 | 5179 | 5189 | 5197 | 5209 | 5227 | 5231 | 5233 |
| 5237 | 5261 | 5273 | 5279 | 5281 | 5297 | 5303 | 5309 | 5323 | 5333 | 5347 | 5351 |
| 5381 | 5387 | 5393 | 5399 | 5407 | 5413 | 5417 | 5419 | 5431 | 5437 | 5441 | 5443 |
| 5449 | 5471 | 5477 | 5479 | 5483 | 5501 | 5503 | 5507 | 5519 | 5521 | 5527 | 5531 |
| 5557 | 5563 | 5569 | 5573 | 5581 | 5591 | 5623 | 5639 | 5641 | 5647 | 5651 | 5653 |
| 5657 | 5659 | 5669 | 5683 | 5689 | 5693 | 5701 | 5711 | 5717 | 5737 | 5741 | 5743 |
| 5749 | 5779 | 5783 | 5791 | 5801 | 5807 | 5813 | 5821 | 5827 | 5839 | 5843 | 5849 |
| 5851 | 5857 | 5861 | 5867 | 5869 | 5879 | 5881 | 5897 | 5903 | 5923 | 5927 | 5939 |
| 5953 | 5981 | 5987 | 6007 | 6011 | 6029 | 6037 | 6043 | 6047 | 6053 | 6067 | 6073 |
| 6079 | 6089 | 6091 | 6101 | 6113 | 6121 | 6131 | 6133 | 6143 | 6151 | 6163 | 6173 |
| 6197 | 6199 | 6203 | 6211 | 6217 | 6221 | 6229 | 6247 | 6257 | 6263 | 6269 | 6271 |
| 6277 | 6287 | 6299 | 6301 | 6311 | 6317 | 6323 | 6329 | 6337 | 6343 | 6353 | 6359 |
| 6361 | 6367 | 6373 | 6379 | 6389 | 6397 | 6421 | 6427 | 6449 | 6451 | 6469 | 6473 |
| 6481 | 6491 | 6521 | 6529 | 6547 | 6551 | 6553 | 6563 | 6569 | 6571 | 6577 | 6581 |
| 6599 | 6607 | 6619 | 6637 | 6653 | 6659 | 6661 | 6673 | 6679 | 6689 | 6691 | 6701 |
| 6703 | 6709 | 6719 | 6733 | 6737 | 6761 | 6763 | 6779 | 6781 | 6791 | 6793 | 6803 |
| 6823 | 6827 | 6829 | 6833 | 6841 | 6857 | 6863 | 6869 | 6871 | 6883 | 6899 | 6907 |
| 6911 | 6917 | 6947 | 6949 | 6959 | 6961 | 6967 | 6971 | 6977 | 6983 | 6991 | 6997 |
| 7001 | 7013 | 7019 | 7027 | 7039 | 7043 | 7057 | 7069 | 7079 | 7103 | 7109 | 7121 |
| 7127 | 7129 | 7151 | 7159 | 7177 | 7187 | 7193 | 7207 | 7211 | 7213 | 7219 | 7229 |
| 7237 | 7243 | 7247 | 7253 | 7283 | 7297 | 7307 | 7309 | 7321 | 7331 | 7333 | 7349 |
| 7351 | 7369 | 7393 | 7411 | 7417 | 7433 | 7451 | 7457 | 7459 | 7477 | 7481 | 7487 |
| 7489 | 7499 | 7507 | 7517 | 7523 | 7529 | 7537 | 7541 | 7547 | 7549 | 7559 | 7561 |
| 7573 | 7577 | 7583 | 7589 | 7591 | 7603 | 7607 | 7621 | 7639 | 7643 | 7649 | 7669 |
| 7673 | 7681 | 7687 | 7691 | 7699 | 7703 | 7717 | 7723 | 7727 | 7741 | 7753 | 7757 |
| 7759 | 7789 | 7793 | 7817 | 7823 | 7829 | 7841 | 7853 | 7867 | 7873 | 7877 | 7879 |
| 7883 | 7901 | 7907 | 7919 | 7927 | 7933 | 7937 | 7949 | 7951 | 7963 | 7993 | 8009 |
| 8011 | 8017 | 8039 | 8053 | 8059 | 8069 | 8081 | 8087 | 8089 | 8093 | 8101 | 8111 |
| 8117 | 8123 | 8147 | 8161 | 8167 | 8171 | 8179 | 8191 | 8209 | 8219 | 8221 | 8231 |
| 8233 | 8237 | 8243 | 8263 | 8269 | 8273 | 8287 | 8291 | 8293 | 8297 | 8311 | 8317 |
| 8329 | 8353 | 8363 | 8369 | 8377 | 8387 | 8389 | 8419 | 8423 | 8429 | 8431 | 8443 |
| 8447 | 8461 | 8467 | 8501 | 8513 | 8521 | 8527 | 8537 | 8539 | 8543 | 8563 | 8573 |
| 8581 | 8597 | 8599 | 8609 | 8623 | 8627 | 8629 | 8641 | 8647 | 8663 | 8669 | 8677 |
| 8681 | 8689 | 8693 | 8699 | 8707 | 8713 | 8719 | 8731 | 8737 | 8741 | 8747 | 8753 |
| 8761 | 8779 | 8783 | 8803 | 8807 | 8819 | 8821 | 8831 | 8837 | 8839 | 8849 | 8861 |
| 8863 | 8867 | 8887 | 8893 | 8923 | 8929 | 8933 | 8941 | 8951 | 8963 | 8969 | 8971 |
| 8999 | 9001 | 9007 | 9011 | 9013 | 9029 | 9041 | 9043 | 9049 | 9059 | 9067 | 9091 |
| 9103 | 9109 | 9127 | 9133 | 9137 | 9151 | 9157 | 9161 | 9173 | 9181 | 9187 | 9199 |
| 9203 | 9209 | 9221 | 9227 | 9239 | 9241 | 9257 | 9277 | 9281 | 9283 | 9293 | 9311 |
| 9319 | 9323 | 9337 | 9341 | 9343 | 9349 | 9371 | 9377 | 9391 | 9397 | 9403 | 9413 |
| 9419 | 9421 | 9431 | 9433 | 9437 | 9439 | 9461 | 9463 | 9467 | 9473 | 9479 | 9491 |
| 9497 | 9511 | 9521 | 9533 | 9539 | 9547 | 9551 | 9587 | 9601 | 9613 | 9619 | 9623 |
| 9629 | 9631 | 9643 | 9649 | 9661 | 9677 | 9679 | 9689 | 9697 | 9719 | 9721 | 9733 |
| 9739 | 9743 | 9749 | 9767 | 9769 | 9781 | 9787 | 9791 | 9803 | 9811 | 9817 | 9829 |
| 9833 | 9839 | 9851 | 9857 | 9859 | 9871 | 9883 | 9887 | 9901 | 9907 | 9923 | 9929 |
| 9931 | 9941 | 9949 | 9967 | 9973 | cuối đĩa 🙂! | ||||||
Đánh giá bài viết:
Đang tải...