Теорема.

Простых чисел бесконечно много.

Доказательство.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p 1 , p 2 , …, p n . Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p 1 ·p 2 ·…·p n +1 . Понятно, что это число отлично от каждого из простых чисел p 1 , p 2 , …, p n . Если число p - простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его p n+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p 1 , p 2 , …, p n .

Если бы это было не так, то по свойствам делимости произведение p 1 ·p 2 ·…·p n делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

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

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.

Решето Эратосфена

Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .

Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.

Опишем несколько первых шагов.

Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .

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

Существует более удобный способ для составления таблицы простых чисел, называемый . Присутствующее в названии слово «решето» не случайно, так как действия этого метода помогают как бы «просеять» сквозь решето Эратосфена целые числа, большие единицы, чтобы отделить простые от составных.

Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .

Сначала записываем по порядку числа 2, 3, 4, …, 50 .

Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.

Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.

Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.

Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.

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

Теорема.

Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .

Доказательство.

Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .

Что же нам дает доказанная теорема, касательно решета Эратосфена?

Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.

Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .

Данное число простое или составное?

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

Несомненно, можно попробовать воспользоваться признаками делимости для доказательства того, что данное число является составным. Если, к примеру, некоторый признак делимости показывает, что данное число делится на некоторое целое положительное число большее единицы, то исходное число является составным.

Пример.

Докажите, что число 898 989 898 989 898 989 составное.

Решение.

Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.

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

Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.

Пример.

Число 11 723 простое или составное?

Решение.

Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .

Достаточно очевидно, что , так как 200 2 =40 000 , а 11 723<40 000 (при необходимости смотрите статью сравнение чисел ). Таким образом, возможные простые делители числа 11 723 меньше числа 200 . Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200 , а вплоть до числа 11 723 .

При желании можно оценить более точно. Так как 108 2 =11 664 , а 109 2 =11 881 , то 108 2 <11 723<109 2 , следовательно, . Таким образом, любое из простых чисел, меньших 109 , потенциально является простым делителем данного числа 11 723 .

Теперь мы будем последовательно делить число 11 723 на простые числа 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.

Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723

Ответ Ильи корректный, но не очень подробный. В 18 веке, кстати, единицу ещё считали простым числом. Например, такие крупные математики как Эйлер и Гольдбах. Гольдбах автор одной из семи задач тысячелетия - гипотезы Гольдбаха. В изначальной формулировке утверждается, что всякое чётное число представимо в виде суммы двух простых чисел. Причём изначально 1 учитывалась как простое число, и мы видим такое: 2 = 1+1. Это наименьший пример, удовлетворяющий исходной формулировке гипотезы. Позднее её подправили, и формулировка приобрела современный вид: "всякое чётное число, начиная с 4, представимо в виде суммы двух простых чисел".

Вспомним определение. Простым является натуральное число р, имеющее только 2 различных натуральных делителя: само р и 1. Следствие из определения: у простого числа р только один простой делитель - само р.

Теперь предположим, что 1 простое число. По определению у простого числа только один простой делитель - оно само. Тогда получится, что любое простое число, большее 1, делится на отличающееся от него простое число (на 1). Но два различных простых числа не могут делиться друг на друга, т.к. иначе это не простые, а составные числа, и это противоречит определению. При таком подходе получается, что существует только 1 простое число - сама единица. Но это абсурд. Следовательно, 1 не простое число.

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

При таком рассмотрении не трудно обнаружить аналоги простых чисел в других алгебраических структурах. Предположим, что у нас есть мультипликативная группа, образованная из степеней 2, начиная с 1: 2, 4, 8, 16, ... и т.д. 2 выступает здесь образующим элементом. Простым числом в этой группе назовём число, большее наименьшего элемента, и делящееся только на себя и на наименьший элемент. В нашей группе такими свойствами обладает только 4. Всё. Больше простых чисел в нашей группе не существует.

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

§2 Простые числа.

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

Сколько делителей может иметь натуральное число? У числа 1 только один делитель. Всякое натуральное имеет два делителя: 1 и само число а . Есть числа, которые не имеют других делителей.

