Введение

Число, делящееся только на 1 или на себя.

Простое число (или простое) — это натуральное число, большее 1, которое не является произведением двух меньших натуральных чисел. Натуральное число, большее 1, которое не является простым, называется составным числом. Например, 5 является простым, потому что единственные способы представить его в виде произведения — 1 × 5 или 5 × 1 — включают само число 5. Однако 4 является составным, поскольку оно является произведением (2 × 2), в котором оба числа меньше 4. Простые числа играют центральную роль в теории чисел благодаря основной теореме арифметики: каждое натуральное число, большее 1, является либо само простым числом, либо может быть разложено на множители как произведение простых чисел, которое однозначно с точностью до порядка следования этих множителей. Свойство быть простым называется простотой. Простой, но медленный метод проверки простоты данного числа, называемый пробным делением, проверяет, является ли число кратным какому-либо целому числу между 2 и . Более быстрые алгоритмы включают тест простоты Миллера — Рабина, который быстр, но имеет небольшую вероятность ошибки, и тест простоты AKS, который всегда дает правильный ответ за полиномиальное время, но слишком медленный для практического применения. Особенно быстрые методы доступны для чисел специальной формы, таких как числа Мерсенна. По состоянию на 2018 год наибольшее известное простое число — это простое число Мерсенна с 24 862 048 десятичными цифрами. Другими словами, число является простым, если его нельзя разделить на меньшие группы равного размера, состоящие более чем из одного элемента, или если нельзя расположить точек в прямоугольную сетку, ширина и высота которой больше одной точки. Например, среди чисел от 1 до 6 простыми числами являются 2, 3 и 5, поскольку нет других чисел, которые делят их без остатка. Число 1 не является простым, поскольку оно явно исключено из определения. 1=4 = 2 × 2 и 1=6 = 2 × 3 являются составными числами. Делителями натурального числа являются натуральные числа, которые делят нацело. Каждое натуральное число имеет делители 1 и само себя. Если у него есть другие делители, оно не может быть простым. Это приводит к эквивалентному определению простых чисел: это числа, имеющие ровно два положительных делителя. Эти два делителя — 1 и само число. Поскольку 1 имеет только один делитель — само себя, оно не является простым по этому определению. Другой способ выразить то же самое: число является простым, если оно больше единицы и ни одно из чисел от 2 до не делит нацело. Первые 25 простых чисел (все простые числа меньше 100) — 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.

Любое четное число больше 2 не является простым, поскольку любое такое число можно представить в виде произведения . Следовательно, каждое простое число, кроме 2, является нечетным числом и называется нечетным простым числом. Аналогично, если простые числа больше 5 записаны в обычной десятичной системе, они заканчиваются на 1, 3, 7 или 9. Числа, заканчивающиеся другими цифрами, все составные: десятичные числа, заканчивающиеся на 0, 2, 4, 6 или 8, являются четными, а десятичные числа, заканчивающиеся на 0 или 5, делятся на 5. Множество всех простых чисел иногда обозначается (полужирным заглавным P) или (доской заглавным P).

История

