Простое число

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

Просто́е число́ () — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — {{num1/doit|1={{formatnum:{{}#invoke:String|replace|source=1| ||count={{{count|}> }}}}}}|2={{{sort|02|alt=2}}}|link={}}} и самого себя[2]. Другими словами, число `x` является простым, если оно больше `1` и при этом делится без остатка только на `1` и на `x` . К примеру, `5`  — простое число, а `6` является составным числом, так как, помимо `1` и `6` , также делится на `2` и на `3` . Основная теорема арифметики устанавливает основную роль простых чисел в теории чисел: любое целое число, больше, чем `1` , является простым или может быть выражено как произведение простых чисел, которое является уникальным с точностью до порядка. Уникальность в этой теореме требует исключения `1` как простого числа, потому что можно включать произвольно много 1 в любое разложение, например, `3` , `1` · `3` , `1` · `1` · `3` , и т. д. являются разложением на множители числа `3` [1].

Свойство числа быть простым называется простотой. Простой, но медленный метод проверки простоты заданного числа n известен как перебор делителей. Он состоит из проверки того, является ли `n` кратным целому числу от `2` до `\sqrt{n}` [18]. Алгоритмы, намного более эффективные, чем перебор делителей, были разработаны для проверки простоты больших чисел. К ним относятся Тест Миллера-Рабина, который является быстрым, но имеет небольшую вероятность ошибки и тест AKS, который всегда дает правильный ответ за полиномиальное время, но слишком медленный, чтобы быть использованным[4]. Особенно быстрые методы вычисления доступны для чисел имеющих особые формы, таких как числа Мерсенна.

Многие вопросы, касающиеся простых чисел, остаются открытыми, например, гипотеза Гольдбаха (каждое чётное целое число больше 2 может быть выражено как сумма двух простых чисел) и гипотеза Харди — Литтлвуда (существует бесконечно много пар простых чисел, разность которых равна 2), такие вопросы стимулировали развитие различных отраслей теории чисел, фокусируясь на аналитических или алгебраических аспектах чисел[19]. Простые числа порождают различные обобщения в других областях математики (в основном в алгебре), такие как простые элементы и простые идеалы.

Натуральные числа, которые больше единицы и не являются простыми, называются составными. Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один натуральный делитель), простые числа (имеющие два натуральных делителя) и составные числа (имеющие больше двух натуральных делителей)[2]. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы[20].

Последовательность простых чисел начинается так: : 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, 163, 167, 173, 179, 181, 191, 193, 197, 199[21]

История

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

В сохранившихся записях древних египтян есть намеки на то, что у них были некоторые сведения о простых числах: например, Папирус Райнда относящийся ко 2-му тысячелетию до н. э. содержит в себе таблицу, выражающую дроби вида 2/n через сумму двух, трех или четырёх дробей с числителями равными единице и различными знаменателями. Разложения дробей, знаменатели которых имеют общий делитель, похожи, что свидетельствует о том, что египтяне по-крайней мере знали разницу между простым числом и составным.[23]

Фрагмент Начал Евклида обнаруженный в Оксиринхе

Однако самые ранние сохранившиеся записи о явном изучении простых чисел исходят от древних греков. Начала Евклида (около 300 г. до н. э.) содержат важные теоремы о простых числах, включая бесконечность простых чисел, Лемму Евклида и основную теорему арифметики.[10] В древней Греции также было придумано решето Эратосфена, простой алгоритм нахождения всех простых чисел от 1 до n. После греков мало что произошло в изучении простых чисел до XVII века.[24] В 1640 году Пьер де Ферма сформулировал (без доказательства) малую теорему Ферма (позже доказанную Лейбницем и Эйлером) и теорему о сумме двух квадратов. Ферма также высказал предположение, что все числа вида `2^{2^n}` + 1 — простые (они были названы числами Ферма) и доказал это до n = 4 (или `2^{16}` + 1). Однако Эйлер показал, что уже следующее число Ферма при n = 5 (или `2^{32}` + 1) является составным (делится на число 641). На сегодняшний день нет других известных чисел Ферма, являющихся простыми. В то же время французский монах Марен Мерсенн обратил внимание на простые числа вида 2p — 1, где p — простое (не все числа такого вида являются простыми).[25] Их назвали простыми числами Мерсенна в его честь.

Работа Эйлера в теории чисел включала в себя множество сведений о простых числах. Он показал что бесконечный ряд 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … является расходящимся. Также в 1747 году он показал, что чётные совершенные числа — это целые числа вида `2^{p-1}(2^p -1)` , где второй множитель является простым Мерсенна. В переписке Эйлера с Христианом Гольдбахом, последний сформулировал знаменитую гипотезу Гольдбаха, о представлении любого чётного числа, начиная с 4, в виде суммы простых, которая до сих пор не доказана.[3]

С начала 19 века внимание многих математиков обратилось к изучению асимптотического распределения простых чисел.[3] Лежандр и Гаусс, независимо друг от друга высказали предположение, что плотность простых чисел в среднем близка к величине, обратно пропорциональной натуральному логарифму.[7]

Долгое время считалось, что простые числа имеют чрезвычайно ограниченное применение за пределами чистой математики. Это изменилось в 1970-х годах, когда были изобретены концепции криптографии с открытым ключом, в которых простые числа составляли основу первых алгоритмов, таких как алгоритм шифрования RSA .[6]

Разложение натуральных чисел в произведение простых

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

Основная теорема арифметики

Главная статья: Основная теорема арифметики
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей.[26] Таким образом, простые числа являются элементарными «строительными блоками» натуральных чисел. Например: :

`23244` `= 2 \cdot 2 \cdot 3 \cdot 13 \cdot 149`
квадратную или вторую степень `2` .)
Как было показано в этом примере, один и тот же простой делитель может появляться несколько раз. Разложение: : n = p1 · p2 · ... · pt числа n на (конечное число) простых множителей p1, p2, … ,pt называется разложением на простые множители числа n. Основная теорема арифметики может быть перефразирована, чтобы сказать, что любое разложение на простые числа будет тождественным, за исключением порядка делителей. Таким образом, на практике для большинства чисел есть много простых алгоритмов разложения на множители, все они должны дать тот же результат.[4]

Если p — простое число и p делит произведение ab целых чисел, то p делит a или p делит b. Это предложение известно как Лемма Евклида.[27] Она используется в некоторых доказательствах уникальности разложения на множители.

Простота единицы

Большинство древних греков даже не считали `1` числом, поэтому они не могли считать его простым.[28] К Средним векам и эпохе Возрождения многие математики включали `1` в качестве первого простого числа.[5] В середине XVIII века Христиан Гольдбах внес в список `1` в качестве первого простого числа в своей знаменитой переписке с Леонардом Эйлером; однако сам Эйлер не считал `1` простым числом.See for instance: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160—188. Variae observationes circa series infinitas, Theorema 19, p.187. В XIX веке многие математики по-прежнему считали число `1` простым числом. Например, список простых цифр Деррика Нормана Лемера до `10,006,721` числа, переизданный 1956 году, начинался с `1` в качестве первого простого числа. Говорят, что Анри Лебег является последним математиком, который назвал `1` простым. К началу XX века математики стали приходить к консенсусу о том, что `1` не является простым числом, а скорее формирует свою специальную категорию — «единицу».[5]

Большая часть математической работы по-прежнему будет верной при назывании `1` простым числом, но основная теорема Евклида об арифметике (упомянутая выше) не будет выполняться, как указано. Например, число `15` может быть разложено как 3 · 5 и 1 · 3 · 5. Если бы `1` являлась простым числом, эти два варианта считались бы разными факторизациями `15` , следовательно утверждение этой теоремы пришлось бы изменить.[5] Точно так же решето Эратосфена работало бы неправильно, если бы `1` считалась простым: модифицированная версия решета, которая предполагает, что `1` является простым числом, исключает все множители кратные `1` (то есть все остальные числа) и дает на выходе только одно число — `1` . Кроме того, простые числа имеют несколько свойств, которых нет у числа `1` , таких как отношение числа к его соответствующему значению функции тождества Эйлера или суммы функции делителей.[1]

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

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают решето Эратосфена, решето Сундарама и решето Аткина.[29]

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

Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

Тест простоты

Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число, позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Задача теста простоты относится к классу сложности P, то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в 2002 году.[31]

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Результатом вычислений истинных тестов всегда является факт простоты, либо составности числа. Вероятностный тест показывает является ли число простым с некоторой вероятностью. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми.[32] Одним из примеров таких чисел являются числа Кармайкла.[33]

Одним из примеров истинных тестов простоты является тест Люка-Лемера для чисел Мерсенна. Очевидный недостаток этого теста заключается в его применимости только к ряду чисел определённого вида. Среди других примеров можно привести основанные на малой теореме Ферма[34]

А также: К вероятностным тестам простоты относят:

Большие простые числа

Уже в течение многих столетий поиск «больших» простых чисел вызвал интерес математиков; однако это исследование приобрело особое значение в последние десятилетия из-за необходимости таких чисел, которые используются в алгоритмах, таких как RSA.[6]

Наиболее эффективный метод получения больших простых чисел относится к семнадцатому столетию, когда Марен Мерсенн предположил, что числа вида `2^n + 1` простые (при n ≤ 257) только для n равных 2, 3, 5, 7, 13, 19, 31, 67, 127 и 257.[7] Проверка верности предположения была намного выше возможностей того времени. Только в XX веке было обнаружено, что гипотеза была ложной и, вероятно, сделана «слепо», поскольку Мерсенн не учел три случая (для n = 61, 89 и 107) и не заметил, что числа, соответствующие n = 67 и n = 257 были составными.[7]

Простое число M 127 (39-значное число) было показано Эдуардом Люка в 1876 году и оставалось самым большим известным простым числом до 1951 года, когда были найдены `\frac{2^{148} + 1}{17}` (44 цифры) и, немного позднее, `180 * (2^{127} - 1)^2 + 1` (из 79 цифр) — последнее простое число, которое было найдено с помощью электронного калькулятора. С тех пор все последующие большие простые числа были обнаружены с помощью компьютера: с 1952 года (когда SWAC показал, что M 521 является простым), по 1996 год они были найдены суперкомпьютером, и все были простыми Мерсенна (найденные с использованием теста Люка-Лемера, специфического алгоритма для таких чисел), за исключением числа `391581 * 2^{216193} - 1` , которое было рекордом между 1989 и 1992 годами.[35]

Алгоритмы получения простых чисел

Некоторые задачи математики с использованием факторизации требуют ряд очень больших простых чисел, выбранных случайным образом. Алгоритм их получения, основанный на постулате Бертрана (Для любого натурального n ≥ 2 найдётся простое число p в интервале n < p < 2n.):[36]

Алгоритм:
Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее равномерно. Для простых случайных чисел эти условия выполняются.[8]

Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.[9]

Пусть N, S — нечётные натуральные числа, N-1 = S*R, причем для каждого простого делителя q числа S существует целое число `a` такое, что

`a^{N-1} = 1\pmod{N}` , `\gcd(a^{\frac{N-1}{q} - 1}, n) = 1`

Тогда каждый простой делитель p числа N удовлетворяет сравнению

`p = 1\pmod{2S}`

Следствие. Если выполнены условия теоремы Ферма и `R \leqslant 4S + 2` , то N — простое число.[9]

Покажем теперь, как с помощью последнего утверждения, имея большое простое число `S` , можно построить существенно большее простое число `N` . Выберем для этого случайным образом чётное число `R` на промежутке `R \leqslant 4S + 2` и положим `N = SR + 1` . Затем проверим число `N` на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем `N` некоторое количество раз с помощью алгоритма Рабина. Если при этом выяснится, что `N`  — составное число, следует выбрать новое значение `R` и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число N, выдержавшее испытания алгоритмом Рабина достаточно много раз. В этом случае появляется надежда на то, что `N`  — простое число, и следует попытаться доказать простоту с помощью тестов простоты.[9]

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

Простых чисел бесконечно много. Это утверждение упоминается как теорема Евклида в честь древнегреческого математика Евклида, поскольку первое известное доказательство этого утверждения приписывается ему. Известно ещё много доказательств бесконечности простых чисел, в том числе аналитическое доказательство Эйлера, доказательство Гольдбаха на основе чисел Ферма,[37] доказательство Фурстенберга с использованием общей топологии и элегантное доказательство Куммера.

Доказательство Евклида

Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20[38]). Доказательство рассматривает любое конечное множество S простых чисел. Основная идея — рассмотреть произведение всех этих чисел плюс один:

` N = 1 + \prod_{p\in S} p. `

Как и любое другое натуральное число (кроме 1), N делится хотя бы на одно простое число (возможно, что N является простым).

Ни один из простых делителей числа N, не может быть членом конечного множества S простых чисел, с которого мы начали, поскольку при делении числа N на любое число из множества S дает остаток равный 1. Следовательно простые числа, по которым N раскладывается на множители, являются простыми числами находящимися вне изначального множества. Таким образом, любое конечное множество простых чисел можно расширить на большее конечное множество простых чисел.[39]

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

Доказательство Евклида может быть кратко воспроизведено так:

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

Некоторые связанные доказательства этой теоремы используют так называемые (последовательность {}}}} в OEIS) `E_n=p_n\#+1` , где `p_n\#`  — произведение первых `n` простых чисел (праймориал). При этом формально говоря доказательство, приведенное Евклидом, не использует эти числа: Евклид показывает, что для любого конечного набора простых чисел (не обязательно первых `n` простых чисел) существует простое число, не включенное в этот набор[40].

