Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1998/04/07.pdf Дата изменения: Fri Dec 23 19:24:40 2005 Дата индексирования: Tue Oct 2 00:09:22 2012 Кодировка: Windows-1251 Поисковые слова: http www.badastronomy.com bad tv foxapollo.html

Простые числа и постулат Бертрана
А.КОРОБОВ

7

Н

АПОМНИМ, что простыми числами называются натуральные числа, которые имеют ровно два различных натуральных делителя, а именно единицу и само число. Последовательность простых чисел

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, ... устроена весьма загадочно; так, никому не удалось найти общей формулы, пригодной для быстрого вычисления простых чисел, и вряд ли такая формула вообще существует. Например, знаменитый французский математик Пьер Ферма предположил, что все числа вида
22 + 1 , n = 1, 2, 3, ...
n

стых чисел, в частности, предложив доказательство бесконечности последовательности простых чисел, построенное на совершенно новой и плодотворной идее.1 Впервые бесконечность множества простых чисел установил знаменитый древнегреческий математик Евклид с помощью очень простого и красивого рассуждения 'от противного'. Прежде чем приводить доказательство Евклида, заметим, что любое натуральное число, больше единицы, можно записать в виде произведения простых сомножителей, последовательно выделяя делители числа в виде все большего числа сомножителей, пока это возможно; например,

лители числа:

360 = 2 180 = 2 2 90 =
= 2 2 2 45 = 2 2 2 3 3 5 . Основная теорема арифметики утверждает, что разложение на простые сомножители всегда одно и то же с точностью до порядка простых сомножителей. Доказательство этой теоремы вполне элементарно, однако мы его приводить не будем, тем более, что многим единственность разложения представляется сама собой разумеющейся (хотя это, конечно, не так!).2 Приведем теперь рассуждение Евклида. Предположим, что все простые числа исчерпываются конечным набором: 2, 3, 5, 7, 11, ..., р. Тогда число

простые; однако это оказалось неверно уже при n = 5. Ошибку обнаружил много лет спустя гениальный ученый Леонард Эйлер, заметив, что 232 + 1 делится на 641. Эйлер также 2 указал многочлен x х + 41, принимающий только простые значения при всех х = 0, 1, 2, ..., 40. Однако при х = 41 значение этого многочлена 2 равно составному числу 41 . Эйлер внес большой вклад в изучение про-

360 = 36 10 = 6 6 10 =
= 2 3 6 2 5 = 2 3 2 3 2 5. Одно и то же натуральное число можно раскладывать на простые сомножители многими способами, например в различной последовательности разлагать на сомножители де1 Доказательство Эйлера можно найти в [4, 8, 10].

2 3 5 7 11 K p + 1
при делении на 2, 3, 5, 7, 11, ..., р дает в остатке 1, т.е. не делится ни на одно простое число. Но это число должно
2 Доказательство основной теоремы арифметики можно прочитать, например, в 'Кванте' ?3 за 1998 год.

Иллюстрация П.Чернуского
2*