1 является простым числом. Простые числа. Составные числа. Вариации и обобщения

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

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 простое число.

Простым числом является натуральное число, которое делится только на себя и на единицу.

Определение 1. Простое число − это натуральное число больше единицы, которое делится только на себя и на 1.

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

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

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

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

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

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

Утверждение 1. Если p - простое число и a любое целое число, то либо a делится на p , либо p и a взаимно простые числа.

Действительно. Если p простое число, то оно делится только на себя и на 1, если a не делится на p , то наибольший общий делитель a и p равен 1. Тогда p и a взаимно простые числа.

Утверждение 2. Если произведение нескольких чисел чисел a 1 , a 2 , a 3 , ... делится на простое число p , то по крайней мере одно из чисел a 1 , a 2 , a 3 , ... делится на p .

Действительно. Если бы ни одно из чисел не делилось на p , то числа a 1 , a 2 , a 3 , ... были бы взаимно простые числа по отношению p . Но из следствия 3 () следует, что их произведение a 1 , a 2 , a 3 , ... также взаимно простое по отношению к p , что противоречит условию утверждения. Следовательно по крайней мере один из чисел делится на p .

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

Доказательство. Пусть k составное число, и пусть a 1 один из его делителей отличное от 1 и самого себя. Если a 1 составное, то имеет кроме 1 и a 1 и другой делитель a 2 . Если a 2 число составное, то имеет кроме 1 и a 2 и другой делитель a 3 . Рассуждая таким образом и учитывая, что числа a 1 , a 2 , a 3 , ... убывают и этот ряд содержит конечное число членов, мы дойдем какого-то простого числа p 1 . Тогда k можно представить в виде

Допустим существует два разложения числа k :

Так как k=p 1 p 2 p 3 ... делится на простое число q 1 , то по крайней мере один из множителей, например p 1 делится на q 1 . Но p 1 простое число и делится только на 1 и на себя. Следовательно p 1 =q 1 (т.к. q 1 ≠1)

Тогда из (2) можно исключить p 1 и q 1:

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

Разложение составного числа k можно записать в следующем виде

(3)

где p 1 , p 2 , ... различные простые числа, α, β, γ ... целые положительные числа.

Разложение (3) называется каноническим разложением числа.

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

Теорема 2. Количество простых чисел бесконечно много.

Доказательство. Предположим, что существует конечное число простых чисел, и пусть наибольшее простое число равно p . Рассмотрим все числа больше p . По предположению утверждения эти числа должны быть составными и должны делится по крайней мере на один из простых чисел. Выберем число, являющиеся произведением всех этих простых чисел плюс 1:

Число z больше p так как 2p уже больше p . p не делится ни на одно из этих простых чисел, т.к. при делении на каждое из них дает остаток 1. Таким образом мы приходим к противоречию. Следовательно существует бесчисленное множество простых чисел.

Данная теорема является частным случаем более общей теоремы:

Теорема 3. Пусть задана арифметическая прогрессия

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

Справедливо и обратное. Если каждый простой множитель числа n входит по крайней мере столько же раз в число m , то m делится на n .

Утверждение 3. Пусть a 1 ,a 2 ,a 3 ,... различные простые числа входящие в m так, что

где i =0,1,...α , j =0,1,...,β , k=0,1,...,γ . Заметим, что α i принимает α +1 значений, β j принимает β +1 значений, γ k принимает γ +1 значений, ... .

На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема 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 . Доказательство этого факта было дано Евклидом и известно как лемма Евклида . Оно используется в доказательстве основной теоремы арифметики .
• Кольцо вычетов $\backslash 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$, такое, что (постулат Бертрана).
• Ряд чисел, обратных к простым , расходится. Более того, при $x\backslash to\backslash infty$
• Любая арифметическая прогрессия вида $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 .

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

В разное время предпринимались попытки указать выражение, значениями которого при разных значениях входящих в него переменных были бы простые числа . Л. Эйлер указал многочлен $\backslash 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 - составное .

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