Аналитическое доказательство Эйлера

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма величин, обратных к первым n простым числам, неограниченно растёт с ростом n.

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

`S(p) = \frac 1 2 + \frac 1 3 + \frac 1 5 + \frac 1 7 + \cdots + \frac 1 p.`

Для любого произвольного вещественного числа х существует простое р, для которого эта частичная сумма больше чем х.[41] Это показывает, что существует бесконечно много простых чисел, так как если бы их существовало конечное число, то сумма достигала бы максимального значения в наибольшем простом числе, а не была бы неограниченной. Точнее, скорость роста S(p) двукратно логарифмическая, что определяется второй теоремой Мертенса. Для сравнения, сумма

`\frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + \cdots + \frac 1 {n^2} = \sum_{i=1}^n \frac 1 {i^2}`

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

` \left( {\frac{1}{3} + \frac{1}{5}} \right) + \left( {\frac{1}{5} + \frac{1}{7}} \right) + \left( {\frac{1} + \frac{1}} \right) + \cdots = \sum\limits_{ \begin{smallmatrix} p \text{ prime, } \\ p + 2 \text { prime} \end{smallmatrix}} {\left( {\frac{1}{p} + \frac{1}} \right)}, `

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

Теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое `\pi(n)` , растёт как `n/\ln(n)` .[42]

