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

Простое число  — натуральное (целое положительное) число,имеющее ровно два различных натуральных делителя — и самого себя.Другими словами, число x является простым, если оно больше 1 и приэтом делится без остатка только на 1 и на x. К примеру, 5 —простое число, а 6 является составным числом, так как, помимо 1 и6, также делится на 2 и на 3.
 Натуральные числа, которые больше единицы и не являются простыми,называются составными. Таким образом, все натуральные числа разбиваютсяна три класса: единицу (имеющую один натуральный делитель), простыечисла (имеющие два натуральных делителя) и составные числа (имеющиебольше двух натуральных делителей). Изучением свойств простых чиселзанимается теория чисел. В теории колец простым числам соответствуютнеприводимые элементы.
 Последовательность простых чисел начинается так:

 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 \ldots

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


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

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


 Файл:Eratosthenes.jpg\textbarthumb\textbar150px\textbarЭратосфенКиренскийрешето Эратосфена, решето Сундарама и решето Аткина.
 Однако, на практике вместо получения списка простых чисел зачастуютребуется проверить, является ли данное число простым. Алгоритмы,решающие эту задачу, называются тестами простоты. Существует множествополиномиальных тестов простоты, но большинство их являютсявероятностными (например, тест Миллера — Рабина) и используются длянужд криптографии. В 2002 году было доказано, что задача проверки напростоту в общем виде полиномиально разрешима, но предложенныйдетерминированный тест Агравала — Каяла — Саксены имеет довольнобольшую вычислительную сложность, что затрудняет его практическоеприменение.
 Для некоторых классов чисел существуют специализированные эффективныетесты простоты (см. ниже).

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


 Простых чисел бесконечно много. Самое старое известное доказательствоэтого факта было дано Евклидом в «Началах» (книга IX, утверждение 20).Его доказательство может быть кратко воспроизведено так:
 Математики предлагали другие доказательства. Одно из них (приведённоеЭйлером) показывает, что сумма величин, обратных к первым nпростым числам, неограниченно растёт с ростом n.
 Теорема о распределении простых чисел утверждает, что количество простыхчисел меньших n, обозначаемое π(n), растёт как n/ln(n).

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


 Издавна ведутся записи, отмечающие наибольшие известные на то времяпростые числа. Один из рекордов поставил в своё время Эйлер, найдяпростое число .
 Наибольшим известным простым числом по состоянию является . Оно содержитдесятичных цифр и является простым числом Мерсенна (M\textsubscript).Его нашли 17 сентября 2015 года в рамках проекта по распределённомупоиску простых чисел Мерсенна GIMPS, однако все проверки завершилисьлишь 7 января 2016 года.
 Числа Мерсенна выгодно отличаются от остальных наличием эффективноготеста простоты: теста Люка — Лемера. Благодаря ему простые числаМерсенна давно удерживают рекорд как самые большие известные простые.
 За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000десятичных цифр EFF назначила денежные призы соответственно в 150 000 и250 000 долларов США. Ранее EFF уже присуждала призы за нахождениепростых чисел из 1 000 000 и 10 000 000 десятичных цифр.

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


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

  • Числа Мерсенна — числа вида Mn=2n1, где n — натуральное число. При этом число Мерсенна может быть простым, только если n — простое число. Как уже было отмечено выше, эффективным тестом простоты является тест Люка-Лемера.
  • Числа Ферма — числа вида Fn=22n+1, где n — неотрицательное целое число. Эффективным тестом простоты является тест Пепина. По состоянию на февраль 2015 года известно только 5 простых чисел Ферма (для n = 0, 1, 2, 3, 4), двадцать восемь следующих чисел Ферма (до F32 включительно) оказались составными, однако не доказано, что других простых чисел Ферма нет.
  • Числа Вудала — числа вида Wn=n2n1. Эффективным тестом простоты является тест Люка — Лемера — Ризеля.
  • Числа Каллена — числа вида Cn=n2n+1.
  • Числа Прота — числа вида P=k2n+1, причём k нечётно и 2n>k. Эффективным тестом простоты для чисел Прота является тест Бриллхарта — Лемера — Селфриджа . Числа Каллена и числа Ферма являются частным случаем чисел Прота (соответственно при k = n и при k = 1, n=2m).
  • Числа Миллса — числа вида Pn=[A3n], где A — константа Миллса.

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

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



  • Если  — простое, и делит , то делит или . Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.
  • Кольцо вычетов Zn является полем тогда и только тогда, когда n — простое.
  • Характеристика каждого поля — это ноль или простое число.
  • Если p — простое, а a — натуральное, то apa делится на p (малая теорема Ферма).
  • Если G — конечная группа, порядок которой |G| делится на p, то G содержит элемент порядка p (теорема Коши).
  • Если G — конечная группа, и pn — максимальная степень p, которая делит |G|, то G имеет подгруппу порядка pn, называемую силовской подгруппой, более того, количество силовских подгрупп равно pk+1 для некоторого целого k (теоремы Силова).
  • Натуральное p>1 является простым тогда и только тогда, когда (p1)!+1 делится на p (теорема Вильсона).
  • Если n>1 — натуральное, то существует простое p, такое, что n<p<2n (постулат Бертрана).
  • Ряд чисел, обратных к простым, расходится. Более того, при x
      $\sum_{p
  • Любая арифметическая прогрессия вида a,a+q,a+2q,a+3q,..., где a,q>1 — целые взаимно простые числа, содержит бесконечно много простых чисел (теорема Дирихле о простых числах в арифметической прогрессии).
  • Всякое простое число, большее 3, представимо в виде 6k+1 или 6k1, где k — некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k\textgreater1) одинакова, то она обязательно кратна 6 — например: 251-257-263-269; 199-211-223; 20183-20201-20219.
  • Если p>3 — простое, то p21 кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3).
  • Теорема Грина-Тао. Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел.
  • Никакое простое число не может иметь вид nk1, где n\textgreater2, k\textgreater1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, большим 2. Из этого следует также, что если простое число имеет вид 2k1, то k — простое (см. числа Мерсенна).
  • Никакое простое число не может иметь вид n2k+1+1, где n\textgreater1, k\textgreater0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, большим 1.

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


 В разное время предпринимались попытки указать выражение, значениямикоторого при разных значениях входящих в него переменных были бы простыечисла. Л. Эйлер указал многочлен n2n+41, принимающийпростые значения при . Однако при значение многочлена является составнымчислом. Можно доказать, что не существует многочлена от одной переменной, который принимает простые значения при всех целых . П. Фермапредположил, что все простые; однако Эйлер опроверг эту гипотезу,доказав, что число  — составное.
 Тем не менее, существуют многочлены, множество положительных значенийкоторых при неотрицательных значениях переменных совпадает с множествомпростых чисел. Одним из примеров является многочлен
 *: (k+2)(1[wz+h+jq]2[(gk+2g+k+1)(h+j)+hz]2[2n+p+q+ze]2[16(k+1)3(k+2)(n+1)2+1f2]2[e3(e+2)(a+1)2+1o2]2[(a21)y2+1x2]2[16r2y4(a21)+1u2]2[((a+u2(u2a))21)(n+4dy)2+1(x+cu)2]2[n+l+vy]2[(a21)l2+1m2]2[ai+k+1li]2[p+l(an1)+b(2an+2an22n2)m]2[q+y(ap1)+s(2ap+2ap22p2)x]2[z+pl(ap)+t(2app21)pm]2) содержащий 26 переменных и имеющий степень 25. Наименьшаястепень для известных многочленов такого типа — 5 при 42 переменных;наименьшее число переменных — 10 при степени около1,6·10\textsuperscript45. Этот результат является частным случаемдоказанной Юрием Матиясевичем диофантовости любого перечислимогомножества.

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


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

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

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

Приложения


 Большие простые числа (порядка ) используются в криптографии с открытымключом. Простые числа также используются в хеш-таблицах и для генерациипсевдослучайных чисел (в частности, в ГПСЧ «Вихрь Мерсенна»).

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



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