shkolageo.ru 1



Простые и составные числа.



Число - одно из основных понятий математики, позволяющее выразить результаты счета или измерения. Когда-то численность множества не отделялась от других его качеств, и для того, чтобы сравнить два множества, их элементы располагали друг против друга. Но потом оказалось, что удобнее сравнивать все множества с одним и тем же множеством-посредником. Так как пальцы были всегда при себе, то и стали считать по пальцам. А потом появились особые названия для чисел - сначала небольших, а потом всё больших и больших.

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

Небольшую «коллекцию» простых чисел нам поможет составить старинный способ, придуманный ещё в III веке до н. э. Эратосфеном, киренским хранителем знаменитой Александрийской библиотеки. Выпишем несколько подряд идущих чисел, начиная с 2. 2 отберём в свою коллекцию, а остальные числа, кратные 2, зачеркнём. Ближайшим будет 3. Его оставляем для коллекции, а все остальные числа, кратные 3, зачеркнём. При этом оказывается, что некоторые числа уже вычеркнуты раньше, например: 6, 12 и др. Следующее наименьшее незачёркнутое число – это 5. Берём 5, а кратные 5 – зачёркиваем. Повторяя эту процедуру снова и снова, мы добьёмся того, что незачёркнутыми останутся одни простые числа – они словно просеялись сквозь решето. Такой способ получил название «решето Эратосфена».

Для упрощения поиска простых чисел заманчивым представляется решение такой задачи: найти формулу, при вычислении значения которой при различных n всегда получались бы простые числа. Попыток отыскания такой формулы было немало.


  1. f (n) = n2 + n + 17

  2. y (n) = n2 – n + 41

  3. u (n) = n2 - 79n + 1609

Попробуем вместо n последовательно подставлять в формулу натуральные числа.

Например: f (1) = 19, f (2) =23, f (6) = 59, f (7) =73

Все эти числа являются простыми, но уже f (16) = 289 = 172, т.е. получилось составное число.

у(1) = 41, у(2) = 43, у(3) = 47 - числа простые, но у(41) = 1681 = 412 является составным числом.

Можно доказать так же, что никакой многочлен с целыми коэффициентами не может для всякого натурального значения n равняться простому числу.

Не о всяком числе можно сразу сказать, простое оно или составное. Например, число 1999. Если нет под рукой специальных таблиц или компьютера, то придется вспомнить о решете Эратосфена. Конечно, это число не столь велико, чтобы его невозможно было просеять сквозь него, но можно прибегнуть к другим способам. В качестве предполагаемых делителей 1999 возьмем начальные простые числа. При этом 2 можно не брать (ясно, что 1999 на него не делится). Простейшие признаки делимости позволяют отвергнуть и другие числа – 3, 5, 7, 11, 13, 17, 19, 23. Этот прием, отмеченный еще Леонардо Пизанским, при довольно большом числе заставляет делать много рутинной работы. Ее лучше переложить на плечи компьютера.

Если взять наугад какое-нибудь большое натуральное число, то с большой вероятностью оно окажется составным потому, что по мере удаления в бесконечность решето Эратосфена становится чаще, а значит, простые числа встречаются все реже и реже.

Первую известную нам таблицу простых чисел составил итальянский математик Пьетро Антонио Катальди в 1603 году. Она охватывала все простые числа от 2 до 743. В 1770 году немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102000 и не делящихся на – 2, 3, 5. К середине XIX века уже были составлены таблицы наименьших делителей не только первого миллиона, но и вплоть до девятого.


У охотников за простыми числами больше всего популярны простые числа Мерсенна. Они названы в честь французского ученого Марена Мерсенна, сыгравшего в XVIII веке видную роль в становлении Европейской науки. Он известен как физик и философ, но в большей степени его знают как человека, подружившегося со многими крупнейшими учеными того времени. Он способствовал установлению контактов между учеными, обмену открытиями между ними. Мерсенн заинтересовался числами вида М(р) = 2р – 1, где р – простое число. Составим таблицу таких чисел.


р

2

3

5

7

11

13

17

19

2р

4

8

32

128

2048

8192

131072

524288

М

3

7

31

127

2047

8191

131071

524287


