Бесконечность множества простых чисел

«Начала» Евклида состоят из 13 книг, т.е. глав. Книги 7, 8, 9 называются «Арифметика в геометрическом изложении». Теорема Евклида из книги 9. (Греческий математик Евклид жил в 330–275 гг. до нашей эры).

Теорема Евклида. Простых чисел бесконечно много.

Доказательство (от противного).

Пусть р ₁, р ₂,..., р_п все простые числа и больше нет простых чисел. Составим число                                 S = р₁ · р₂  · … · p_n + 1. Это число является либо простым, либо составным. Но простым оно быть не может, так как оно больше всех чисел р ₁, р₂, …, p_n, а по предположению других простых чисел, кроме них, не существует. С другой стороны, если бы а было составным числом, оно должно было бы иметь хотя бы один простой делитель, которым должно быть одно из чисел р ₁, р₂, …, p_n. Но число S при делении на любое из этих чисел дает остаток 1. Полученное противоречие показывает, что сделанное нами предположение неверно, т.е.   множество простых чисел бесконечно.

Хотя со времен Евклида прошло более 2000 лет, к его теореме ничего нового не добавлено. Из этой теоремы следует, что какое бы большое простое число мы не нашли, обязательно найдется еще большее простое число.

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

Известны очень большие участки составных натуральных чисел, например числа                                   (n ¹ 1) п! +2, п! + 3,..., п! + п – составные. Число п можно взять сколько угодно большим.

Решето Эратосфена

Математиками составлены обширные таблицы, в которых указаны простые числа. При составлении таких таблиц не надо проверять для каждого числа, имеет ли оно делители, отличные от единицы и этого числа. Греческий математик и астроном Эратосфен, живший в Александрии в III веке до н. э.,придумал более простой способ решения этой задачи, основанный на вычеркивании чисел по определенному правилу.

Так как древние греки писали на восковых дощечках и не вычеркивали, а выкалывали числа, то после применения метода Эратосфена табличка становилась похожей на решето. Поэтому его метод называют методом «решета Эратосфена».

Метод Эратосфена заключается в следующем. Сначала выписывают все числа от 2 до n. После этого вычёркивают все числа, кратные 2, кроме самого числа 2. Например, если n = 40, получим:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,

23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40

Мы видим, что числа вычёркиваются через одно, причём, все оставшиеся, кроме 2, не делятся на 2, т.е. и наименьший простой делитель наверняка больше 2.

Первым оставшимся числом после 2 является число 3. Вычеркнем все числа, кратные 3, кроме самого числа 3 (т.е. вычёркиваем каждое третье число. Оставшиеся числа не делятся ни на 2, ни на 3 (кроме 2 и 3), получим:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,

23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40

На следующем шаге вычёркиваем числа кратные 5, кроме числа 5. (Это первое число, оставшееся после вычёркивания и идущее после чисел 2 и 3), получим:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,

23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40

Числа, оставшиеся после трёх вычеркиваний (кроме самих 2, 3, 5), не делятся ни на 2, ни на 3, ни на 5, т.е. их простые делители должны быть, по крайней мере, равны 7. Но наименьший простой делитель числа меньшего 40 не превосходит , т.е. меньше 7. Значит, среди оставшихся чисел нет составных, все они простые.

Итак, простые числа, меньшие 40 – это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Отсюда, как следствие, вытекают правила:

Правило 1. Чтобы составить таблицу простых чисел, не больших натурального числа n, надо вычеркнуть на отрезке натурального ряда от 2 до n все составные числа, кратные простым 2, 3, 5, …, не большим .

Так, чтобы составить таблицу простых чисел, не больших 100, надо вычеркнуть на отрезке натурального ряда от 2 до 100 все составные числа кратные простым не большим  = 10, т.е. кратные простым 2, 3, 5, 7. Простых чисел, меньших 100, будет 25, это

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.

Правило 2. Чтобы определить простым или составным является натуральное число m, надо делить это число на простые числа 2, 3, 5, … не большие , если m делится хотя бы на одно из этих простых чисел, то оно составное, если не делится, то простое.

П р и м е р. Установить, является ли число 1973 простым или составным. Для этого надо испытать делимость 1973 на простые числа, не большие » 44. Следовательно, надо испытать делимость на 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Испытания показывают, что число 1973 простое.

В настоящее время имеются напечатанные таблицы простых чисел, содержащие все простые числа, меньшие 12 миллионов.

С помощью готовой таблицы решается вопрос о том, является ли данное число простым или составным. Хотя и было доказано, что наибольшего простого числа не существует, математики стремятся обнаружить большие простые числа, далеко выходящие за пределы даже самых больших таблиц. Одно из таких больших простых чисел равно 2³²¹⁷ – 1. Это число в десятичной записи имеет 969 цифр. То, что число простое, было установлено в 1957 году с помощью ЭВМ.

Среди простых чисел есть много таких, разность которых равна 2. Например, пары простых чисел 3 и 5, 5 и 7, 11 и 13, 17 и 19 и т.д. Такие пары простых чисел называют числами-близнецами. Числа – близнецы встречаются на протяжении всей исследованнойчасти натурального ряда. Известны весьма большие числа-близнецы, например, 100116957 и 100116959. Однако до сих пор не решен вопрос о том, существует бесконечное или конечное множество пар чисел-близнецов.