В Риндском математическом папирусе, датированном примерно 1550 годом до н.э., содержатся египетские разложения дробей различных видов для простых и составных чисел. Однако самые ранние сохранившиеся записи об изучении простых чисел принадлежат древнегреческим математикам, которые называли их (πρῶτος ἀριθμὸς). В «Началах» Евклида (ок. 300 г. до н.э.) доказана бесконечность множества простых чисел и основная теорема арифметики, а также показано, как построить совершенное число из простого числа Мерсена. Еще одно греческое изобретение, решето Эратосфена, до сих пор используется для составления списков простых чисел. Около 1000 года н.э. исламский математик Ибн аль-Хайсам (Альхазен) открыл теорему Уилсона, характеризующую простые числа как числа, которые без остатка делят. Он также предположил, что все четные совершенные числа происходят из конструкции Евклида с использованием простых чисел Мерсена, но не смог это доказать. Другой исламский математик, Ибн аль-Банна аль-Марракуши, заметил, что решето Эратосфена можно ускорить, рассматривая только простые делители, не превышающие квадратный корень из верхнего предела. Ферма также исследовал простоту чисел Ферма, а Марен Мерсенн изучал простые числа Мерсена – простые числа вида , где само по себе является простым числом. Кристиан Гольдбах сформулировал гипотезу Гольдбаха, утверждающую, что каждое четное число является суммой двух простых чисел, в письме к Эйлеру в 1742 году. Эйлер доказал гипотезу Альхазена (ныне теорему Евклида — Эйлера), что все четные совершенные числа могут быть построены из простых чисел Мерсена. В начале XIX века Лежандр и Гаусс предположили, что при стремлении к бесконечности число простых чисел, не превышающих , асимптотически равно , где – натуральный логарифм. Более слабым следствием этой высокой плотности простых чисел был постулат Бертрана, утверждающий, что для каждого существует простое число между и , доказанный в 1852 году Пафнутием Чебышевым. Идеи Бернарда Римана, изложенные в его статье 1859 года о дзета-функции, наметили план доказательства гипотезы Лежандра и Гаусса. Хотя тесно связанная с ней гипотеза Римана остается недоказанной, план Римана был завершен в 1896 году Адамаром и де ла Валле-Пуссеном, и результат теперь известен как теорема о простых числах. Другим важным результатом XIX века была теорема Дирихле об арифметических прогрессиях, утверждающая, что некоторые арифметические прогрессии содержат бесконечно много простых чисел. Многие математики работали над тестами на простоту для чисел, слишком больших для проверки делением. Методы, ограниченные конкретными формами чисел, включают тест Пепина для чисел Ферма (1877), теорему Прота (ок. 1878), тест простоты Лукаса — Лемера (разработан в 1856 году) и обобщенный тест простоты Лукаса. Поиск все более и более крупных простых чисел вызвал интерес за пределами математических кругов благодаря Great Internet Mersenne Prime Search и другим проектам распределенных вычислений. Представление о том, что простые числа имеют мало применений за пределами чистой математики, было опровергнуто в 1970-х годах, когда были изобретены криптография с открытым ключом и криптосистема RSA, в основе которых лежат простые числа. Возросшая практическая значимость компьютерного тестирования на простоту и факторизации привела к разработке усовершенствованных методов, способных обрабатывать большие числа произвольной формы. Математическая теория простых чисел также продвинулась вперед благодаря теореме Грина — Тао (2004), утверждающей, что существуют арифметические прогрессии простых чисел произвольной длины, и доказательству Итан Чжана 2013 года о том, что существует бесконечно много простых промежутков ограниченного размера.

Первостепенность одного

Большинство древних греков даже не считали 1 числом, поэтому не могли рассматривать вопрос о его простоте. Некоторые ученые греческой и последующей римской традиции, включая Никомаха, Ямблиха, Боэция и Кассиодора, также рассматривали простые числа как подраздел нечетных чисел и поэтому не считали 2 простым числом. Однако Евклид и большинство других греческих математиков считали 2 простым числом. Средневековые исламские математики в основном придерживались греческого взгляда на 1 как на не-число. В середине XVIII века Кристиан Гольдбах указал 1 как простое число в своей переписке с Леонардом Эйлером, однако сам Эйлер не считал 1 простым. В XIX веке многие математики по-прежнему считали 1 простым числом.

Если бы определение простого числа было изменено, чтобы считать 1 простым, многие утверждения, связанные с простыми числами, пришлось бы переформулировать более неуклюжим образом. Например, фундаментальную теорему арифметики пришлось бы перефразировать с точки зрения разложения на простые множители, большие 1, поскольку каждое число имело бы множественные разложения с любым количеством единиц. Аналогично, решето Эратосфена не работало бы правильно, если бы оно обрабатывало 1 как простое число, поскольку оно исключило бы все кратные 1 (то есть все остальные числа) и выдало бы только число 1. К началу XX века математики начали соглашаться с тем, что 1 не следует включать в список простых чисел, а выделять в отдельную категорию как "единицу". Эта теорема утверждает, что любое целое число, большее 1, можно представить в виде произведения одного или нескольких простых чисел. Более того, это произведение уникально в том смысле, что любые два разложения на простые множители одного и того же числа будут содержать одинаковое количество копий одних и тех же простых чисел, хотя порядок их может отличаться. Таким образом, хотя существует множество различных способов найти разложение, используя алгоритм факторизации целых чисел, все они должны давать один и тот же результат. Следовательно, простые числа можно рассматривать как "основные строительные блоки" натуральных чисел. Некоторые доказательства уникальности разложения на простые множители основаны на лемме Евклида: если *p* – простое число и *p* делит произведение *ab* целых чисел *a* и *b*, то *p* делит *a* или *p* делит *b* (или оба). И наоборот, если число *n* обладает свойством, что когда оно делит произведение, оно всегда делит хотя бы один из множителей произведения, то *n* должно быть простым.