• $\backslash 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,\backslash ;0,\backslash ;1,\backslash ;\backslash ldots$ Целые числа $-1,\backslash ;1,\backslash ;\backslash frac\{1\}\{2\},\backslash ;\backslash ;0\{,\}12,\backslash frac\{2\}\{3\},\backslash ;\backslash ldots$ Рациональные числа $-1,\backslash ;1,\backslash ;\backslash ;0\{,\}12,\backslash frac\{1\}\{2\},\backslash ;\backslash pi,\backslash ;\backslash sqrt\{2\},\backslash ;\backslash ldots$ Вещественные числа

$-1,\backslash ;\backslash frac\{1\}\{2\},\backslash ;0\{,\}12,\backslash ;\backslash pi,\backslash ;3i+2,\backslash ;e^\{i\backslash pi/3\},\backslash ;\backslash ldots$

Комплексные числа

$1,\backslash ;i,\backslash ;j,\backslash ;k,\backslash ;2i\; +\; \backslash pi\; j-\backslash frac\{1\}\{2\}k,\backslash ;\backslash dots$ Кватернионы $1,\backslash ;i,\backslash ;j,\backslash ;k,\backslash ;l,\backslash ;m,\backslash ;n,\backslash ;o,\backslash ;2\; -\; 5l\; +\; \backslash frac\{\backslash pi\}\{3\}m,\backslash ;\backslash dots$ Октонионы $1,\backslash ;e\_1,\backslash ;e\_2,\backslash ;\backslash dots,\backslash ;e\_\{15\},\backslash ;7e\_2\; +\; \backslash frac\{2\}\{5\}e\_7\; -\; \backslash frac\{1\}\{3\}e\_\{15\},\backslash ;\backslash dots$ Седенионы |заголовок5= Другие
числовые системы |заголовок6= См. также

Общие сведения Факторизационные формы С ограниченными делителями Числа с многими делителями Связанные с аликвотными последовательностями Другое

Отрывок, характеризующий Простое число

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