Наибольшее известное простое

Главная статья: Наибольшее известное простое число

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа[43]. Один из рекордов поставил в своё время Эйлер, найдя простое число − 1 = 2147483647.

Наибольшим известным простым числом по состоянию является число Мерсенна M77232917 = − 1. Оно содержит 23249425 десятичных цифр; в книге с записью этого числа было бы около девяти тысяч страниц. Его нашли 26 декабря 2017 года в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS. Предыдущее самое большое известное простое число, открытое в январе 2016 года, было на миллион знаков короче[44].

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила[45] денежные призы соответственно в 150 000 и 250 000 долларов США[46]. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

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

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

  • Числа Мерсенна — числа вида `M_n=2^n-1` , где n — натуральное число[12].
  • Числа Ферма — числа вида `F_n=2^{2^n}+1` , где n — неотрицательное целое число[47], однако не доказано, что других простых чисел Ферма нет[48].
  • Числа Вудала — числа вида `W_n=n \cdot 2^n-1` [49].
  • Числа Каллена — числа вида `C_n=n \cdot 2^n+1` [50].
  • Числа Прота — числа вида `P=k \cdot 2^n+1` , причём k нечётно и `2^n>k` [51]. Числа Каллена и числа Ферма являются частным случаем чисел Прота (соответственно при k = n и при k = 1, `n=2^m` ).
  • Числа Миллса — числа вида `P_n = A^{3^n} , ` где `A`  — константа Миллса.

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

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

  • Если p — простое, и p делит ab, то p делит a или b. Доказательство этого факта было дано Евклидом и известно как лемма Евклида[10]. Оно используется в доказательстве основной теоремы арифметики.
  • Кольцо вычетов `\mathbb{Z}_n` является полем тогда и только тогда, когда `n`  — простое[11].
  • Характеристика каждого поля — это ноль или простое число[11].
  • Если `p`  — простое, а `a`  — натуральное, то `a^p-a` делится на `p` (малая теорема Ферма).
  • Если `G`  — конечная группа, порядок которой `|G|` делится на `p` , то `G` содержит элемент порядка `p` (теорема Коши)[15].
  • Если `G`  — конечная группа, и `p^n`  — максимальная степень `p` , которая делит `|G|` , то `G` имеет подгруппу порядка `p^n` , называемую силовской подгруппой, более того, количество силовских подгрупп равно `pk+1` для некоторого целого `k` (теоремы Силова)[52].
  • Натуральное `p > 1` является простым тогда и только тогда, когда `(p-1)! + 1` делится на `p` (теорема Вильсона)[14].
  • Если `n > 1`  — натуральное, то существует простое `p` , такое, что `n < p < 2 n` (постулат Бертрана)[53].
  • Ряд чисел, обратных к простым, расходится[3]. Более того, при `x\to\infty`
  • `\sum_{p
  • Любая арифметическая прогрессия вида ` a, a + q, a + 2 q, a + 3 q, ... ` , где ` a, q > 1`  — целые взаимно простые числа, содержит бесконечно много простых чисел (теорема Дирихле о простых числах в арифметической прогрессии).
  • Всякое простое число, большее 3, представимо в виде `6k+1` или `6k-1` , где `k`  — некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k>1) одинакова, то она обязательно кратна 6 — например: 251-257-263-269; 199-211-223; 20183-20201-20219.
  • Если `p > 3`  — простое, то `p^2-1` кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3)[54].
  • Теорема Грина-Тао. Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел.
  • Никакое простое число не может иметь вид `n^k-1` , где n>2, k>1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид `2^k-1` , то k — простое (см. числа Мерсенна)[12].
  • Никакое простое число не может иметь вид `n^{2k+1}+1` , где n>1, k>0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бо́льшим 1[55].
  • Каждое простое число (кроме чисел вида 8n-1) можно представить в виде суммы трех квадратов.

Применения

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

Арифметические функции

В арифметические функции, а именно функции, определённые на множестве натуральных чисел и принимающих значения во множестве комплексных чисел, играют решающую роль в теории чисел. В частности, среди них наиболее важными являются мультипликативные функции или функции `f` , в которых для каждой паре `(a,b)` взаимно простых чисел ставится в соответствие[13]

`f(ab) = f(a)f(b)`

Примерами мультипликативных функций являются функция Эйлера `\phi` , которая ставит в соответствие числу `n` количество натуральных чисел, меньших n и взаимно простых с ним и функция делителя, которая число n связывает с числом его делителей.[56] Значение этих функций от степени простого числа:

`\phi(p^m) = p^m - p^{m-1}` `\sigma(p^m) = m + 1`

Арифметические функции можно легко вычислить, зная значение, которое они принимают для степеней простых чисел.[13] На самом деле из разложения натурального числа n на множители

`n = p_1^{q_1}\cdot...\cdot p_a^{q_a}`

мы имеем, что

`f(n) = f(p_1^{q_1})\cdot...\cdot f(p_a^{q_a})`

и следовательно, возвращаясь к задаче вычисления `f(n)` получается что вычислить `f` от каждой степени простого делителя, обычно проще, чем вычислить `f` по общей формуле.[57]

Например, чтобы узнать значение функции Эйлера `\phi` от n = 450 = 2 × 3 2 × 5 2, достаточно вычислить

`\phi(450) = \phi(2)\cdot\phi(3^2)\cdot\phi(5^2) = (2-1)\cdot(9-3)\cdot(25-5) = 120`

Модульная арифметика

В модульной арифметике простые числа играют очень важную роль: кольцо вычетов `\mathbb{Z}/n\mathbb{Z}` является полем тогда и только тогда, когда n является простым.[11] Также существование первообразного корня кольца `\mathbb{Z}/n\mathbb{Z}` привязано к простым числам: оно существует, только если n — простое число, 1, 2, 4 или число в форме `p^n\circ2p^n` , где p нечётно.

Одной из важнейших теорем модульной арифметики является малая теорема Ферма.[14] Эта теорема утверждает, что для любого простого числа р и любого натурального числа a имеем:

`a^p \equiv a \pmod{p}`

или для любого простого р и любого натурального а не делящегося на р, справедливо:

`a^{p-1} \equiv 1 \pmod{p}`

Это свойство можно использовать для проверки того, что число не является простым. На самом деле, если n таково, что:

`a^n \not\equiv a \pmod{n}`

для некоторого натурального а, то n не может быть простым.[14] Однако это свойство не может быть использовано для проверки числа на простоту: есть некоторые числа, называемые числами Кармайкла (наименьшее — 561) для которых это будет не верно. Числом Кармайкла называется составное число, которое является псевдопростым числом по каждому основанию b, взаимно простому с n. В 1994 году Уильям Роберт Альфорд, Эндрю Гранвиль и Карл Померанс показали, что таких чисел бесконечно много.[58]

Теория групп

Простые числа также играют основополагающую роль в алгебре. В теории групп, группа, в которой каждый элемент является степенью простого числа р называется р-группой.[59] P-группа является конечной, тогда и только тогда, когда порядок (число его элементов) является степенью р. Примером бесконечной р-группы является p-группой Прюфера.[60] Известно, что p-группы имеют нетривиальный центр и, следовательно, не могут быть простыми (кроме группы с p элементами); если группа конечна, более того, все нормальные подгруппы пересекают центр нетривиальным образом.

Примером таких групп является циклическая группа умножения по модулю простого числа.[61]

Все группы порядка p являются циклическими и поэтому абелевыми; также каждая группа порядка p 2 абелева. Кроме того, любая конечная абелева группа изоморфна прямому произведению конечного числа циклических р-групп.

В теореме Коши утверждается, что Если порядок конечной группы G делится на простое число p, то G содержит элементы порядка p. Эта теорема обобщается теоремами Силова.[15]

Теория колец и теория поля

Простым числом Эйзенштейна называется целое число Эйзенштейна

`z = a + b\omega` `(\omega = e^{2\pi i/3})` ,

являющееся неприводимым (эквивалентно, простым) элементом Zω в смысле теории колец. Делителями простых чисел Эйзенштейна являются только обратимые элементы (±1, ±ω, ±ω2), a + bω и их произведения.[16]

Умножение на обратимый элемент и сопряжение любого простого числа Эйзенштейна также является простым числом Эйзенштейна.

Целое число Эйзенштейна z = a + bω является простым числом Эйзенштейна тогда и только тогда, когда выполняется одно из следующих взаимоисключающих условий:

  1. z является произведением обратимого элемента на натуральное простое вида 3n − 1,
  2. |z|2 = a2ab + b2 является натуральным простым (сравнимым с 0 или 1 по модулю 3).
Отсюда следует, что абсолютное значение квадрата любого целого числа Эйзенштейна является либо простым числом, либо квадратом простого числа.[16]

Криптосистема с открытым ключом

Главная статья: Криптосистема с открытым ключом
Некоторые алгоритмы криптографии с открытым ключом, такие как RSA и обмен ключами Диффи-Хеллмана, основаны на больших простых числах (обычно 1024—2048 бит). RSA полагается на предположение, что намного проще (то есть более эффективно) выполнять умножение двух (больших) чисел x и y, чем вычислять взаимно простые x и y, если известно только их произведение `x\cdot y` . Обмен ключами Диффи-Хеллмана основан на том, что существуют эффективные алгоритмы возведения в степень по модулю, а обратная операция — дискретного логарифмирования считается сложной.[62][63]

RSA

Трудность факторизации больших чисел привела к разработке первого эффективного метода криптографии с открытым ключом — RSA. В этой криптографической системе, человек, который должен получить зашифрованное сообщение, генерирует ключ: выбираются два различных случайных простых числа `p` и `q` заданного размера (обычно используются, 1024- или 2048-битные числа). Далее вычисляется их произведение `n = p * q` , называемое модулем. Вычисляется значение функции Эйлера от числа `n` `\phi(n) = (p - 1)(q - 1)` . Выбирается целое число `e` ( `1 < e < \phi(n)` ), взаимно простое со значением функции `\phi(n)` . Обычно в качестве `e` берут небольшие простые числа (например, простые числа Ферма). Число `e` называется открытой экспонентой (англ. public exponent). Вычисляется число `d` , называемое секретной экспонентой, мультипликативно обратное к числу e по модулю `\phi(n)` . Пара `\{e, n\}` публикуется в качестве открытого ключа RSA (англ. RSA public key). Пара `\{d, n\}` играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.[6]

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

В 1991 году RSA Security опубликовала список полупростых чисел, предлагая денежные призы за разложение некоторых из них на множители, с целью подтверждения безопасности метода и поощрения исследования в этой области: инициатива называлась Challenge RSA Factoring.[17] На протяжении многих лет некоторые из этих чисел были разложены, а для других проблема факторизации все ещё остается открытой; однако конкурс был завершен в 2007 году.[17]

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

В разное время предпринимались попытки указать выражение, значениями которого при разных значениях входящих в него переменных были бы простые числа. Л. Эйлер указал многочлен `\textstyle n^2-n+41,` принимающий простые значения при {{s|n = 0, 1, 2, …, 40}}. Однако при {{s|n = 41}} значение многочлена является составным числом. Можно доказать, что не существует многочлена от одной переменной n, который принимает простые значения при всех целых n. П. Ферма предположил, что все числа вида {{s простые; однако Эйлер опроверг эту гипотезу, доказав, что число + 1 = 4294967297 — составное.

Тем не менее, существуют многочлены, множество положительных значений которых при неотрицательных значениях переменных совпадает с множеством простых чисел. Одним из примеров является многочлен : \begin{align} \bigl(k+2\bigr) \bigl\{1 & - \bigl+ h + j - q\bigr ^2 - \bigl+ 2g + k + 1)(h + j) + h - z\bigr ^2 - \bigl+ p + q + z - e\bigr ^2 \\ & - \bigl+ 1)^3(k + 2)(n + 1)^2 + 1 - f^2\bigr ^2 - \bigl+ 2)(a + 1)^2 + 1 - o^2\bigr ^2 - \bigl- 1)y^2 + 1 - x^2\bigr ^2 \\ & - \bigl- 1) + 1 - u^2\bigr ^2 - \bigl+ u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2\bigr ^2 - \bigl+ l + v - y\bigr ^2 \\ & - \bigl- 1)l^2 + 1 - m^2\bigr ^2 - \bigl+ k + 1 - l - i\bigr ^2 - \bigl+ l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m\bigr ^2 \\ & - \bigl+ y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x\bigr ^2 - \bigl+ pl(a - p) + t(2ap - p^2 - 1) - pm\bigr ^2\bigr\} \end{align} содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа — 5 при 42 переменных; наименьшее число переменных — 10 при степени около 1,6·1045[64]. Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества.

Интересно, что приведённый выше многочлен, который порождает простые числа, сам разлагается на множители. Заметим, что второй множитель этого многочлена (в фигурных скобках) имеет форму: единица минус сумма квадратов. Таким образом, многочлен может принимать положительные значения (при положительных `k` ) только если, каждый из этих квадратов (то есть каждый многочлен в квадратных скобках) равен нулю. В этом случае выражение в фигурных скобках будет равно 1[65].

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

Главная статья: Открытые проблемы в теории чисел

Распределение простых чисел pn = fsn); Δsn = pn+1² — pn². Δpn = pn+1 — pn; Δpn = 2, 4, 6, … .

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

  1. Проблема Гольдбаха (первая проблема Ландау): верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел?
  2. Вторая проблема Ландау: бесконечно ли множество «простых близнецов» — пар простых чисел, разность между которыми равна 2? (в 2013 году математик Чжан Итан из университета Нью-Гэмпшира[66][67] доказал, что существует бесконечно большое количество пар простых чисел, расстояние между которыми не превышает 70 миллионов. Позже, Джеймс Мэйнард улучшил результат до 600. В 2014 году проект под руководством Теренса Тао несколько улучшили последний метод, получив оценку в 246.)
  3. Гипотеза Лежандра (третья проблема Ландау): верно ли, что для всякого натурального числа n между {{power|n|2}} и {{power|(n + 1)|2}} всегда найдётся простое число?
  4. Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида {{power|n|2}} + 1, где n — натуральное число?

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

См. также

Примечания

  1. "«Arguments for and against the primality of 1 ».
  2. — Простое число Математическая энциклопедия (в 5 томах) — М. — Математическая энциклопедия !! — 4, 1977 — http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t4.djvu : Советская Энциклопедия
  3. Apostol, Tom M. Introduction to analytic number theory — https://www.worldcat.org/oclc/1859863 — New York : Springer-Verlag, 1976 — xii, 338 pages — ISBN 0387901639
  4. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие — http://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf — Казань: Казанский университет, 2011 — 190
  5. Why is the number one not prime? (from the Prime Pages' list of frequently asked questions) by Chris K. Caldwell.
  6. Menezes, A. J. (Alfred J.), 1965- Handbook of applied cryptography — https://www.worldcat.org/oclc/35292671 — Boca Raton : CRC Press, 1997 — xxviii, 780 pages — ISBN 9780849385230
  7. Du Sautoy, Marcus. L'enigma dei numeri primi — https://www.worldcat.org/oclc/799339321 — Milano : Rizzoli, 2005 — 606 p. — ISBN 8817008435
  8. Vasilenko, O. N. (Oleg Nikolaevich) Teoretiko-chislovye algoritmy v kriptografii — https://www.worldcat.org/oclc/85690769 — Moskva : MT︠S︡NMO. Moskovskiĭ t︠s︡entr nepreryvnogo matematicheskogo obrazovanii︠a︡, 2006 — 333 pages — ISBN 5940571034
  9. Нестеренко Ю. В. Введение в криптографию : Питер, 2001 — 288
  10. Рыбников К. Русские издания «Начал» Евклида. — http://www.mathnet.ru/links/c2d03cc30a7e6f4b3c40bd7a0d6175ca/rm8809.pdf — Успехи математических наук № 9, 1941 — 318—321
  11. Степанов С. А. Сравнения — http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm — М. : «Знание», 1975 — 64
  12. . При этом число Мерсенна может быть простым, только если n — простое число. Как уже было отмечено выше, эффективным тестом простоты является тест Люка — Лемера
  13. Graham, Ronald L. (1935- ). Konkretnaâ matematika : osnovanie informatiki — https://www.worldcat.org/oclc/1014108083 — Moskva : Izdatelʹstvo "Mir", 1998 — 703, [1] s. — ISBN 5030017933
  14. Виноградов И. М. Основы теории чисел — http://ilib.mccme.ru/djvu/vinogradov.htm — 5 изд. — М.-Л. : Гостехиздат, 1952
  15. Курош А. Г. Теория групп. 3-е изд., М.: Наука, 1967.
  16. Eisenstein Integer--from MathWorld
  17. RSA Laboratories, The RSA Factoring Challenge . Опубликовано 18 мая 2007.
  18. Lindsay N. Childs A Concrete Introduction to Higher Algebra — 3rd — New York, 2009 — 603
  19. . Простые числа используются в нескольких подпрограммах в области информационных технологий, таких как криптосистема с открытым ключом, которая использует такие свойства, как сложность разложения чисел на простые множителиГарднер, Мартин От мозаик Пенроуза к надёжным шифрам — Penrose Tiles to Trapdoor Ciphers / пер. с англ. Ю. А. Данилова — М. : , 1993 — 416 — ISBN 5-03-001991-X — 10000 — Гарднер
  20. Dudley, Underwood Elementary number theory — https://www.worldcat.org/oclc/3844364 — 2d ed — San Francisco : W.H. Freeman, 1978 — ix, 249 pages — ISBN 9780716700760
  21. , см. также список простых чисел
  22. Préhistoire de la géométrie : le problème des sources (PDF) . Site de l’IREM de La Réunion. Voir aussi « Les fables d’Ishango, ou l’irrésistible tentation de la mathématique-fiction» , analyse par O. Keller sur Bibnum
  23. Egyptian Unit Fractions — http://mathpages.com/home/kmath340/kmath340.htm — Mathpages
  24. Prime numbers — John J. O'Connor, Edmund F. Robertson — MacTutor — en
  25. List of Known Mersenne Prime Numbers — Great Internet Mersenne Prime Search
  26. , Section 2, Theorem 2
  27. , Section 2, Lemma 5
  28. См, например, David E. Joyce’s комментарий на Начала (Евклид), Книга VII, определения 1 и 2 .
  29. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers, 1978
  30. Knuth, Donald Ervin, 1938- The art of computer programming — https://www.worldcat.org/oclc/823849 — Reading, Mass. : Addison-Wesley Pub. Co, ©1973-©1981 — 4 volumes — ISBN 0201896842
  31. Б. Шнайер Прикладная криптография — 296—300
  32. Кормен Т., Лейзер Ч. Алгоритмы. Построение и анализ — М. : МЦНМО, 2002 — 765—772
  33. Crandall R., Pomerance C. Prime Numbers: A Computational Perspective : Springer, 2005
  34. Introduction to algorithms — https://www.worldcat.org/oclc/46792720 — 2nd ed — Cambridge, Mass. : MIT Press, 2001 — xxi, 1180 pages — ISBN 0262032937
  35. The Largest Known Prime by Year: A Brief History — Chris Caldwell — The Prime Pages — en
  36. Jitsuro Nagura On the interval containing at least one prime number — https://projecteuclid.org/euclid.pja/1195570997 — EN — Proceedings of the Japan Academy, 1952 — 28 — 4 — 177–181 — 0021-4280 — 10.3792/pja/1195570997
  37. Letter in Латынь from Goldbach to Euler, July 1730.
  38. James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63, English translation of Euclid’s proof
  39. Harry Furstenberg On the Infinitude of Primes — http://www.jstor.org/stable/2307043 — The American Mathematical Monthly, 1955 — 62 — 5 — 353–353 — 10.2307/2307043
  40. Romeo Mestrovic Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2012) and another new proof — http://arxiv.org/abs/1202.3670 — arXiv:1202.3670 math , 2012-02-16
  41. , Section 1.6, Theorem 1.13
  42. Диамонд Г. Элементарные методы в изучении распределения простых чисел — http://www.mathnet.ru/php/archive.phtml?wshow — УМН, 1990
  43. Рекорды простых чисел по годам
  44. The Largest Prime Number to Date Has Been Discovered And It's Hurting Our Brains — Michelle — Starr — ScienceAlert — 2018-01-06 — en-gb
  45. EFF Cooperative Computing Awards
  46. Профессор из США определил самое большое простое число — Юлия Рудый — 2013-02-07 / Вести.Ru — 2018-02-25
  47. . Эффективным тестом простоты является тест Пепина. По состоянию на февраль 2015 года известно только 5 простых чисел Ферма (для n = 0, 1, 2, 3, 4), двадцать восемь следующих чисел Ферма (до `F_{32}` включительно) оказались составными
  48. Виолант-и-Хольц, Альберт. Загадка Ферма. Трёхвековой вызов математике — М. : Де Агостини, 2014 — 151 — ISBN 978-5-9774-0625-3 — (Мир математики: в 45 томах, том 9) — 78
  49. . Эффективным тестом простоты является тест Люка — Лемера — Ризеля
  50. . Эффективным тестом простоты для чисел Прота является тест Бриллхарта — Лемера — Селфриджа (англ. Brillhart–Lehmer–Selfridge test)
  51. А. И. Кострикин. Введение в алгебру, III часть. М.: Физматлит, 2001.
  52. Chris Caldwell, Bertrand’s postulate at Prime Pages glossary.
  53. Доказательство. Нечётное число p, не кратное 3, равно 1 или 2 по модулю 3 и равно 1, 3, 5 или 7 по модулю 8. При возведении в квадрат это даёт 1 по модулю 3 и 1 по модулю 8. Вычитая 1, получаем 0 по модулю 3 и 0 по модулю 8. Следовательно, `p^2-1` кратно 3 и кратно 8; следовательно, оно кратно 24
  54. Эти 2 свойства непосредственно следуют из формул разложения суммы и разности степеней
  55. Sandifer, Charles Edward, 1951- The early mathematics of Leonhard Euler — https://www.worldcat.org/oclc/82370957 — Washington, D.C. : Mathematical Association of America, 2007 — xix, 391 pages — ISBN 0883855593
  56. Bach, Eric. Algorithmic number theory — https://www.worldcat.org/oclc/33164327 — Cambridge, Mass. : MIT Press, ©1996- — volumes <1> — ISBN 0262024055
  57. W. R. Alford, Andrew Granville, Carl Pomerance There are Infinitely Many Carmichael Numbers — http://www.jstor.org/stable/2118576 — Annals of Mathematics, 1994 — 139 — 3 — 703–722 — 10.2307/2118576
  58. Charles C. Sims Enumerating p-Groups — http://onlinelibrary.wiley.com/doi/10.1112/plms/s3-15.1.151/abstract — en — Proceedings of the London Mathematical Society, 1965-01-01 — s3-15 — 1 — 151–166 — 1460-244X — 10.1112/plms/s3-15.1.151
  59. Jacobson, Nathan, 1910-1999. Basic algebra — https://www.worldcat.org/oclc/294885194 — 2nd ed., Dover ed — Mineola, N.Y. : Dover Publications, 2009 — 2 volumes — ISBN 9780486471877
  60. Сагалович Ю.Л. Введение в алгебраические коды — http://iitp.ru/upload/content/790/algebcodes.pdf, 2011 — 302
  61. Ferguson, Niels. Practical cryptography — https://www.worldcat.org/oclc/51568066 — New York : Wiley, 2003 — xx, 410 pages — ISBN 0471223573
  62. W. Diffie, M. Hellman New directions in cryptography — http://ieeexplore.ieee.org/document/1055638/ — IEEE Transactions on Information Theory, November 1976 — 22 — 6 — 644–654 — 0018-9448 — 10.1109/tit.1976.1055638
  63. Yuri Matiyasevich, Diophantine Equations in the XX Century
  64. Matijasevic’s polynomial . The Prime Glossary.
  65. Неизвестный математик совершил прорыв в теории простых чисел-близнецов
  66. Bounded Gaps Between Primes

Литература

  • Гальперин Г. «Просто о простых числах» — Квант — 4 — 1987 — 9—14,38 — http://kvant.mccme.ru/1987/04/prosto_o_prostyh_chislah.htm
  • Нестеренко Ю. В. — [http://nature.web.ru/db/msg.html?mid Введение в криптографию / Под редакцией В. В. Ященко, 2001 : Питер — ISBN 5-318-00443-1 — 288 — http://nature.web.ru/db/msg.html?mid
  • Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М. : МЦНМО, 2003 — 328 — ISBN 5-94057-103-4 — http://www.ict.edu.ru/ft/002416/book.pdf
  • Черёмушкин А. В. Лекции по арифметическим алгоритмам в криптографии — М. : МЦНМО, 2002 — 104 — ISBN 5-94057-060-7 — http://www.ict.edu.ru/ft/002419/cherem.pdf — 2000 — https://web.archive.org/web/20130531134702/http://www.ict.edu.ru/ft/002419/cherem.pdf — 2013-05-31 — http://www.ict.edu.ru/ft/002419/cherem.pdf.
  • Кормен Т., Лейзер Ч. — Глава 33.8. Проверка чисел на простоту Алгоритмы. Построение и анализ — http://www.proklondike.com/books/thalg/kormen_leiser_algorith.html — М. : МЦНМО, 2002 — 765—772 — ISBN 5-900916-37-5
  • Crandall R., Pomerance C. — Глава 3. «Recognizing Primes and Composites». Глава 4. «Primality Proving» — 117—224 Prime Numbers: A Computational Perspective — http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf : Springer, 2005 — ISBN 0-387-25282-7
  • / Сост. А. П. Савин Энциклопедический словарь юного математика — М. : Педагогика, 1985 — 352 — Простое число — 262—263 — Энциклопедический словарь юного математика
  • Кноп К. «В погоне за простотой»
  • Кордемский Б. А. Математическая смекалка — М. : ГИФМЛ, 1958 — 576 — http://ilib.mccme.ru/djvu/klassik/smekalka.htm
  • Генри С. Уоррен, мл. Алгоритмические трюки для программистов — Глава 16. Формулы для простых чисел — Hacker's Delight — ISBN 0-201-91465-4 — 288, 2007 — М. : «Вильямс»
  • Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты — Prime Numbers: A Computational Perspective — М. : УРСС, Либроком, 2011 — 664 — ISBN 978-5-397-02060-2
  • Ю. Матиясевич. Формулы для простых чисел — Квант, 1975 — 5 — 5—13 — http://kvant.mccme.ru/1975/05/formuly_dlya_prostyh_chisel.htm
  • — http://www.nkj.ru/archive/articles/17984/Н. Карпушина. Палиндромы и «перевёртыши» среди простых чисел — Наука и жизнь — 5, 2010
  • Д. Цагер. Первые 50 миллионов простых чисел — Успехи математических наук — 39 — 6(240), 1984 — 175–190 — http://mi.mathnet.ru/umn2506
  • Энрике Грасиан  Простые числа. Долгая дорога к бесконечности — (Мир математики) — 3 : Де Агостини — 148, 2014 — ISBN 978-5-9774-0682-6 — 978-5-9774-0637-6

Ссылки

Числовые системы
Счётные
множества
Натуральные числа ( `\scriptstyle\mathbb{N}` ) • Целые ( `\scriptstyle\mathbb{Z}` ) • Рациональные ( `\scriptstyle\mathbb{Q}` ) • Алгебраические ( `\scriptstyle\overline{\mathbb{Q}}` ) • ПериодыВычислимыеАрифметические
Вещественные числа
и их расширения
Вещественные ( `\scriptstyle\mathbb{R}` ) • Комплексные ( `\scriptstyle\mathbb{C}` ) • Кватернионы ( `\scriptstyle\mathbb{H}` ) • Числа Кэли (октавы, октонионы) ( `\scriptstyle\mathbb{O}` ) • Седенионы ( `\scriptstyle\mathbb{S}` ) • Альтернионы • ДуальныеГиперкомплексныеСупердействительныеГипервещественныеСюрреальные
Инструменты расширения
числовых систем
Процедура Кэли — ДиксонаТеорема ФробениусаТеорема Гурвица
Иерархия чисел
Другие
числовые системы
Кардинальные числаПорядковые числа (трансфинитные, ординал)p-адическиеСупернатуральные числа
См. также
Двойные числаИррациональные числаТрансцендентные числаЧисловой лучБикватернион
Производные латинской буквы P, p
Буквы
Символы
I am not robot