p-адические числа

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

Первичные элементы в кольцах

Коммутативное кольцо — это алгебраическая структура, в которой определены сложение, вычитание и умножение. Целые числа являются кольцом, а простые числа в целых числах обобщаются на кольца двумя различными способами: простыми элементами и неразложимыми элементами. Элемент кольца называется простым, если он отличен от нуля, не имеет мультипликативной обратной (то есть не является единицей) и удовлетворяет следующему условию: если делит произведение двух элементов , то он также делит хотя бы один из или . Элемент называется неразложимым, если он не является ни единицей, ни произведением двух других элементов, отличных от единицы. В кольце целых чисел простые и неразложимые элементы образуют одно и то же множество.

В произвольном кольце все простые элементы являются неразложимыми. Обратное утверждение неверно в общем случае, но верно для областей однозначной факторизации. Основная теорема арифметики продолжает выполняться (по определению) в областях однозначной факторизации. Примером такой области являются гауссовы целые числа , кольцо комплексных чисел вида , где — мнимая единица, а и — произвольные целые числа. Его простые элементы известны как гауссовы простые числа. Не каждое число, которое является простым среди целых чисел, остаётся простым в гауссовых целых числах; например, число 2 можно представить как произведение двух гауссовых простых чисел и . Рациональные простые числа (простые элементы в целых числах), сравнимые с 3 по модулю 4, являются гауссовыми простыми числами, но рациональные простые числа, сравнимые с 1 по модулю 4, не являются. Это следствие теоремы Ферма о суммах двух квадратов, которая утверждает, что нечётное простое число можно представить в виде суммы двух квадратов, , и, следовательно, разложить на множители как , ровно когда сравнимо с 1 по модулю 4.

Первоочередные идеалы

Не каждое кольцо является областью однозначной факторизации. Например, в кольце чисел (для целых чисел и ) число имеет две разложения на множители , где ни один из четырех множителей нельзя далее разложить, поэтому оно не имеет однозначной факторизации. Чтобы расширить однозначную факторизацию на более широкий класс колец, понятие числа можно заменить понятием идеала — подмножества элементов кольца, содержащего все суммы пар своих элементов и все произведения своих элементов с элементами кольца. Первичные идеалы, которые обобщают простые элементы в том смысле, что главный идеал, порожденный простым элементом, является первичным идеалом, являются важным инструментом и объектом изучения в коммутативной алгебре, алгебраической теории чисел и алгебраической геометрии. Первичные идеалы кольца целых чисел — это идеалы (0), (2), (3), (5), (7), (11), … Основная теорема арифметики обобщается теоремой Ласкера — Нётера, которая выражает каждый идеал в нётеровском коммутативном кольце как пересечение первичных идеалов, являющихся соответствующим обобщением простых степеней. Спектр кольца — это геометрическое пространство, точками которого являются первичные идеалы кольца. Арифметическая геометрия также выигрывает от этого понятия, и многие концепции существуют как в геометрии, так и в теории чисел. Например, разложение или ветвление простых идеалов при переходе к расширению поля, основная задача алгебраической теории чисел, имеет некоторое сходство с ветвлением в геометрии. Эти концепции могут даже помочь в вопросах теории чисел, касающихся исключительно целых чисел. Например, первичные идеалы в кольце целых чисел квадратичного поля могут быть использованы для доказательства закона квадратичной взаимности — утверждения об существовании квадратных корней по модулю простых чисел. Ранние попытки доказать последнюю теорему Ферма привели Куммера к введению регулярных простых чисел, простых чисел, связанных с невозможностью однозначной факторизации в циклотомических целых числах. Вопрос о том, сколько простых чисел раскладываются в произведение нескольких простых идеалов в алгебраическом числе, решается теоремой о плотности Чеботарева, которая (при применении к циклотомическим целым числам) имеет теорему Дирихле о простых числах в арифметической прогрессии в качестве частного случая.