Наташа была спокойнее, но не веселее. Она не только избегала всех внешних условий радости: балов, катанья, концертов, театра; но она ни разу не смеялась так, чтобы из за смеха ее не слышны были слезы. Она не могла петь. Как только начинала она смеяться или пробовала одна сама с собой петь, слезы душили ее: слезы раскаяния, слезы воспоминаний о том невозвратном, чистом времени; слезы досады, что так, задаром, погубила она свою молодую жизнь, которая могла бы быть так счастлива. Смех и пение особенно казались ей кощунством над ее горем. О кокетстве она и не думала ни раза; ей не приходилось даже воздерживаться. Она говорила и чувствовала, что в это время все мужчины были для нее совершенно то же, что шут Настасья Ивановна. Внутренний страж твердо воспрещал ей всякую радость. Да и не было в ней всех прежних интересов жизни из того девичьего, беззаботного, полного надежд склада жизни. Чаще и болезненнее всего вспоминала она осенние месяцы, охоту, дядюшку и святки, проведенные с Nicolas в Отрадном. Что бы она дала, чтобы возвратить хоть один день из того времени! Но уж это навсегда было кончено. Предчувствие не обманывало ее тогда, что то состояние свободы и открытости для всех радостей никогда уже не возвратится больше. Но жить надо было.
Ей отрадно было думать, что она не лучше, как она прежде думала, а хуже и гораздо хуже всех, всех, кто только есть на свете. Но этого мало было. Она знала это и спрашивала себя: «Что ж дальше?А дальше ничего не было. Не было никакой радости в жизни, а жизнь проходила. Наташа, видимо, старалась только никому не быть в тягость и никому не мешать, но для себя ей ничего не нужно было. Она удалялась от всех домашних, и только с братом Петей ей было легко. С ним она любила бывать больше, чем с другими; и иногда, когда была с ним с глазу на глаз, смеялась. Она почти не выезжала из дому и из приезжавших к ним рада была только одному Пьеру. Нельзя было нежнее, осторожнее и вместе с тем серьезнее обращаться, чем обращался с нею граф Безухов. Наташа Осссознательно чувствовала эту нежность обращения и потому находила большое удовольствие в его обществе. Но она даже не была благодарна ему за его нежность; ничто хорошее со стороны Пьера не казалось ей усилием. Пьеру, казалось, так естественно быть добрым со всеми, что не было никакой заслуги в его доброте. Иногда Наташа замечала смущение и неловкость Пьера в ее присутствии, в особенности, когда он хотел сделать для нее что нибудь приятное или когда он боялся, чтобы что нибудь в разговоре не навело Наташу на тяжелые воспоминания. Она замечала это и приписывала это его общей доброте и застенчивости, которая, по ее понятиям, таковая же, как с нею, должна была быть и со всеми. После тех нечаянных слов о том, что, ежели бы он был свободен, он на коленях бы просил ее руки и любви, сказанных в минуту такого сильного волнения для нее, Пьер никогда не говорил ничего о своих чувствах к Наташе; и для нее было очевидно, что те слова, тогда так утешившие ее, были сказаны, как говорятся всякие бессмысленные слова для утешения плачущего ребенка. Не оттого, что Пьер был женатый человек, но оттого, что Наташа чувствовала между собою и им в высшей степени ту силу нравственных преград – отсутствие которой она чувствовала с Kyрагиным, – ей никогда в голову не приходило, чтобы из ее отношений с Пьером могла выйти не только любовь с ее или, еще менее, с его стороны, но даже и тот род нежной, признающей себя, поэтической дружбы между мужчиной и женщиной, которой она знала несколько примеров.
В конце Петровского поста Аграфена Ивановна Белова, отрадненская соседка Ростовых, приехала в Москву поклониться московским угодникам. Она предложила Наташе говеть, и Наташа с радостью ухватилась за эту мысль. Несмотря на запрещение доктора выходить рано утром, Наташа настояла на том, чтобы говеть, и говеть не так, как говели обыкновенно в доме Ростовых, то есть отслушать на дому три службы, а чтобы говеть так, как говела Аграфена Ивановна, то есть всю неделю, не пропуская ни одной вечерни, обедни или заутрени.
Графине понравилось это усердие Наташи; она в душе своей, после безуспешного медицинского лечения, надеялась, что молитва поможет ей больше лекарств, и хотя со страхом и скрывая от доктора, но согласилась на желание Наташи и поручила ее Беловой. Аграфена Ивановна в три часа ночи приходила будить Наташу и большей частью находила ее уже не спящею. Наташа боялась проспать время заутрени. Поспешно умываясь и с смирением одеваясь в самое дурное свое платье и старенькую мантилью, содрогаясь от свежести, Наташа выходила на пустынные улицы, прозрачно освещенные утренней зарей. По совету Аграфены Ивановны, Наташа говела не в своем приходе, а в церкви, в которой, по словам набожной Беловой, был священник весьма строгий и высокой жизни. В церкви всегда было мало народа; Наташа с Беловой становились на привычное место перед иконой божией матери, вделанной в зад левого клироса, и новое для Наташи чувство смирения перед великим, непостижимым, охватывало ее, когда она в этот непривычный час утра, глядя на черный лик божией матери, освещенный и свечами, горевшими перед ним, и светом утра, падавшим из окна, слушала звуки службы, за которыми она старалась следить, понимая их. Когда она понимала их, ее личное чувство с своими оттенками присоединялось к ее молитве; когда она не понимала, ей еще сладостнее было думать, что желание понимать все есть гордость, что понимать всего нельзя, что надо только верить и отдаваться богу, который в эти минуты – она чувствовала – управлял ее душою. Она крестилась, кланялась и, когда не понимала, то только, ужасаясь перед своею мерзостью, просила бога простить ее за все, за все, и помиловать. Молитвы, которым она больше всего отдавалась, были молитвы раскаяния. Возвращаясь домой в ранний час утра, когда встречались только каменщики, шедшие на работу, дворники, выметавшие улицу, и в домах еще все спали, Наташа испытывала новое для нее чувство возможности исправления себя от своих пороков и возможности новой, чистой жизни и счастия.
В продолжение всей недели, в которую она вела эту жизнь, чувство это росло с каждым днем. И счастье приобщиться или сообщиться, как, радостно играя этим словом, говорила ей Аграфена Ивановна, представлялось ей столь великим, что ей казалось, что она не доживет до этого блаженного воскресенья.
Но счастливый день наступил, и когда Наташа в это памятное для нее воскресенье, в белом кисейном платье, вернулась от причастия, она в первый раз после многих месяцев почувствовала себя спокойной и не тяготящеюся жизнью, которая предстояла ей.
Приезжавший в этот день доктор осмотрел Наташу и велел продолжать те последние порошки, которые он прописал две недели тому назад.
– Непременно продолжать – утром и вечером, – сказал он, видимо, сам добросовестно довольный своим успехом. – Только, пожалуйста, аккуратнее. Будьте покойны, графиня, – сказал шутливо доктор, в мякоть руки ловко подхватывая золотой, – скоро опять запоет и зарезвится. Очень, очень ей в пользу последнее лекарство. Она очень посвежела.
Графиня посмотрела на ногти и поплевала, с веселым лицом возвращаясь в гостиную.

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

