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

 

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

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

p₁p₂...p_k + 1 = q₁q₂...q_m

Ни одно из чисел q₁, q₂, ..., q_m не может совпасть ни с одним из чисел p₁, p₂, ..., p_k, ибо в случае q_i = p_j должна была бы и правая часть равенства

p₁p₂...p_k – q₁q₂...q_m = –1

делиться на это q_i = p_j, что невозможно, т. е. q₁, q₂, ..., q_m – еще какие-то простые числа, хотя мы считали, что их всего k.

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

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

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

Вопрос о том, как часто простые числа встречаются в натуральном ряду и как они распределены среди натуральных чисел, оказался очень сложным. Изучение таблиц простых чисел показывает, что в натуральном ряду есть участки, где простые числа располагаются гуще. Есть даже числа, которые находятся совсем близко друг от друга, как, например, 2 и 3, 3 и 5, 191 и 193, 2711 и 2713. Такие пары чисел называются близнецами. До сих пор неизвестно, конечно или бесконечно число пар близнецов. Самая большая (на сегодняшний день) пара близнецов была открыта в 1995 году: это числа 242206083´2³⁸⁸⁸⁰–1 и 242206083´2³⁸⁸⁸⁰+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 все числа, которые делятся на p₁. Таких чисел будет . Останется чисел, не делящихся на p₁. Теперь из оставшихся чисел выбросим все числа, делящиеся на p₂. Их будет

.

Останется

.

Продолжая дальше выбрасывать числа, делящиеся на p₃, p₄, ..., p_k придем к формуле

,

или также

.

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

j(p^a) = p^a – p^a–1, j(p) = p – 1,

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

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

j(n₁n₂) = j(n₁)j(n₂).

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

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

M(p) = 2^p – 1,

названные так в честь французского монаха Марена Мерсенна, жившего в начале XVII века. Любой математик быстро сообразит, что M(p) бывает простым только тогда, когда само число p – простое, т. к. 2^uv – 1 делится на 2^u – 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) – простое, то 2^p–1´M(p) – совершенное.

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

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

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