Теория групп

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

Вычислительные методы

Долгое время теория чисел в целом и изучение простых чисел в частности считались каноническим примером чистой математики, не имеющей практического применения за пределами самой математики, за исключением использования зубчатых колес с простым числом зубьев для равномерного распределения нагрузки. В частности, теоретики чисел, такие как британский математик Г. Х. Харди, гордились тем, что их работа не имеет никакого военного значения. Это представление о чистоте теории чисел было разрушено в 1970-х годах, когда стало известно, что простые числа могут быть использованы в качестве основы для создания алгоритмов криптографии с открытым ключом. Например, чтобы проверить, является ли число 37 простым, этот метод делит его на простые числа в диапазоне от 2 до √37, то есть на 2, 3 и 5. Каждое деление дает ненулевой остаток, следовательно, 37 действительно является простым числом. Хотя этот метод прост в описании, он непрактичен для проверки простоты больших целых чисел, поскольку количество операций, которое он требует, растет экспоненциально с увеличением числа цифр в этих числах. Тем не менее, метод пробного деления все еще используется, с ограничением размера делителя, меньшим, чем квадратный корень, для быстрого выявления составных чисел с небольшими делителями, прежде чем применять более сложные методы к числам, прошедшим эту проверку.

Сита

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

Факторизация целых чисел

Задача получения одного (или всех) простых множителей для составного целого числа называется факторизацией этого числа. Она значительно сложнее, чем проверка на простоту, и хотя существует множество алгоритмов факторизации, они работают медленнее, чем самые быстрые методы проверки на простоту. Метод пробного деления и алгоритм Польарда ρ могут использоваться для нахождения очень маленьких множителей числа. Методы, подходящие для произвольно больших чисел и не зависящие от размера его множителей, включают в себя квадратичное решето и общее решето числового поля. Как и в случае проверки на простоту, существуют также алгоритмы факторизации, требующие, чтобы входные данные имели специальную форму, включая специальное решето числового поля. По состоянию на 2019 год наибольшим числом, которое было успешно разложено на множители с помощью алгоритма общего назначения, является RSA-240, состоящее из 240 десятичных цифр (795 бит) и являющееся произведением двух больших простых чисел. Алгоритм Шора способен разложить на множители любое целое число за полиномиальное количество шагов на квантовом компьютере. Однако текущие технологии позволяют запускать этот алгоритм только для очень небольших чисел. По состоянию на 2012 год наибольшим числом, разложенным на множители квантовым компьютером с использованием алгоритма Шора, является 21.

Другие вычислительные приложения

Несколько алгоритмов криптографии с открытым ключом, таких как RSA и обмен ключами Диффи — Хеллмана, основаны на больших простых числах (обычно используются простые числа длиной 2048 бит). RSA опирается на предположение, что умножение двух (больших) чисел *a* и *b* гораздо проще (то есть эффективнее), чем вычисление *a* и *b* (предполагается, что они взаимно простые), если известно только их произведение *n*. Простые числа часто используются для хэш-таблиц. Например, оригинальный метод Картера и Вегмана для универсального хеширования основывался на вычислении хеш-функций путем выбора случайных линейных функций по модулю больших простых чисел. Картер и Вегман обобщили этот метод для независимого хеширования, используя полиномы более высокой степени, также по модулю больших простых чисел. Помимо хеш-функций, простые числа используются для определения размера хэш-таблицы в хэш-таблицах с квадратичным зондированием, чтобы обеспечить охват всей таблицы последовательностью зондирования. Некоторые методы контрольных сумм основаны на математике простых чисел. Например, контрольные суммы, используемые в Международном стандартном номере книги (ISBN), определяются как остаток от деления числа на 11, являющееся простым числом. Благодаря тому, что 11 — простое число, этот метод способен обнаруживать как одиночные ошибки в цифрах, так и перестановки соседних цифр. Другой метод контрольных сумм, Adler-32, использует арифметику по модулю 65521, наибольшего простого числа, меньшего чем 2<sup>16</sup>. Простые числа также используются в генераторах псевдослучайных чисел, включая линейные конгруэнтные генераторы и Mersenne Twister.

