Простые числа

 

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

Допустим, что простых чисел существует лишь конечное количество. Обозначим все эти простые числа p1, p2, ..., pk и составим число N = p1p2...pk + 1. Это число по предположению (ибо даже самое большое простое число pk меньше N) не может быть простым. Следовательно, оно должно раскладываться на множители:

p1p2...pk + 1 = q1q2...qm

Ни одно из чисел q1, q2, ..., qm не может совпасть ни с одним из чисел p1, p2, ..., pk, ибо в случае qi = pj должна была бы и правая часть равенства

p1p2...pkq1q2...qm = –1

делиться на это qi = pj, что невозможно, т. е. q1, q2, ..., qm – еще какие-то простые числа, хотя мы считали, что их всего k.

Такое вычисление на самом деле довольно часто приводит к новым простым числам. Обычно их называют факториальными. Рекорд – это число (около 8000 цифр)

2´3´5´...´18523+1.

Теорема (основная теорема арифметики). Всякое целое число a, большее 1, представляется в виде произведения степеней простых сомножителей, причем это разложение единственно (с точностью до перестановки мест сомножителей), т. е. , где a1, a2, ..., ak ³ 0.

Вопрос о том, как часто простые числа встречаются в натуральном ряду и как они распределены среди натуральных чисел, оказался очень сложным. Изучение таблиц простых чисел показывает, что в натуральном ряду есть участки, где простые числа располагаются гуще. Есть даже числа, которые находятся совсем близко друг от друга, как, например, 2 и 3, 3 и 5, 191 и 193, 2711 и 2713. Такие пары чисел называются близнецами. До сих пор неизвестно, конечно или бесконечно число пар близнецов. Самая большая (на сегодняшний день) пара близнецов была открыта в 1995 году: это числа 242206083´238880–1 и 242206083´238880+1. Однако, существуют сколь угодно длинные отрезки натурального ряда, в которых нет ни одного простого числа. Например, среди последовательных чисел k!+2, k!+3, ..., k!+k нет ни одного простого.

Важными характеристиками расположения простых чисел в натуральном ряду служат величины: p(n) – число простых чисел, не превосходящих n, и отношение – средняя плотность простых чисел среди первых n натуральных. Изучение таблиц простых чисел показало, что, двигаясь по натуральному ряду, мы будем встречать простые числа все реже. Эйлер обосновал это наблюдение, доказав, что . Иногда это выражают словами: “Вероятность того, что наугад выбранное число – простое, равна нулю”. Можно доказать, что простые числа располагаются все же гуще квадратов натуральных чисел.

Но все эти результаты очень мало говорят о самом числе p(n). Математикам хотелось получить для p(n) какую-нибудь достаточно простую приближенную формулу. Первая гипотеза о величине p(n) была сделана независимо французским математиком А. Лежандром и К. Гауссом около 1800 г. Она заключалась в том, что . Однако доказать это утверждение улалось лишь 100 лет спустя. Функция p(n) называется функцией Чебышева.

Определение. Функция Эйлера j(n) определяется для всех целых положительных n и представляет собою количество чисел ряда 1, 2, ..., n–1, взаимно простых с n.

Пусть – каноническое разложение числа n. Вычеркнем из ряда 1, 2, ..., n все числа, которые делятся на p1. Таких чисел будет . Останется чисел, не делящихся на p1. Теперь из оставшихся чисел выбросим все числа, делящиеся на p2. Их будет

.

Останется

.

Продолжая дальше выбрасывать числа, делящиеся на p3, p4, ..., pk придем к формуле

,

или также

.

В частности, будем иметь

j(pa) = papa–1, j(p) = p – 1,

где p – простое число.

Приведем без доказательства одно важное свойство функции Эйлера: при взаимно простых n1 и n2 имеет место равенство

j(n1n2) = j(n1)j(n2).

Рассмотрим некоторые простые числа специального вида.

Простые числа Мерсенна являются простыми числами вида

M(p) = 2p – 1,

названные так в честь французского монаха Марена Мерсенна, жившего в начале XVII века. Любой математик быстро сообразит, что M(p) бывает простым только тогда, когда само число p – простое, т. к. 2uv – 1 делится на 2u – 1. А верно ли обратное – то есть для любого ли простого p число M(p) будет простым? К сожалению нет. Например, число M(11) – составное: M(11) = 2047 = 23´89.

Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел M(p) для различных простых чисел p. Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение.

Сам Мерсенн нашел несколько первых простых чисел такого вида и сделал предположение о следующих. Несмотря на то, что его предположение оказалось частично ошибочным, оно привлекло к себе внимание лучших математиков того времени. В 1750 году Леонард Эйлер установил, что число M(31) является простым. Это число оставалось самым большим из известных простых чисел более ста лет. В 1876 году французский математик Лукаш установил, что число M(127) является простым числом. Для проверки на простоту чисел Мерсенна был разработан специальный алгоритм – тест Лукаша–Лемера[4]. Именно благодаря этому алгоритму стало возможным проверять простоту чисел, содержащих многие тысячи десятичных цифр!

Интерес к чмслам Мерсенна тесно связан с так называемыми совершенными числами, – числами, равными сумме своих делителей (исключая само число): 6 = 1+2+3, 28 = 1+2+4+7+14. А именно: если число M(p) – простое, то 2p–1´M(p) – совершенное.

До сих пор неизвестно, конечно или бесконечно количество простых чисел Мерсенна.

Существует еще один тип простых чисел с большой и интересной историей. Они были впервые введены французским юристом Пером Ферма (1601–1665), который прославился своими выдающимися математическими работами. Он также занимался поиском больших простых чисел. Например, Ферма установил, что числа 21 + 1, 22 + 1, 24 + 1, 216 + 1 – простые. В письме Мерсенну, написанном в 1640 г. Ферма выдвинул предположение, что – всегда число простое, но сообщил, что не в состоянии определить, является число 4294967297 = 232 + 1 простым или нет. Мы можем вычислить , выполнив для этого 32 опрерации возведения в квадрат по модулю 232 + 1, в результате получится 3029026160; следовательно, (согласно собственной теореме Ферма, которую он доказал в том же 1640 г.!), 232 + 1 не есть простое число. Это доказательство не дает абсолютно никакой информации относительно множителей, а только дает ответ на поставленный Ферма вопрос. Позднее Эйлер определил, что это число имеет делитель равный 641. Сейчас числа вида

называются числами Ферма. Первые четыре числа Ферма: 5, 17, 257, 65537 простые, но уже пятое число – F(5) = 232 + 1, как показал Эйлер, является составным. Других простых чисел Ферма так и найдено.