Геометрия окружностей - Учебное пособие (Мендель В.В.)

Тема 3. бесконечность множества простых чисел. решето эратосфена

                Мы выяснили, что множество натуральных чисел можно разбить на три подмножества. Встает вопрос о числе простых чисел в бесконечном натуральном ряду. Существуют ли простые числа среди больших натуральных чисел, или с какого то определенного числа все натуральные числа, следующие за ним, будут составными? Оказывается, что хотя в натуральном ряду можно найти участки составных чисел любой длины, множество простых чисел бесконечно. Это утверждение было доказано ещё древнегреческим математиком Евклидом и входит в его знаменитые «Начала». Приведём здесь доказательство этого утверждения:

Теорема 3.3.  Множество простых чисел бесконечно.

Доказательство. Доказательство проведем от противного. Пусть множество простых чисел конечно, и пусть р – наибольшее простое число. Рассмотрим натуральное число  N, которое является произведением всех простых чисел, т.е.

                                                   

 и прибавим к этому числу 1: . Очевидно, что полученное число не делится ни на одно простое число от 1 до р, следовательно получаем, что N = 1, но непосредственно видно, что N>1. Получили противоречие, которое возникло из за того, что мы сделали неправильное предположение. Следовательно, множество натуральных чисел бесконечно.Δ

                Таким образом, какую бы длинную серию последовательных составных чисел мы ни встретили в ряду натуральных чисел, мы можем быть убеждены в том, что за нею найдется ещё бесконечное множество простых чисел.

                Рассмотрим вопрос о нахождении или о выделении простых чисел в натуральном ряду. Алгоритм отделения простых чисел основан на следующей теореме:

Теорема 3.4.  Если натуральное число n (n>1) не делится ни на одно простое число, не превосходящее , то оно простое.

               

Алгоритм выделения простых чисел  в последовательности натуральных чисел 2,…,n (Решето Эратосфена)

Вычеркиваем последовательно каждое второе число после двух. Первое, не зачеркнутое число  3, является простым.

 

Вычеркиваем каждое третье число после трёх. Первое, не зачеркнутое число 5, является простым.

 

Вычеркиваем каждое пятое число после пяти и т.д., пока не дойдем до числа, большего .

 

Все числа, которые остаются не вычеркнутыми, являются простыми.

 

Задания для самостоятельного решения

3.1. Выделить все простые числа  от   157 до 211.

Выписать десять последовательных составных чисел.