Число не являющееся ни простым ни составным. Числа. Простые числа. Формулы для нахождения простых чисел

|заголовок5= Другие
числовые системы |заголовок6= См. также

На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема 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$	Седенионы

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

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

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

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

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

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

Натуральные числа, большие единицы и числа, которые не являются простыми, называют составными числами . Т.о., все натуральные числа делятся на 3 класса: единица (имеет 1 делитель), простые числа (имеют 2 делителя) и составные числа (имеют больше 2-х делителей).

Начало последовательности простых чисел выглядит так:

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, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

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

Самое большое простое число, которое известно.

Самое большое известное простое число - это 2 57885161 - 1. Это число состоит из 17 425 170 десятичных цифр и называется простое число Мерсенна (M 57885161).

Некоторые свойства простых чисел.

Допустим, p — простое, и p делит ab , тогда p делит a либо b .

Кольцо вычетов 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 (постулат Бертрана ).

Ряд чисел, которые обратны к простым, расходится. Кроме того, при .

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

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

Когда p > 3 — простое число, значит, p 2 -1 делится на 24 (работает и на нечётных чисел, которые не делятся на три).

Теорема Грина-Тао . Есть бесконечные арифметические прогрессии, которые состоят из простых чисел.

n k -1 , где n>2, k>1 . Другими словами, число, которое следует за простым, не может быть квадратом либо более высокой степенью с основанием, которое больше двух. Можно сделать вывод, что когда простое число представлено как 2 k -1 , значит k — простое.

Ни одно простое число нельзя представить как n 2k+1 +1 , где n>1, k>0 . Другими словами, число, которое предшествует простому, не может быть кубом либо более высокой нечётной степенью с основанием, которое больше единицы.

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

Этот многочлен содержит 26 переменных, имеет 25. Самая низкая степень для известных многочленов представленного вида — пять при 42 переменных; самое маленькое количество переменных — десять при степени приблизительно 1,6·10 45 .

Действия с простыми числами.

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

2. Разность простых чисел.

3. Сумма простых чисел.

4. Деление простых чисел.

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

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

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа . На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема 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
• Геометрия простых и совершенных чисел (исп.)

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

 

---

Читайте:
Калорийность скумбрии запеченной в фольге в духовке Скумбрия в духовке калорийность на 100 грамм Маш в мультиварке Приготовление маша в мультиварке Варим повидло из красной смородины на зиму – рецепт приготовления смородинового повидла в домашних условиях К чему сильно чешется правое или левое запястье Вычисления пифагора по дате рождения