Другие применения

Простые числа имеют центральное значение в теории чисел, но также находят множество применений в других областях математики, включая абстрактную алгебру и элементарную геометрию. Например, можно расположить столько точек в двумерной сетке, сколько простых чисел, чтобы никакие три из них не лежали на одной прямой, или чтобы каждый треугольник, образованный тремя из этих точек, имел большую площадь. Другой пример – критерий Эйзенштейна, проверка на неприводимость полинома, основанная на делимости его коэффициентов на простое число и его квадрат. Понятие простого числа настолько важно, что оно было обобщено различными способами в разных областях математики. В общем случае, термин "простое" указывает на минимальность или неделимость в соответствующем смысле. Например, простое поле данного поля – это его наименьшее подполе, содержащее как 0, так и 1. Это либо поле рациональных чисел, либо конечное поле с простым числом элементов, откуда и происходит название. Часто, используя слово "простое", подразумевается дополнительное значение, а именно, что любой объект можно, по существу, единственным образом разложить на простые компоненты. Например, в теории узлов простой узел – это узел, который нельзя разложить на сумму двух нетривиальных узлов. Любой узел можно единственным образом представить в виде суммы простых узлов. Разложение трехмерных многообразий на простые компоненты – еще один пример такого рода. Помимо математики и информатики, простые числа могут быть связаны с квантовой механикой и используются метафорически в искусстве и литературе. Они также применялись в эволюционной биологии для объяснения жизненных циклов цикад.

Квантовая механика

Начиная с работ Хью Монтгомери и Фримена Дайсона в 1970-х годах, математики и физики предполагали, что нули дзета-функции Римана связаны с энергетическими уровнями квантовых систем. Простые числа также играют важную роль в квантовой информатике благодаря математическим структурам, таким как взаимно непредвзятые базисы и симметричные информационно полные положительнозначные меры операторов.

Биология

Эволюционная стратегия, используемая цикадами рода Magicicada, основана на использовании простых чисел. Эти насекомые проводят большую часть своей жизни под землей в виде личинок. Они окукливаются и выходят из своих нор только через 7, 13 или 17 лет, после чего летают, размножаются и умирают максимум через несколько недель. Биологи предполагают, что такие циклы размножения, основанные на простых числах, эволюционировали для того, чтобы предотвратить синхронизацию с ними хищников. В отличие от этого, многолетние периоды между цветением бамбука, как предполагается, являются гладкими числами, в разложении на множители которых содержатся только малые простые числа.

Искусство и литература

Простые числа оказали влияние на многих художников и писателей. Французский композитор Оливье Мессиан использовал простые числа для создания аметрической музыки, вдохновляясь "естественными явлениями". В таких произведениях, как La Nativité du Seigneur (1935) и Quatre études de rythme (1949–50), он одновременно применяет мотивы с длительностью, определяемой различными простыми числами, для создания непредсказуемых ритмов: в третьем этюде "Neumes rythmiques" встречаются простые числа 41, 43, 47 и 53. По словам Мессиана, этот метод сочинения был "вдохновлен движениями природы, движениями свободной и неравномерной продолжительности". В своем научно-фантастическом романе "Контакт" ученый Карл Саган предположил, что разложение на простые множители можно использовать для установления двухмерных плоскостей изображения при общении с инопланетянами, идею, которую он впервые неофициально обсудил с американским астрономом Фрэнком Дрейком в 1975 году. В романе Марка Хэддона "Загадочное ночное убийство собаки" рассказчик располагает части истории в соответствии с последовательными простыми числами, чтобы передать психическое состояние главного героя – математически одаренного подростка с синдромом Аспергера. В романе Паоло Джордано "Одиночество простых чисел" простые числа используются как метафора одиночества и изоляции, представляя собой "изгоев" среди целых чисел.