Простые числа. Составные числа. Числа. Простые числа §2 Простые числа

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

Навигация по странице.

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

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

Определение.

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

Определение.

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

Отдельно заметим, что число 1 не относится ни к простым, ни к составным числам. Единица имеет только один положительный делитель, которым является само число 1 . Этим число 1 отличается от всех остальных целых положительных чисел, которые имеют не менее двух положительных делителей.

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

Определение.

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

Определение.

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

Отметим, что каждое целое положительное число, большее единицы, есть либо простое, либо составное число. Иными словами, не существует ни одного такого целого числа, которое не являлось бы ни простым, ни составным. Это следует из свойства делимости , которое гласит, что числа 1 и a всегда являются делителями любого целого числа a .

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

Определение.

Натуральные числа, которые не являются простыми, называются составными .

Приведем примеры простых и составных чисел .

В качестве примеров составных чисел приведем 6 , 63 , 121 и 6 697 . Это утверждение тоже нуждается в пояснении. Число 6 имеет кроме положительных делителей 1 и 6 еще и делители 2 и 3 , так как 6=2·3 , поэтому 6 – действительно составное число. Положительными делителями 63 являются числа 1 , 3 , 7 , 9 , 21 и 63 . Число 121 равно произведению 11·11 , поэтому его положительными делителями являются 1 , 11 и 121 . А число 6 697 составное, так как его положительными делителями кроме 1 и 6 697 являются еще и числа 37 и 181 .

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

Таблица простых чисел

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

Возникает логичный вопрос: «Почему мы заполнили таблицу простых чисел только до 1 000 , разве нельзя составить таблицу всех существующих простых чисел»?

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

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

Теорема.

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

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

Пусть a – натуральное число, большее единицы, и b – наименьший положительный и отличный от единицы делитель числа a . Докажем, что b – простое число методом от противного.

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

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

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

Теорема.

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

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

Предположим, что это не так. То есть, предположим, что простых чисел всего 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.

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

Алгоритмы поиска и распознавания простых чисел

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают решето Эратосфена , решето Сундарама и решето Аткина .
Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты . Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера - Рабина) и используются для нужд криптографии . В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала - Каяла - Саксены имеет довольно большую вычислительную сложность , что затрудняет его практическое применение.
Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

Бесконечность множества простых чисел

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах » (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма величин, обратных к первым n простым числам, неограниченно растёт с ростом n .
Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты : теста Люка - Лемера . Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.
За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов США . Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

Простые числа специального вида

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

Для поиска простых чисел обозначенных типов в настоящее время используются проекты распределенных вычислений GIMPS , PrimeGrid , Ramsey@Home , Seventeen or Bust , Riesel Sieve , Wieferich@Home .

Некоторые свойства

Если p - простое, и p делит ab , то p делит a или b . Доказательство этого факта было дано Евклидом и известно как лемма Евклида . Оно используется в доказательстве основной теоремы арифметики .

Кольцо вычетов $\mathbb{Z}_n$ является полем тогда и только тогда, когда $n$ - простое.

Характеристика каждого поля - это ноль или простое число.

Если $p$ - простое, а $a$ - натуральное, то $a^p-a$ делится на $p$ (малая теорема Ферма).

Если $G$ - конечная группа, порядок которой $|G|$ делится на $p$ , то $G$ содержит элемент порядка $p$ (теорема Коши).

Если $G$ - конечная группа, и $p^n$ - максимальная степень $p$ , которая делит $|G|$ , то $G$ имеет подгруппу порядка $p^n$ , называемую силовской подгруппой , более того, количество силовских подгрупп равно $pk+1$ для некоторого целого $k$ (теоремы Силова).

Натуральное $p > 1$ является простым тогда и только тогда, когда $(p-1)! + 1$ делится на $p$ (теорема Вильсона).

Если $n > 1$ - натуральное, то существует простое $p$ , такое, что $n < p < 2 n$ (постулат Бертрана).

Ряд чисел, обратных к простым , расходится. Более того, при $x\to\infty$ $\sum_{p$

Любая арифметическая прогрессия вида $a, a + q, a + 2 q, a + 3 q, ...$ , где $a, q > 1$ - целые взаимно простые числа , содержит бесконечно много простых чисел (теорема Дирихле о простых числах в арифметической прогрессии) .

Всякое простое число, большее 3, представимо в виде $6k+1$ или $6k-1$ , где $k$ - некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k>1) одинакова, то она обязательно кратна 6 - например: 251-257-263-269; 199-211-223; 20183-20201-20219.

Если $p > 3$ - простое, то $p^2-1$ кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3) .

