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

Простое число — это натуральное (целое положительное) число p, которое делится без остатка только на два натуральных числа: на 1 и на само себя. Иными словами, простое число p имеет ровно два натуральных делителя: 1 и само число p.

В силу определения, множество всех делителей простого числа p является двухэлементным, т.е. представляет собой множество \{1; p\}.

Множество всех простых чисел обозначают символом \mathbb{P}. Таким образом, в силу определения множества простых чисел, мы можем записать: \mathbb{P}\subset\mathbb{N}.

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

     \begin{equation*} 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 \ldots \end{equation*}

Основная теорема арифметики

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

Разложение натурального числа n>1 в произведение простых чисел называют каноническим:

     \begin{equation*} n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_2^{\alpha_3}\cdot p_3^{\alpha_3}\cdot\ldots\cdot p_k^{\alpha_k}, \end{equation*}

где p_i — простое число, p_i<p_{i+1} и 0<\alpha_j\in\mathbb{N}. Например, каноническое разложение натурального числа 120 выглядит так: 120=2^3\cdot3^1\cdot 5^1.

Представление натурального числа в виде произведения простых также называют факторизацией числа.

Свойства простых чисел

  • Любое натуральное число a либо делится на простое число p, либо взаимно просто с ним (то есть НОД(a;p)=1).
  • Произведение натуральных чисел делится на простое число тогда и только тогда, когда хотя бы одно из них делится на это простое число.
  • Простых чисел бесконечно много (не существует самого большого простого числа).
  • Если натуральное число не делится ни на одно простое число, квадрат которого не превосходит это натуральное число, то оно само является простым.
  • Если p — простое число, а a — натуральное, то a^p-a делится на p (малая теорема Ферма).
  • Если n>1 — натуральное число, то существует такое простое число p, что n<p<2n (постулат Бертрана).
  • Любое простое число p>3 представимо в виде p=6k\pm 1, k\in\mathbb{N}.
  • Если p>3 — простое число, то p^2-1 кратно 24.

Решето Эратосфена

Эратосфен Киренский

Эратосфен Киренский

Одним из наиболее известных алгоритмов поиска и распознавания простых чисел является решето Эратосфена. Так этот алгоритм был назван в честь греческого математика Эратосфена Киренского, которого считают автором алгоритма.

Для нахождения всех простых чисел, меньших заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Шаг 1. Выписать подряд все натуральные числа от двух до n, т.е. 2, 3, 4, \ldots, n.
Шаг 2. Присвоить переменной p значение 2, то есть значение равное наименьшему простому числу.
Шаг 3. Вычеркнуть в списке все числа от 2p до n кратные p, то есть числа: 2p, 3p, 4p, \ldots.
Шаг 4. Найти первое незачёркнутое число в списке, большее p, и присвоить переменной p значение этого числа.
Шаг 5. Повторить шаги 3 и 4 до достижения числа n.

Процесс применения алгоритма будет выглядеть следующим образом:

Sieve_of_Eratosthenes

Все оставшиеся незачёркнутые числа в списке по завершении процесса применения алгоритма будут представлять собой множество простых чисел от 2 до n.

Гипотеза Гольдбаха

petros

Обложка книги «Дядюшка Петрос и гипотеза Гольдбаха»

Несмотря на то, что простые числа изучаются математиками достаточно давно, на сегодняшний день остаются нерешёнными многие связанные с ними проблемы. Одной из наиболее известных нерешённых проблем является гипотеза Гольдбаха, которая формулируется следующим образом:

  • Верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел (бинарная гипотеза Гольдбаха)?
  • Верно ли, что каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел (тернарная гипотеза Гольдбаха)?

Следует сказать, что тернарная гипотеза Гольдбаха является частным случаем бинарной гипотезы Гольдбаха, или, как говорят математики, тернарная гипотеза Гольдбаха является более слабой, чем бинарная гипотеза Гольдбаха.

Гипотеза Гольдбаха получила широкую известность за пределами математического сообщества в 2000-м году благодаря рекламному маркетинговому трюку издательских компаний Bloomsbury USA (США) и Faber and Faber (Великобритания). Указанные издательства, выпустив книгу «Uncle Petros and Goldbach’s Conjecture» («Дядюшка Петрос и гипотеза Гольдбаха»), пообещали выплатить в течение 2-х лет с момента издания книги приз 1 миллион долларов США тому, кто докажет гипотезу Гольдбаха. Иногда упомянутый приз от издательств путают с премиями за решение «Задач тысячелетия» (Millennium Prize Problems). Не стоит заблужаться, гипотеза Гольдбаха не отнесена «Институтом Клэя» к «задачам тысячелетия», хотя и является при этом тесно связанной с гипотезой Римана — одной из «задач тысячелетия».

Книга «Простые числа. Долгая дорога к бесконечности»

primes

Обложка книги «Мир математики. Простые числа. Долгая дорога к бесконечности»

Дополнительно рекомендую прочесть увлекательную научно-популярную книгу «Мир математики. Простые числа. Долгая дорога к бесконечности», в аннотации к которой сказано: «Поиск простых чисел — одна из самых парадоксальных проблем математики. Ученые пытались решить ее на протяжении нескольких тысячелетий, но, обрастая новыми версиями и гипотезами, эта загадка по-прежнему остается неразгаданной. Появление простых чисел не подчинено какой-либо системе: они возникают в ряду натуральных чисел самопроизвольно, игнорируя все попытки математиков выявить закономерности в их последовательности. Эта книга позволит читателю проследить эволюцию научных представлений с древнейших времен до наших дней и познакомит с самыми любопытными теориями поиска простых чисел».

Дополнительно процитирую начало второй главы этой книги: «Простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом, было бы очень полезно проследить увлекательную и сложную историю теории простых чисел: как именно она развивалась, как именно были собраны факты и истины, которые в настоящее время считаются общепринятыми. В этой главе мы увидим, как целые поколения математиков тщательно изучали натуральные числа в поисках правила, предсказывающего появление простых чисел, — правила, которое в процессе поиска становилось все более и более ускользающим. Мы также подробно рассмотрим исторический контекст: в каких условиях математики работали и в какой степени в их работе применялись мистические и полурелигиозные практики, которые совсем не похожи на научные методы, используемые в наше время. Тем не менее медленно и с трудом, но была подготовлена почва для новых воззрений, вдохновлявших Ферма и Эйлера в XVII и XVIII в.в.»

Вернуться назад...

МЕТКИ >, , , ,