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

Простое число (или простое число ) — это натуральное число больше 1, которое не является произведением двух меньших натуральных чисел. Натуральное число больше 1, не являющееся простым, называется составным числом . Например, число 5 простое, потому что единственные способы записать его как произведение 1 × 5 или 5 × 1 включают само число 5. Однако число 4 является составным, потому что оно представляет собой произведение ( 2 × 2 ), в котором оба числа меньше 4. Простые числа занимают центральное место в теории чисел из-за основной теоремы арифметики : каждое натуральное число больше 1 либо само по себе простое, либо может быть факторизованкак произведение простых чисел, уникальное с точностью до их порядка.

Свойство быть простым называется простотой . Простой, но медленный метод проверки простоты заданного числа , называемый пробным делением , проверяет, является ли число кратным любому целому числу от 2 до . Более быстрые алгоритмы включают тест на простоту Миллера-Рабина , который работает быстро, но имеет небольшую вероятность ошибки, и тест на простоту AKS , который всегда дает правильный ответ за полиномиальное время , но слишком медленный для практического применения. Особенно быстрые методы доступны для чисел специальных форм, таких как числа Мерсенна . По состоянию на декабрь 2018 года самым большим известным простым числом является простое число Мерсенна с 24 862 048.${\ Displaystyle п}$${\ Displaystyle п}$${\ displaystyle {\ sqrt {п}}}$^{[Обновить]}десятичные цифры . ^[1]

Существует бесконечно много простых чисел, как показал Евклид около 300 г. до н.э. Ни одна известная простая формула не отделяет простые числа от составных. Однако распределение простых чисел в натуральных числах в целом можно смоделировать статистически. Первым результатом в этом направлении является доказанная в конце XIX века теорема о простых числах , которая гласит, что вероятность того, что случайно выбранное большое число окажется простым, обратно пропорциональна количеству его цифр, то есть его логарифму .

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

Натуральное число (1, 2, 3, 4, 5, 6 и т. д.) называется простым числом (или простым числом ), если оно больше 1 и не может быть записано в виде произведения двух меньших натуральных чисел. Числа больше 1, которые не являются простыми, называются составными числами . ^[2] Другими словами, является простым, если элементы нельзя разделить на более мелкие группы одинакового размера из более чем одного элемента, ^[3] или если невозможно разместить точки в прямоугольной сетке шириной более одной точки. и высотой более одной точки. ^[4] Например, среди чисел от 1 до 6 числа 2, 3 и 5 являются простыми числами, ^[5]${\ Displaystyle п}$${\ Displaystyle п}$${\ Displaystyle п}$так как нет других чисел, которые делят их нацело (без остатка). 1 не является простым числом, поскольку оно специально исключено из определения. 4 = 2 × 2 и 6 = 2 × 3 составные.

Составные числа можно расположить в прямоугольники , а простые числа — нет.

Демонстрация с помощью стержней Кюизенера того, что 7 является простым числом, потому что ни одно из чисел 2, 3, 4, 5 или 6 не делится нацело .

Математический папирус Райнда

Относительная ошибка и логарифмический интеграл как аппроксимация функции подсчета простых чисел . Обе относительные ошибки уменьшаются до нуля по мере роста, но сходимость к нулю для логарифмического интеграла происходит гораздо быстрее.${\ Displaystyle {\ tfrac {п} {\ журнал п}}}$${\ Displaystyle \ OperatorName {Ли} (п)}$${\ Displaystyle п}$

Штрихи в арифметических прогрессиях по модулю 9. Каждая строка тонкой горизонтальной полосы показывает одну из девяти возможных прогрессий по модулю 9 с простыми числами, отмеченными красным. Последовательности чисел, равные 0, 3 или 6 по модулю 9, содержат не более одного простого числа (число 3); остальные последовательности чисел, равные 2, 4, 5, 7 и 8 по модулю 9, имеют бесконечно много простых чисел с одинаковым количеством простых чисел в каждой последовательности.

Спираль Улама . Простые числа (красные) группируются на одних диагоналях, а не на других. Простые значения показаны синим цветом.${\ Displaystyle 4n ^ {2} -2n + 41}$

График абсолютных значений дзета-функции, показывающий некоторые ее особенности

Простые числа Гаусса с нормой меньше 500

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

Решето Эратосфена начинается с того, что все числа не отмечены (серые). Он неоднократно находит первое неотмеченное число, помечает его как простое (темные цвета) и помечает его квадрат и все последующие кратные как составные (более светлые цвета). После пометки чисел, кратных 2 (красный), 3 (зеленый), 5 (синий) и 7 (желтый), все простые числа до квадратного корня из размера таблицы обработаны, а все оставшиеся неотмеченные числа (11, 13 и т. д.) отмечены как простые (пурпурные).

Связная сумма двух простых узлов

Построение правильного пятиугольника с помощью линейки и циркуля. Это возможно только потому, что 5 — простое число Ферма .