Ответ Ильи корректный, но не очень подробный. В 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.

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

• Если - простое, и делит , то делит или . Доказательство этого факта было дано Евклидом и известно как лемма Евклида . Оно используется в доказательстве основной теоремы арифметики .
• Кольцо вычетов является полем тогда и только тогда, когда - простое.
• Характеристика каждого поля - это ноль или простое число.
• Если - простое, а - натуральное, то делится на (малая теорема Ферма).
• Если - конечная группа с элементов, то содержит элемент порядка .
• Если - конечная группа, и - максимальная степень , которая делит , то имеет подгруппу порядка , называемую силовской подгруппой , более того, количество силовских подгрупп равно для некоторого целого (теоремы Силова).
• Натуральное является простым тогда и только тогда, когда делится на (теорема Вильсона).
• Если - натуральное, то существует простое , такое, что (постулат Бертрана).
• Ряд чисел, обратных к простым, расходится. Более того, при
• Любая арифметическая прогрессия вида , где - целые взаимно простые числа , содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
• Всякое простое число, большее 3, представимо в виде или , где - некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k>1) одинакова, то она обязательно кратна 6 - например: 251-257-263-269; 199-211-223; 20183-20201-20219.
• Если - простое, то кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3) .
• Теорема Грина-Тао. Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел .
• n >2, k >1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид , то k - простое (см. числа Мерсенна).
• Никакое простое число не может иметь вид , где n >1, k >0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бо́льшим 1 .

содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа - 5 при 42 переменных; наименьшее число переменных - 10 при степени около 15905. Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества .

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

Распределение простых чисел p n = f (Δs n ); Δs n = p n +1 ² - p n ². Δp n = p n +1 - p n ; Δp n = 2, 4, 6, … .

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

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

Приложения

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

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

См. также

Примечания

Литература

• Гальперин Г. «Просто о простых числах» // Квант . - № 4. - С. 9-14,38.
• Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. - Питер, 2001. - 288 с. - ISBN 5-318-00443-1
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии . - М .: МЦНМО , 2003. - 328 с. - ISBN 5-94057-103-4
• Черемушкин А. В. . - М .: МЦНМО , 2002. - 104 с. - ISBN 5-94057-060-7
• Кноп К. «В погоне за простотой»
• Кордемский Б. А. Математическая смекалка . - М .: ГИФМЛ, 1958. - 576 с.
• Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker"s Delight. - М .: «Вильямс», 2007. - 288 с. - ISBN 0-201-91465-4
• Ю. Матиясевич. Формулы для простых чисел // Квант . - 1975. - № 5. - С. 5-13.
• Н. Карпушина. Палиндромы и «перевёртыши» среди простых чисел // Наука и жизнь . - 2010. - № 5.
• Д. Цагер. Первые 50 миллионов простых чисел // Успехи математических наук . - 1984. - Т. 39. - № 6(240). - С. 175–190.

Ссылки

• The Prime Pages (англ.) - база данных наибольших известных простых чисел
• PrimeGrid prime lists - все простые числа, найденные в рамках проекта PrimeGrid
• Геометрия простых и совершенных чисел (исп.)

Числовые системы
Счётные множества	Натуральные числа () Целые () Рациональные () Алгебраические () Периоды Вычислимые Арифметические
Вещественные числа и их расширения	Вещественные () Комплексные ()