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

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

Просто́е число́ — это натуральное число, которое имеет ровно 2 различных делителя (только 1 и самого себя). Все остальные числа, не равные единице, называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

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

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, … (последовательность A000040 в OEIS, см. также список простых чисел)

Содержание

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

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

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует (здесь и далее речь идёт о полиномиальной зависимости времени работы алгоритма от логарифма проверяемого числа, то есть от количества его цифр). На предполагаемой вычислительной сложности задачи факторизации базируется криптосистема

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

Основная статья: Тест простоты

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

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

Для некоторых классов чисел существуют специализированные эффективные тесты простоты. Например, для проверки на простоту чисел Мерсенна используется тест Люка — Лемера, а для проверки на простоту чисел Ферматест Пепина.

Сколько существует простых чисел?

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

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

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

Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).

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

Наибольшим известным простым числом по состоянию на сентябрь 2008 года является 243112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна 37156667, было найдено 6 сентября 2007 года участником проекта нем. Hans-Michael Elvenich).

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

За нахождение простого числа из более чем 108 десятичных цифр EFF назначила[2] награду в 150000 долларов США.

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

  • Если p — простое, и p делит ab, то p делит a или b. Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.
  • Кольцо вычетов \mathbb{Z}_n является полем тогда и только тогда, когда n — простое.
  • Характеристика каждого поля — это ноль или простое число.
  • Если p — простое, а a — натуральное, то ap - a делится на p (малая теорема Ферма).
  • Если G — конечная группа с pn элементов, то G содержит элемент порядка p.
  • Если G — конечная группа, и pn — максимальная степень p, которая делит | G | , то G имеет подгруппу порядка pn, называемую силовской подгруппой, более того, количество силовских подгрупп равно pk + 1 для некоторого целого k (теоремы Силова).
  • Натуральное p > 1 является простым тогда и только тогда, когда (p - 1)! + 1 делится на p (теорема Вильсона).
  • Если n > 1 — натуральное, то существует простое p, такое, что n < p < 2n (постулат Бертрана).
  • Ряд чисел, обратных к простым, расходится. Более того, при x\to\infty
\sum_{p&amp;amp;lt;x} \frac{1}{p}\ \sim\ \ln \ln x.

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

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

  1. Проблема Гольдбаха (первая проблема Ландау): доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.
  2. Вторая проблема Ландау: бесконечно ли множество «простых близнецов» — простых чисел, разность между которыми равна 2?
  3. Гипотеза Лежандра (третья проблема Ландау) верно ли, что между n2 и (n + 1)2 всегда найдётся простое число?
  4. Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?

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

Приложения

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

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

Литература

См. также

Примечания

  1. Weisstein, Eric W. AKS Primality Test на сайте Wolfram MathWorld.(англ.)
  2. EFF Cooperative Computing Awards(англ.)
  3. Weisstein, Eric W. Landau's Problems на сайте Wolfram MathWorld.(англ.)

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Простые числа" в других словарях:

  • Простые числа-близнецы — Простые числа близнецы, или парные простые числа  пары простых чисел, отличающихся на 2. Содержание 1 Общая информация 2 Теорема Бруна 3 Списки …   Википедия

  • Простые числа, отличающиеся на шесть — Простые числа, отличающиеся на шесть  пара простых чисел вида «p, p + 6»[1]. Например, таковыми являются числа 5 и 11. В английском языке для таких пар чисел применяется термин «sexy primes» (англ. sexy  сексуальный, возбуждающий,… …   Википедия

  • Простые числа (альбом) — Простые числа Обложка альбома «Простые числа» (Несчастного случая, 2006) Студийный альбом Несчастного случая Дата выпуска 2006 Записан 2006 Жанр …   Википедия

  • Простые числа Ферма — Числа Ферма числа вида . Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако, эта гипотеза была опровергнута Эйлером в 1732 году, нашедшим разложение числа F5 на простые делители: Последовательность… …   Википедия

  • Простые числа Софи Жермен — это такие простые p, что 2p + 1 тоже простое: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, ... (последовательность A005384 в OEIS) Софи Жермен доказала Великую теорему Ферма для показателей, являющихся простыми этого вида. Как и… …   Википедия

  • Взаимно простые числа — Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. Примеры: 14 и 25 взаимно просты, а 15 и 25 не взаимно просты (у них имеется общий делитель 5). Наглядное представление: если на плоскости построить… …   Википедия

  • Кубические простые числа — Кубические простые числа  это простые числа, которые являются решением одного из двух кубических уравнений третей степени от переменных x и y. Первое из них: [1] и первые несколько таких кубических простых чисел: 7, 19, 37, 61, 127, 271, 331 …   Википедия

  • Взаимно-простые числа — Два целых числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. Содержание 1 Связанные определения 2 Примеры 3 Свойства 4 См. также …   Википедия

  • взаимно простые числа — натуральные числа, не имеющие общих делителей, отличных от 1; например, 15 и 16. * * * ВЗАИМНО ПРОСТЫЕ ЧИСЛА ВЗАИМНО ПРОСТЫЕ ЧИСЛА, натуральные числа, не имеющие общих делителей, отличных от 1; напр., 15 и 16 …   Энциклопедический словарь

  • ВЗАИМНО ПРОСТЫЕ ЧИСЛА — натуральные числа, не имеющие общих делителей, отличных от 1; напр., 15 и 16 …   Большой Энциклопедический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»