Wikia

Математика

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

Обсуждение1
1408статей на этой вики

Просто́е число́ — это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 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), представимо в виде произведения простых чисел, причём единственным способом (с точностью до порядка следования сомножителей). Таким образом, простые числа — «элементарные строительные блоки» натуральных чисел.

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

Тесты простоты Править

Файл:Eratosthenes.jpg

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

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

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

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

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

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

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

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

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

Наибольшим известным простым числом по состоянию на сентябрь 2006 года является 2^{32582657} - 1. Оно содержит 9 808 358 десятичных цифр и является 44-м известным простым числом Мерсенна (M32582657). Его нашли 4 сентября 2006 года Кертис Купер и Стивен Бун из Университета штата Миссури (Шаблон:Lang-en2), участники проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Предыдущее наибольшее известное простое число 2^{30402457}-1 содержит 9 152 052 десятичных цифры и является 43-м известным простым числом Мерсенна (M30402457). Его нашли 15 декабря 2005 года также Кертис Купер и Стивен Бун в рамках проекта GIMPS.

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

Некоторые свойства Править

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

Открытые вопросы Править

До сих пор существует много открытых вопросов относительно простых чисел. Например:

  • Проблема Гольдбаха: верно ли, что каждое чётное число больше двух может быть представлено в виде суммы двух простых чисел? Верно ли, что каждое нечётное число больше 5 может быть представлено в виде суммы трёх простых чисел?
  • Простые близнецы — это простые числа, разность между которыми равна 2. Верно ли, что существует бесконечно много простых близнецов?
  • Содержит ли последовательность чисел Фибоначчи бесконечное количество простых?
  • Конечно ли количество простых чисел Ферма (то есть чисел вида 2^{2^n}+1)?
  • Всегда ли найдется простое число между n^2 и (n + 1)^2?
  • Бесконечно ли количество простых вида n^2 + 1?
  • Гипотеза Буняковского: верно ли, что любой неприводимый целозначный многочлен, НОД всех значений которого равен 1, принимает простые значения сколь угодно много раз?

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

Большие простые числа (порядка 10^{300}) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел.

См. также Править

Литература Править

Списки Править

Шаблон:Хорошая статьяaf:Priemgetal ang:Frumtæl ar:عدد أولي be-x-old:Просты лік bg:Просто число bn:মৌলিক সংখ্যা br:Niveroù kentael ca:Nombre primer cs:Prvočíslo cy:Rhif cysefin da:Primtalel:Πρώτος αριθμόςeo:Primoet:Algarv eu:Zenbaki lehen fa:اعداد اولgl:Número primo he:מספר ראשוני hr:Prost broj ht:Nonm premyé hu:Prímszámok id:Bilangan prima is:Frumtalaka:მარტივი რიცხვიla:Numerus primus lb:Primzuel lmo:Nümar primm lt:Pirminis skaičius lv:Pirmskaitlis nds:Primtall nl:Priemgetal nn:Primtal no:Primtall pl:Liczby pierwszero:Număr prim scn:Nùmmuru primu simple:Prime number sk:Prvočíslo sl:Praštevilo sr:Прост број sv:Primtal ta:பகா எண் th:จำนวนเฉพาะuk:Просте число ur:مفرد عدد vi:Số nguyên tố vls:Priemgetal yi:פרימצאל yo:Nọ́mbà àkọ́kọ́ zh:素数 zh-min-nan:Sò͘-sò͘

Викия-сеть

Случайная вики