Определение . Натуральное число р называется простым, если оно имеет ровно два делителя: 1 и р.

Определение . Натуральное число, а называется составным, если кроме 1 и а у него есть еще, хотя бы один делитель.

Замечание . Число 1 не относится ни к составным, ни к простым.

Множество N можно разбить на три подмножества.

1 - число, имеющее один делитель.

Простые числа, имеющие ровно два делителя.

Составные числа, имеющие по меньшей мере три делителя.

Выпишем несколько первых простых чисел:

2, 3, 5, 7, 11, 13, 17 …

Бесконечно ли эта последовательность, или можно перечислить все простые числа? Ответ был известен еще Евклиду.

Теорема . (Евклида)

Множество простых чисел бесконечно.

Доказательство . “
”Пусть
- множество всех простых чисел, где - последнее (наибольшее) простое число.

Составим число
. Очевидно,
, значит, N -составное.
делится на какое-то из простых, например, на . Но тогда, по свойствам делимости, 1 делится на , что невозможно.

Рассмотрим некоторые элементарные свойства простых чисел.

1. Пусть
- наименьший делитель натурального числа а.

Тогда p -простое число.

Доказательство . Пусть d -некоторый делитель числа p .

Но p -наименьший делитель
или
p -простое.

2. Пусть
- наименьший делитель составного числа а .

Тогда

Доказательство . а- составное, значит

По условию

3. Пусть а - натуральное число, p - простое число.

Тогда а делится на p , либо а и p взаимно просты.

Доказательство . Пусть
. D - делитель простого
или

Если d =1, то а и p взаимно просты.

Если d =p , то а делится на р.

4. Пусть p -простое число, произведение аb делится на p , тогда а делится на p или b делится на р.

Доказательство . Если а не делится на p , то по свойству 3 НОД (а, p )=1.

Но тогда, по свойству 2 взаимно простых чисел, b делится на р .

Замечание 1 . Свойство 4 легко обобщать по индукции: если произведение
делится на простое p , то найдется множитель , который делится на р.

Замечание 2 . Если произведение
делится на простое p , причем все сомножители - простые числа, то хотя бы один из сомножителей равен р.

Для составления списка простых чисел, не превосходящих заданного числа N , используют алгоритм, который называют “решето Эратосфена”.

Выпишем натуральные числа от 2 до N .

Число 2 - простое. Вычеркнем из списка все числа кратные 2 (кроме 2). Первое из оставшихся-число 3, будет простым. Вычеркнем из списка все числа кратные 3 (кроме числа 3). Первое из оставшихся-число 5, будет простым. Затем вычеркнем все числа, кратные 5 (кроме числа 5) и так далее.

Алгоритм остановится, когда не вычеркнутое число станет больше, чем
. Действительно, по свойству 2, все составные числа в нашем списке имеют делитель
. Значит, они уже вычеркнуты.

Все остальные числа - простые.

Пример . Найти все простые числа на промежутке от 2 до 100.

Решение. Вычеркнем (выделим) числа, кратные 2 (рис. 1).

Следующее простое число
все остальные числа - простые (рис. 5).

Замечание . Если p - первое, не вычеркнутое число, то все числа меньше уже вычеркнуты.
Вычеркивать кратные числу p можно начинать с .

п. 2 Факторизация.

Составное число 495 имеет делитель 5, значит
. Второй сомножитель также число составное
. Продолжая процесс, можно исходно число разложить на множители

Определение . Факторизацией составного числа N называется разложение N на простые множители.

Самый очевидный способ факторизации числа N сводится к перебору всех возможных простых делителей,
.

Пример . Разложить на множитель число 323.

Заметим, что
. Значит, делитель нужно искать среди простых чисел
. Перебирая их по очереди находим, что

Пример . Доказать, что 919 - простое число.

Так как
, то наименьший простой делитель не превосходит 29. Проверкой убедимся, что 919 не делится на простые числа .
- простое число.

Для больших натуральных чисел рассмотренный способ неэффективен. Многие математики искали более простые способы факторизации, требующие меньшего объема вычислений.