Теорема Грина-Тао . Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел .

$n^k-1$ , где n >2, k >1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид $2^k-1$ , то k - простое (см. числа Мерсенна).

Никакое простое число не может иметь вид $n^{2k+1}+1$ , где n >1, k >0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бо́льшим 1 .

Формулы для нахождения простых чисел

В разное время предпринимались попытки указать выражение, значениями которого при разных значениях входящих в него переменных были бы простые числа . Л. Эйлер указал многочлен $\textstyle n^2-n+41,$ принимающий простые значения при n = 0, 1, 2, …, 40 . Однако при n = 41 значение многочлена является составным числом. Можно доказать, что не существует многочлена от одной переменной n , который принимает простые значения при всех целых n . П. Ферма предположил, что все числа вида 2 2 k + 1 простые; однако Эйлер опроверг эту гипотезу, доказав, что число 2 2 5 + 1 = 4 294 967 297 - составное .
Тем не менее, существуют многочлены, множество положительных значений которых при неотрицательных значениях переменных совпадает с множеством простых чисел. Одним из примеров является многочлен

$\begin{align}$

&(k+2) (1 - ^2 - [(gk + 2g + k + 1)(h + j) + h - z]^2 - ^2 - \\ &^2 - ^2 - [(a^2 - 1)y^2 + 1 - x^2]^2 - \\ &^2 - [((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2]^2 - ^2 - \\ &[(a^2 - 1)l^2 + 1 - m^2]^2 - ^2 - ^2 - \\ &^2 - ^2) \end{align} содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа - 5 при 42 переменных; наименьшее число переменных - 10 при степени около 1,6·10 45 . Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества .

Открытые вопросы

До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе :

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

Приложения

Большие простые числа (порядка 10 300 ) используются в криптографии с открытым ключом . Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ «Вихрь Мерсенна »).

Вариации и обобщения

В теории колец , разделе общей алгебры , определено понятие простого элемента и простого идеала .

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

См. также

Напишите отзыв о статье "Простое число"
Примечания
|заголовок3= Инструменты расширения
числовых систем |заголовок4= Иерархия чисел |список4=

$-1,\;0,\;1,\;\ldots$ Целые числа

$-1,\;1,\;\frac{1}{2},\;\;0{,}12,\frac{2}{3},\;\ldots$ Рациональные числа

$-1,\;1,\;\;0{,}12,\frac{1}{2},\;\pi,\;\sqrt{2},\;\ldots$ Вещественные числа

$-1,\;\frac{1}{2},\;0{,}12,\;\pi,\;3i+2,\;e^{i\pi/3},\;\ldots$ Комплексные числа
$1,\;i,\;j,\;k,\;2i + \pi j-\frac{1}{2}k,\;\dots$ Кватернионы $1,\;i,\;j,\;k,\;l,\;m,\;n,\;o,\;2 - 5l + \frac{\pi}{3}m,\;\dots$ Октонионы $1,\;e_1,\;e_2,\;\dots,\;e_{15},\;7e_2 + \frac{2}{5}e_7 - \frac{1}{3}e_{15},\;\dots$ Седенионы |заголовок5= Другие
числовые системы |заголовок6= См. также

Общие сведения

Факторизационные формы

С ограниченными делителями

Числа с многими делителями

Связанные с аликвотными
последовательностями

Другое

Отрывок, характеризующий Простое число
Получив известие о болезни Наташи, графиня, еще не совсем здоровая и слабая, с Петей и со всем домом приехала в Москву, и все семейство Ростовых перебралось от Марьи Дмитриевны в свой дом и совсем поселилось в Москве.
Болезнь Наташи была так серьезна, что, к счастию ее и к счастию родных, мысль о всем том, что было причиной ее болезни, ее поступок и разрыв с женихом перешли на второй план. Она была так больна, что нельзя было думать о том, насколько она была виновата во всем случившемся, тогда как она не ела, не спала, заметно худела, кашляла и была, как давали чувствовать доктора, в опасности. Надо было думать только о том, чтобы помочь ей. Доктора ездили к Наташе и отдельно и консилиумами, говорили много по французски, по немецки и по латыни, осуждали один другого, прописывали самые разнообразные лекарства от всех им известных болезней; но ни одному из них не приходила в голову та простая мысль, что им не может быть известна та болезнь, которой страдала Наташа, как не может быть известна ни одна болезнь, которой одержим живой человек: ибо каждый живой человек имеет свои особенности и всегда имеет особенную и свою новую, сложную, неизвестную медицине болезнь, не болезнь легких, печени, кожи, сердца, нервов и т. д., записанных в медицине, но болезнь, состоящую из одного из бесчисленных соединений в страданиях этих органов. Эта простая мысль не могла приходить докторам (так же, как не может прийти колдуну мысль, что он не может колдовать) потому, что их дело жизни состояло в том, чтобы лечить, потому, что за то они получали деньги, и потому, что на это дело они потратили лучшие годы своей жизни. Но главное – мысль эта не могла прийти докторам потому, что они видели, что они несомненно полезны, и были действительно полезны для всех домашних Ростовых. Они были полезны не потому, что заставляли проглатывать больную большей частью вредные вещества (вред этот был мало чувствителен, потому что вредные вещества давались в малом количестве), но они полезны, необходимы, неизбежны были (причина – почему всегда есть и будут мнимые излечители, ворожеи, гомеопаты и аллопаты) потому, что они удовлетворяли нравственной потребности больной и людей, любящих больную. Они удовлетворяли той вечной человеческой потребности надежды на облегчение, потребности сочувствия и деятельности, которые испытывает человек во время страдания. Они удовлетворяли той вечной, человеческой – заметной в ребенке в самой первобытной форме – потребности потереть то место, которое ушиблено. Ребенок убьется и тотчас же бежит в руки матери, няньки для того, чтобы ему поцеловали и потерли больное место, и ему делается легче, когда больное место потрут или поцелуют. Ребенок не верит, чтобы у сильнейших и мудрейших его не было средств помочь его боли. И надежда на облегчение и выражение сочувствия в то время, как мать трет его шишку, утешают его. Доктора для Наташи были полезны тем, что они целовали и терли бобо, уверяя, что сейчас пройдет, ежели кучер съездит в арбатскую аптеку и возьмет на рубль семь гривен порошков и пилюль в хорошенькой коробочке и ежели порошки эти непременно через два часа, никак не больше и не меньше, будет в отварной воде принимать больная.
Что же бы делали Соня, граф и графиня, как бы они смотрели на слабую, тающую Наташу, ничего не предпринимая, ежели бы не было этих пилюль по часам, питья тепленького, куриной котлетки и всех подробностей жизни, предписанных доктором, соблюдать которые составляло занятие и утешение для окружающих? Чем строже и сложнее были эти правила, тем утешительнее было для окружающих дело. Как бы переносил граф болезнь своей любимой дочери, ежели бы он не знал, что ему стоила тысячи рублей болезнь Наташи и что он не пожалеет еще тысяч, чтобы сделать ей пользу: ежели бы он не знал, что, ежели она не поправится, он не пожалеет еще тысяч и повезет ее за границу и там сделает консилиумы; ежели бы он не имел возможности рассказывать подробности о том, как Метивье и Феллер не поняли, а Фриз понял, и Мудров еще лучше определил болезнь? Что бы делала графиня, ежели бы она не могла иногда ссориться с больной Наташей за то, что она не вполне соблюдает предписаний доктора?
– Эдак никогда не выздоровеешь, – говорила она, за досадой забывая свое горе, – ежели ты не будешь слушаться доктора и не вовремя принимать лекарство! Ведь нельзя шутить этим, когда у тебя может сделаться пневмония, – говорила графиня, и в произношении этого непонятного не для нее одной слова, она уже находила большое утешение. Что бы делала Соня, ежели бы у ней не было радостного сознания того, что она не раздевалась три ночи первое время для того, чтобы быть наготове исполнять в точности все предписания доктора, и что она теперь не спит ночи, для того чтобы не пропустить часы, в которые надо давать маловредные пилюли из золотой коробочки? Даже самой Наташе, которая хотя и говорила, что никакие лекарства не вылечат ее и что все это глупости, – и ей было радостно видеть, что для нее делали так много пожертвований, что ей надо было в известные часы принимать лекарства, и даже ей радостно было то, что она, пренебрегая исполнением предписанного, могла показывать, что она не верит в лечение и не дорожит своей жизнью.
Доктор ездил каждый день, щупал пульс, смотрел язык и, не обращая внимания на ее убитое лицо, шутил с ней. Но зато, когда он выходил в другую комнату, графиня поспешно выходила за ним, и он, принимая серьезный вид и покачивая задумчиво головой, говорил, что, хотя и есть опасность, он надеется на действие этого последнего лекарства, и что надо ждать и посмотреть; что болезнь больше нравственная, но…
Графиня, стараясь скрыть этот поступок от себя и от доктора, всовывала ему в руку золотой и всякий раз с успокоенным сердцем возвращалась к больной.
Признаки болезни Наташи состояли в том, что она мало ела, мало спала, кашляла и никогда не оживлялась. Доктора говорили, что больную нельзя оставлять без медицинской помощи, и поэтому в душном воздухе держали ее в городе. И лето 1812 года Ростовы не уезжали в деревню.
Несмотря на большое количество проглоченных пилюль, капель и порошков из баночек и коробочек, из которых madame Schoss, охотница до этих вещиц, собрала большую коллекцию, несмотря на отсутствие привычной деревенской жизни, молодость брала свое: горе Наташи начало покрываться слоем впечатлений прожитой жизни, оно перестало такой мучительной болью лежать ей на сердце, начинало становиться прошедшим, и Наташа стала физически оправляться.
Наташа была спокойнее, но не веселее. Она не только избегала всех внешних условий радости: балов, катанья, концертов, театра; но она ни разу не смеялась так, чтобы из за смеха ее не слышны были слезы. Она не могла петь. Как только начинала она смеяться или пробовала одна сама с собой петь, слезы душили ее: слезы раскаяния, слезы воспоминаний о том невозвратном, чистом времени; слезы досады, что так, задаром, погубила она свою молодую жизнь, которая могла бы быть так счастлива. Смех и пение особенно казались ей кощунством над ее горем. О кокетстве она и не думала ни раза; ей не приходилось даже воздерживаться. Она говорила и чувствовала, что в это время все мужчины были для нее совершенно то же, что шут Настасья Ивановна. Внутренний страж твердо воспрещал ей всякую радость. Да и не было в ней всех прежних интересов жизни из того девичьего, беззаботного, полного надежд склада жизни. Чаще и болезненнее всего вспоминала она осенние месяцы, охоту, дядюшку и святки, проведенные с Nicolas в Отрадном. Что бы она дала, чтобы возвратить хоть один день из того времени! Но уж это навсегда было кончено. Предчувствие не обманывало ее тогда, что то состояние свободы и открытости для всех радостей никогда уже не возвратится больше. Но жить надо было.
Ей отрадно было думать, что она не лучше, как она прежде думала, а хуже и гораздо хуже всех, всех, кто только есть на свете. Но этого мало было. Она знала это и спрашивала себя: «Что ж дальше?А дальше ничего не было. Не было никакой радости в жизни, а жизнь проходила. Наташа, видимо, старалась только никому не быть в тягость и никому не мешать, но для себя ей ничего не нужно было. Она удалялась от всех домашних, и только с братом Петей ей было легко. С ним она любила бывать больше, чем с другими; и иногда, когда была с ним с глазу на глаз, смеялась. Она почти не выезжала из дому и из приезжавших к ним рада была только одному Пьеру. Нельзя было нежнее, осторожнее и вместе с тем серьезнее обращаться, чем обращался с нею граф Безухов. Наташа Осссознательно чувствовала эту нежность обращения и потому находила большое удовольствие в его обществе. Но она даже не была благодарна ему за его нежность; ничто хорошее со стороны Пьера не казалось ей усилием. Пьеру, казалось, так естественно быть добрым со всеми, что не было никакой заслуги в его доброте. Иногда Наташа замечала смущение и неловкость Пьера в ее присутствии, в особенности, когда он хотел сделать для нее что нибудь приятное или когда он боялся, чтобы что нибудь в разговоре не навело Наташу на тяжелые воспоминания. Она замечала это и приписывала это его общей доброте и застенчивости, которая, по ее понятиям, таковая же, как с нею, должна была быть и со всеми. После тех нечаянных слов о том, что, ежели бы он был свободен, он на коленях бы просил ее руки и любви, сказанных в минуту такого сильного волнения для нее, Пьер никогда не говорил ничего о своих чувствах к Наташе; и для нее было очевидно, что те слова, тогда так утешившие ее, были сказаны, как говорятся всякие бессмысленные слова для утешения плачущего ребенка. Не оттого, что Пьер был женатый человек, но оттого, что Наташа чувствовала между собою и им в высшей степени ту силу нравственных преград – отсутствие которой она чувствовала с Kyрагиным, – ей никогда в голову не приходило, чтобы из ее отношений с Пьером могла выйти не только любовь с ее или, еще менее, с его стороны, но даже и тот род нежной, признающей себя, поэтической дружбы между мужчиной и женщиной, которой она знала несколько примеров.
В конце Петровского поста Аграфена Ивановна Белова, отрадненская соседка Ростовых, приехала в Москву поклониться московским угодникам. Она предложила Наташе говеть, и Наташа с радостью ухватилась за эту мысль. Несмотря на запрещение доктора выходить рано утром, Наташа настояла на том, чтобы говеть, и говеть не так, как говели обыкновенно в доме Ростовых, то есть отслушать на дому три службы, а чтобы говеть так, как говела Аграфена Ивановна, то есть всю неделю, не пропуская ни одной вечерни, обедни или заутрени.
Графине понравилось это усердие Наташи; она в душе своей, после безуспешного медицинского лечения, надеялась, что молитва поможет ей больше лекарств, и хотя со страхом и скрывая от доктора, но согласилась на желание Наташи и поручила ее Беловой. Аграфена Ивановна в три часа ночи приходила будить Наташу и большей частью находила ее уже не спящею. Наташа боялась проспать время заутрени. Поспешно умываясь и с смирением одеваясь в самое дурное свое платье и старенькую мантилью, содрогаясь от свежести, Наташа выходила на пустынные улицы, прозрачно освещенные утренней зарей. По совету Аграфены Ивановны, Наташа говела не в своем приходе, а в церкви, в которой, по словам набожной Беловой, был священник весьма строгий и высокой жизни. В церкви всегда было мало народа; Наташа с Беловой становились на привычное место перед иконой божией матери, вделанной в зад левого клироса, и новое для Наташи чувство смирения перед великим, непостижимым, охватывало ее, когда она в этот непривычный час утра, глядя на черный лик божией матери, освещенный и свечами, горевшими перед ним, и светом утра, падавшим из окна, слушала звуки службы, за которыми она старалась следить, понимая их. Когда она понимала их, ее личное чувство с своими оттенками присоединялось к ее молитве; когда она не понимала, ей еще сладостнее было думать, что желание понимать все есть гордость, что понимать всего нельзя, что надо только верить и отдаваться богу, который в эти минуты – она чувствовала – управлял ее душою. Она крестилась, кланялась и, когда не понимала, то только, ужасаясь перед своею мерзостью, просила бога простить ее за все, за все, и помиловать. Молитвы, которым она больше всего отдавалась, были молитвы раскаяния. Возвращаясь домой в ранний час утра, когда встречались только каменщики, шедшие на работу, дворники, выметавшие улицу, и в домах еще все спали, Наташа испытывала новое для нее чувство возможности исправления себя от своих пороков и возможности новой, чистой жизни и счастия.
В продолжение всей недели, в которую она вела эту жизнь, чувство это росло с каждым днем. И счастье приобщиться или сообщиться, как, радостно играя этим словом, говорила ей Аграфена Ивановна, представлялось ей столь великим, что ей казалось, что она не доживет до этого блаженного воскресенья.
Но счастливый день наступил, и когда Наташа в это памятное для нее воскресенье, в белом кисейном платье, вернулась от причастия, она в первый раз после многих месяцев почувствовала себя спокойной и не тяготящеюся жизнью, которая предстояла ей.
Приезжавший в этот день доктор осмотрел Наташу и велел продолжать те последние порошки, которые он прописал две недели тому назад.
– Непременно продолжать – утром и вечером, – сказал он, видимо, сам добросовестно довольный своим успехом. – Только, пожалуйста, аккуратнее. Будьте покойны, графиня, – сказал шутливо доктор, в мякоть руки ловко подхватывая золотой, – скоро опять запоет и зарезвится. Очень, очень ей в пользу последнее лекарство. Она очень посвежела.
Графиня посмотрела на ногти и поплевала, с веселым лицом возвращаясь в гостиную.
В начале июля в Москве распространялись все более и более тревожные слухи о ходе войны: говорили о воззвании государя к народу, о приезде самого государя из армии в Москву. И так как до 11 го июля манифест и воззвание не были получены, то о них и о положении России ходили преувеличенные слухи. Говорили, что государь уезжает потому, что армия в опасности, говорили, что Смоленск сдан, что у Наполеона миллион войска и что только чудо может спасти Россию.
11 го июля, в субботу, был получен манифест, но еще не напечатан; и Пьер, бывший у Ростовых, обещал на другой день, в воскресенье, приехать обедать и привезти манифест и воззвание, которые он достанет у графа Растопчина.
В это воскресенье Ростовы, по обыкновению, поехали к обедне в домовую церковь Разумовских. Был жаркий июльский день. Уже в десять часов, когда Ростовы выходили из кареты перед церковью, в жарком воздухе, в криках разносчиков, в ярких и светлых летних платьях толпы, в запыленных листьях дерев бульвара, в звуках музыки и белых панталонах прошедшего на развод батальона, в громе мостовой и ярком блеске жаркого солнца было то летнее томление, довольство и недовольство настоящим, которое особенно резко чувствуется в ясный жаркий день в городе. В церкви Разумовских была вся знать московская, все знакомые Ростовых (в этот год, как бы ожидая чего то, очень много богатых семей, обыкновенно разъезжающихся по деревням, остались в городе). Проходя позади ливрейного лакея, раздвигавшего толпу подле матери, Наташа услыхала голос молодого человека, слишком громким шепотом говорившего о ней:
– Это Ростова, та самая…
– Как похудела, а все таки хороша!
Она слышала, или ей показалось, что были упомянуты имена Курагина и Болконского. Впрочем, ей всегда это казалось. Ей всегда казалось, что все, глядя на нее, только и думают о том, что с ней случилось. Страдая и замирая в душе, как всегда в толпе, Наташа шла в своем лиловом шелковом с черными кружевами платье так, как умеют ходить женщины, – тем спокойнее и величавее, чем больнее и стыднее у ней было на душе. Она знала и не ошибалась, что она хороша, но это теперь не радовало ее, как прежде. Напротив, это мучило ее больше всего в последнее время и в особенности в этот яркий, жаркий летний день в городе. «Еще воскресенье, еще неделя, – говорила она себе, вспоминая, как она была тут в то воскресенье, – и все та же жизнь без жизни, и все те же условия, в которых так легко бывало жить прежде. Хороша, молода, и я знаю, что теперь добра, прежде я была дурная, а теперь я добра, я знаю, – думала она, – а так даром, ни для кого, проходят лучшие годы». Она стала подле матери и перекинулась с близко стоявшими знакомыми. Наташа по привычке рассмотрела туалеты дам, осудила tenue [манеру держаться] и неприличный способ креститься рукой на малом пространстве одной близко стоявшей дамы, опять с досадой подумала о том, что про нее судят, что и она судит, и вдруг, услыхав звуки службы, ужаснулась своей мерзости, ужаснулась тому, что прежняя чистота опять потеряна ею.
Благообразный, тихий старичок служил с той кроткой торжественностью, которая так величаво, успокоительно действует на души молящихся. Царские двери затворились, медленно задернулась завеса; таинственный тихий голос произнес что то оттуда. Непонятные для нее самой слезы стояли в груди Наташи, и радостное и томительное чувство волновало ее.
«Научи меня, что мне делать, как мне исправиться навсегда, навсегда, как мне быть с моей жизнью… – думала она.
Дьякон вышел на амвон, выправил, широко отставив большой палец, длинные волосы из под стихаря и, положив на груди крест, громко и торжественно стал читать слова молитвы:
– «Миром господу помолимся».
«Миром, – все вместе, без различия сословий, без вражды, а соединенные братской любовью – будем молиться», – думала Наташа.
– О свышнем мире и о спасении душ наших!
«О мире ангелов и душ всех бестелесных существ, которые живут над нами», – молилась Наташа.
Когда молились за воинство, она вспомнила брата и Денисова. Когда молились за плавающих и путешествующих, она вспомнила князя Андрея и молилась за него, и молилась за то, чтобы бог простил ей то зло, которое она ему сделала. Когда молились за любящих нас, она молилась о своих домашних, об отце, матери, Соне, в первый раз теперь понимая всю свою вину перед ними и чувствуя всю силу своей любви к ним. Когда молились о ненавидящих нас, она придумала себе врагов и ненавидящих для того, чтобы молиться за них. Она причисляла к врагам кредиторов и всех тех, которые имели дело с ее отцом, и всякий раз, при мысли о врагах и ненавидящих, она вспоминала Анатоля, сделавшего ей столько зла, и хотя он не был ненавидящий, она радостно молилась за него как за врага. Только на молитве она чувствовала себя в силах ясно и спокойно вспоминать и о князе Андрее, и об Анатоле, как об людях, к которым чувства ее уничтожались в сравнении с ее чувством страха и благоговения к богу. Когда молились за царскую фамилию и за Синод, она особенно низко кланялась и крестилась, говоря себе, что, ежели она не понимает, она не может сомневаться и все таки любит правительствующий Синод и молится за него.
Окончив ектенью, дьякон перекрестил вокруг груди орарь и произнес:
– «Сами себя и живот наш Христу богу предадим».
«Сами себя богу предадим, – повторила в своей душе Наташа. – Боже мой, предаю себя твоей воле, – думала она. – Ничего не хочу, не желаю; научи меня, что мне делать, куда употребить свою волю! Да возьми же меня, возьми меня! – с умиленным нетерпением в душе говорила Наташа, не крестясь, опустив свои тонкие руки и как будто ожидая, что вот вот невидимая сила возьмет ее и избавит от себя, от своих сожалений, желаний, укоров, надежд и пороков.
Графиня несколько раз во время службы оглядывалась на умиленное, с блестящими глазами, лицо своей дочери и молилась богу о том, чтобы он помог ей.

§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, но это противоречит тому, что
.

Единица простое число? Нет, единица не является простым числом.
0 простое число? Нет, ноль не является простым числом.
2 простое число? Да, 2 простое число. 2 является единственным четным простым числом.

3 простое число? Да, 3 простое число.
5 простое число? Да, 5 простое число.
7 простое число? Да, 7 простое число.
9 простое число? Нет, 9 не является простым числом. Ведь 9 делится на себя, на единицу и на три.
11 простое число? Да, 11 простое число.
13 простое число? Да, 13 простое число.
15 простое число? Нет, 15 не является простым числом. Ведь 15 делится на себя, на единицу, на три, на пять.
17 простое число? Да, 17 простое число.
19 простое число? Да, 19 простое число.
20 простое число? Нет, 20 не является простым числом. Ведь 20 делится на себя, на единицу, на два, на четыре, на пять, на десять.
777 простое число? Нет, 777 не является простым числом. Ведь 777 делится на себя, на единицу, на 3, на 7, на 37.
997 простое число? Да, 997 простое число.
Простым числом является натуральное число, которое делится только на себя и на единицу.