М(2) = 3, М(3) = 7, М(5) = 31 – простые числа, это видно сразу. Нетрудно убедиться, что и М(7) = 127 – тоже простое число. Но М(11) = 2047 = 23 * 89 – число составное. Числа М(р) с ростом р увеличиваются очень быстро, и поэтому трудно установить, являются ли они простыми или составными. Не все числа вида М(р) = 2р – 1 являются простыми. Леонарду Эйлеру удалось доказать, что М(31) = 2 147 483 647 есть простое число. Очень долго оно считалось самым большим из известных науке простых чисел, но в 1883 году Иван Михеевич Первушин сумел доказать, что М(61) = 2 305 843 002 913 693 951 есть простое число. В наше время с помощью ЭВМ найдено еще несколько простых чисел этого вида, одно из последних М(216 091), но записать его цифрами подряд трудно, в нем столько цифр, что их хватит на целую книгу. Пока не удалось установить, конечно или бесконечно число таких простых чисел.


Пьер Ферма – юрист по профессии, математик по призванию. Его интересовали вопросы, связанные с простыми числами. Он высказал предположение, что простыми являются все числа вида F(n) = .

Проверим это предположение для нескольких n, составив таблицу


n

0

1

2

3

4

5

2n

1

2

4

8

16

32



2

4

16

256

65536

4294967296

F=

3

5

17

257

65537

4294967297

Первые числа - 3, 5, 17, 257 – простые. Труднее установить, что 65 537 – тоже простое число. Хочется думать, что все F(n) - тоже простые, но оказывается, что F(5) = 4 294 967 297 – составное, оно делится на 641. Проверить это несложно, гораздо сложнее установить, что именно на 641 надо делить. Установил это Л.Эйлер. Любопытно, что до сих пор никому не удалось установить, имеются ли простые числа вида F(n) = при n, большем 4.


Карл Фридрих Гаусс установил, что правильный p-угольник для простого р можно построить при помощи циркуля и линейки тогда и только тогда, когда р есть простое число вида F(n). Иначе говоря, треугольник с равными сторонами и углами построить с помощью циркуля и линейки можно; пятиугольник – тоже; построение 17-угольника довольно сложно, но возможно; оказывается можно построить при помощи циркуля и линейки даже 257 и 65 537-угольники, но вот например 7-угольник, пользуясь этими инструментами, построить нельзя, так как ни при каком n 7 не равно .

Стоит ещё раз подчеркнуть, что с натуральных чисел начинается вся математика, да и любой другой науке без натуральных чисел не обойтись. А простые числа? Есть ли важные основания, чтобы интересоваться ими?

Начнём издалека. Пусть нам надо построить множество N, а в качестве инструмента для этой работы имеется только операция сложения. Какие понадобятся материалы? Ясно, что на «складе» необходимо иметь большой (бесконечно большой!) запас единиц – из этих единиц-«кирпичиков» можно построить всё множество N. Действительно, сначала возьмем 1, прибавим ещё одну – операция сложения нам разрешена – получим 2, прибавим ещё одну 1 – получим 3, ещё одну… К любому числу можно прибавить ещё одну 1, и, таким образом, всё множество N будет построено.

А теперь пусть надо построить множество N, но сложение запрещено, разрешено применять только умножение. Возьмём 1 – начальный элемент множества N. Но путём умножения из единиц следующий элемент – 2 – не получить, её придётся брать со «склада». Такая же картина и с 3. 4 получим легко: надо умножить 2 на 2, но за 5 – снова на «склад». 6 – это 2*3, здесь тоже всё в порядке, но с 7 опять неладно! Зато 8 = 2*2*2 , 9=3*3, 10=2*5. 11 с помощью операции умножения из 1, 2, 3, 5, 7 не получишь, снова надо идти на «склад». Вы, наверное, уже заметили, что «складом» в этом случае будет множество простых чисел P. Таким образом, любое натуральное число – либо составное, и тогда его можно получить, перемножая некоторые простые, либо простое, и тогда его придётся взять из P,так как «создать» его при помощи умножения других чисел невозможно. Можно сказать так:


Любое натуральное число А может быть представлено в виде произведения

А = р1е1  р2е2  р3е3  …  рnen, где p – различные простые числа и e – натуральные показатели степени. Это утверждение называется основной теоремой арифметики. Если ещё добавить, что слово multiplicatio означает умножение, то совершенно очевидным становится вывод:

ПРОСТЫЕ ЧИСЛА СОСТАВЛЯЮТ МУЛЬТИПЛИКАТИВНЫЙ БАЗИС МНОЖЕСТВА НАТУРАЛЬНЫХ ЧИСЕЛ.