I. Метод Ферма.

Пусть N - данное число,
. Образуем числа

Если одно из них окажется точным квадратом, то получим равенство
, или
.

Перебор следует вести в плоть до значения
. (В этом случае
и
). Если точный квадрат не встретился, то N - простое число.

Пример . Разложить на множители N =9271.

Имеем
, значит m=97. вычислим последовательно: .

II. Метод Эйлера.

Эйлер предложил записывать число N в виде суммы
, где d - специально подобранный множитель такой, что НОД (x , yd )=1. величина d зависит от вида числа N . Так, если N =4k +1, то d =1, если N =6k +1, то d =3 и т.д. Всего Эйлер указал 65 множителей d для разных видов N .

Если N представлено в виде
двумя способами (с одним и тем же d ), то N можно разложить на множители.

Например, пусть

Тогда , где НОД (u,v)=1.

Получаем систему:
и

решая которые, находим: .

Пример . Разложить на множители N = 2197.

Отсюда, u=2, v=3, t=10, s=24.

.

III. Ряд приемов основан на простых алгебраических тождествах. Например, теорема Софии Жермен утверждает, что
- составное число.

Это следует из того, что и при N >1 оба множителя больше 1.

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

п.3. О формулах, генерирующих простые числа.

Долгое время математики пытались найти формулу, позволяющие вычислить сколько угодно большое простое число. Наибольшую известность получила формула Мерсенна.
и числа Ферма .

Определение .
- числа Мерсенна.

Для составных значений
число
делится на и значит, не будет простым.

Пусть N - простое число. Тогда, - простые числа.

Но уже
, таким образом, простота числа p не гарантирует простату
.

Простыми оказались числа Мерсенна при .

Простоту числа
(записываемого 139 цифрами) доказал в 1876 году французский математик Э. Люка.

Дальнейший поиск простых чисел Месенна продолжился с помощью вычислительной техники.

Наиболее известное (на 2011 год) простое число является 46–м числом Мерсенна. Это
. Для его записи требуется около 13 миллионов цифр.

Основой для вычислительных алгоритмов служит критерий простоты чисел
, указанный Люка в 1878 году и усовершенствованный Лемером в 1930.

Критерий Люка – Лемера.

Число
простое тогда и только тогда, когда в рекуррентной последовательности
член
делится на
.

На сегодняшний день неизвестно, конечно или бесконечно множество чисел Мерсена.

Определение .
- числа Ферма.

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

Ферма предположил (1650), что все числа такого вида будут простыми. Однако Эйлер показал (1739), что .

В настоящее время неизвестно, имеются ли другие простые числа Ферма при
.

С помощью чисел Ферма можно получить другое доказательство теоремы Эвклида.

Теорема (Пойа).

Любые два числа Ферма взаимно просты.

Доказательство . Пусть и
- произвольные числа Ферма.

Покажем, что
делится на . В самом деле, делится на х+1, т.е. на .

Пусть m - общий делитель и
. Тогда и так как
, значит,
. Но числа Ферма нечетные

Следствие . Простых чисел бесконечно много.

Доказательство . каждое из
имеет нечетный делитель, который не делит остальные числа Ферма следовательно, есть по меньшей мере N простых нечетных чисел,
простых чисел бесконечно много.

Замечание . Простые числа Ферма неожиданно появляются в задаче о построении правильного N –угольника с помощью циркуля и линейки. Гаусс доказал, что построение возможно тогда и только тогда, когда
, где - простые числа Ферма.

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

Эйлер обратил внимание на многочлены:
, задающий простые числа при
и , принимающий простые значения при
.

Позднее была доказана следующая теорема.

Теорема (Гольдбах).

Никакой многочлен
с целыми коэффициентами не может принимать простые значения
при всех
.

Доказательство . Пусть , пусть
- простое число.

Тогда по формуле Тейлора: .

Все коэффициенты
- целые числа
делится на р.

Если попробовать, чтобы значения
были простыми, то
при всех целых t, но это противоречит тому, что
.