простые числа? Как могла бы выглядеть формула количества простых чисел до некоторого числа
n?
Не успели мы расстаться с великим швейцарским математиком Леонардом Эйлером (1707–1783), как снова встречаемся с ним.
В 1772 г. Эйлер выяснил, что выражение n² + n + 41 (напомним, что любое выражение вида ax² + bx + c называется квадратным многочленом) дает простые числа при условии, что n меньше 40. Например, для n = 0, 1, 2, 3, 4, 5, 6 мы получаем, соответственно, следующие значения: 41, 43, 47, 53, 61, 71, 83. Отметим, что разности между этими значениями равны 2, 4, 6, 10, 12.
Совершенно очевидно, что формула Эйлера не может выдавать простые числа бесконечно. Всякий, кто помнит хотя бы крохи математических законов, которые проходят в восьмом классе, поймет, что при n = 41 результат не будет простым числом, так как в этом случае все три слагаемые формулы делятся на 41, из чего следует, что и их сумма должна делиться на 41.
А если подумать еще немного, мы поймем, что эта формула не может давать простого числа и при n = 40. Запишем ее в таком виде:
40² + 40 + 41 = 40 (40 + 1) + 41 = 40 · 41 + 41 = 41 (40 + 1) = 41².
Получившееся значение – не только не простое число: это еще и полный квадрат, 1681.
Отметим, что число 1681 обладает одним весьма интересным свойством: это единственное четырехзначное число, которое не только само является полным квадратом, но и состоит из двух частей, 16 и 81, каждая из которых тоже само является полным квадратом (если не учитывать тривиальные случаи чисел вроде 1600).
Примечание. До сих пор не доказано, что какой-либо квадратный многочлен вида ax ² + bx + c генерирует бесконечное количество простых чисел.
Когда я слушал в Тель-Авивском университете курс теории чисел, лектор, профессор Григорий Фрейман, показал нам доказательство следующей теоремы:
Арифметическая прогрессия an + b содержит бесконечное количество простых чисел, если a и b – взаимно простые числа, то есть не имеют общих делителей, больших, чем 1.
Доказательство теоремы Дирихле, названной по имени Густава Лежёна Дирихле (1805–1859), исключительно красиво, но нашему лектору понадобилось для его объяснения четыре занятия, и оно заходит в области математики, лежащие далеко за пределами темы этой книги. Поскольку я обещал использовать только основные арифметические операции, я объясню, причем как можно проще, лишь утверждение этой теоремы.
Выберем два взаимно простых числа (то есть два числа, не имеющих общих делителей), например
