Простое число — это натуральное (целое положительное) число , которое делится без остатка только на два натуральных числа: на и на само себя. Иными словами, простое число имеет ровно два натуральных делителя: и само число .
В силу определения, множество всех делителей простого числа является двухэлементным, т.е. представляет собой множество .
Множество всех простых чисел обозначают символом . Таким образом, в силу определения множества простых чисел, мы можем записать: .
Последовательность простых чисел выглядит так:
Основная теорема арифметики
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа являются элементарными «строительными блоками» множества натуральных чисел.
Разложение натурального числа title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют каноническим :
где — простое число, и . Например, каноническое разложение натурального числа выглядит так: .
Представление натурального числа в виде произведения простых также называют факторизацией числа .
Свойства простых чисел
Решето Эратосфена
Одним из наиболее известных алгоритмов поиска и распознавания простых чисел является решето Эратосфена . Так этот алгоритм был назван в честь греческого математика Эратосфена Киренского, которого считают автором алгоритма.
Для нахождения всех простых чисел, меньших заданного числа , следуя методу Эратосфена, нужно выполнить следующие шаги:
Шаг 1.
Выписать подряд все натуральные числа от двух до , т.е. .
Шаг 2.
Присвоить переменной значение , то есть значение равное наименьшему простому числу.
Шаг 3.
Вычеркнуть в списке все числа от до кратные , то есть числа: .
Шаг 4.
Найти первое незачёркнутое число в списке, большее , и присвоить переменной значение этого числа.
Шаг 5.
Повторить шаги 3 и 4 до достижения числа .
Процесс применения алгоритма будет выглядеть следующим образом:
Все оставшиеся незачёркнутые числа в списке по завершении процесса применения алгоритма будут представлять собой множество простых чисел от до .
Гипотеза Гольдбаха
Обложка книги «Дядюшка Петрос и гипотеза Гольдбаха»
Несмотря на то, что простые числа изучаются математиками достаточно давно, на сегодняшний день остаются нерешёнными многие связанные с ними проблемы. Одной из наиболее известных нерешённых проблем является гипотеза Гольдбаха , которая формулируется следующим образом:
- Верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел (бинарная гипотеза Гольдбаха)?
- Верно ли, что каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел (тернарная гипотеза Гольдбаха)?
Следует сказать, что тернарная гипотеза Гольдбаха является частным случаем бинарной гипотезы Гольдбаха, или, как говорят математики, тернарная гипотеза Гольдбаха является более слабой, чем бинарная гипотеза Гольдбаха.
Гипотеза Гольдбаха получила широкую известность за пределами математического сообщества в 2000-м году благодаря рекламному маркетинговому трюку издательских компаний Bloomsbury USA (США) и Faber and Faber (Великобритания). Указанные издательства, выпустив книгу «Uncle Petros and Goldbach’s Conjecture» («Дядюшка Петрос и гипотеза Гольдбаха»), пообещали выплатить в течение 2-х лет с момента издания книги приз 1 миллион долларов США тому, кто докажет гипотезу Гольдбаха. Иногда упомянутый приз от издательств путают с премиями за решение «Задач тысячелетия» (Millennium Prize Problems). Не стоит заблужаться, гипотеза Гольдбаха не отнесена «Институтом Клэя» к «задачам тысячелетия», хотя и является при этом тесно связанной с гипотезой Римана — одной из «задач тысячелетия».
Книга «Простые числа. Долгая дорога к бесконечности»
Обложка книги «Мир математики. Простые числа. Долгая дорога к бесконечности»
Дополнительно рекомендую прочесть увлекательную научно-популярную книгу , в аннотации к которой сказано: «Поиск простых чисел - одна из самых парадоксальных проблем математики. Ученые пытались решить ее на протяжении нескольких тысячелетий, но, обрастая новыми версиями и гипотезами, эта загадка по-прежнему остается неразгаданной. Появление простых чисел не подчинено какой-либо системе: они возникают в ряду натуральных чисел самопроизвольно, игнорируя все попытки математиков выявить закономерности в их последовательности. Эта книга позволит читателю проследить эволюцию научных представлений с древнейших времен до наших дней и познакомит с самыми любопытными теориями поиска простых чисел».
Дополнительно процитирую начало второй главы этой книги: «Простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом, было бы очень полезно проследить увлекательную и сложную историю теории простых чисел: как именно она развивалась, как именно были собраны факты и истины, которые в настоящее время считаются общепринятыми. В этой главе мы увидим, как целые поколения математиков тщательно изучали натуральные числа в поисках правила, предсказывающего появление простых чисел, - правила, которое в процессе поиска становилось все более и более ускользающим. Мы также подробно рассмотрим исторический контекст: в каких условиях математики работали и в какой степени в их работе применялись мистические и полурелигиозные практики, которые совсем не похожи на научные методы, используемые в наше время. Тем не менее медленно и с трудом, но была подготовлена почва для новых воззрений, вдохновлявших Ферма и Эйлера в XVII и XVIII в.в.»
Простые числа представляют собой одно из самых интересных математических явлений, которое привлекает к себе внимание ученых и простых граждан на протяжении уже более двух тысячелетий. Несмотря на то, что сейчас мы живем в век компьютеров и самых современных информационных программ, многие загадки простых чисел не решены до сих пор, есть даже такие, к которым ученые не знают, как подступиться.
Простые числа - это, как известно еще из курса элементарной арифметики, те которые делятся без остатка только на единицу и самое себя. Кстати, если натуральное число делится, кроме выше перечисленных, еще на какое-либо число, то оно именуется составным. Одна из самых знаменитых теорем гласит, что любое составное число может быть представлено в виде единственно возможного произведения простых чисел.
Несколько любопытных фактов. Во-первых, единица является уникальной в том плане, что, по сути, не принадлежит ни к простым, ни к составным числам. В то же время в научной среде все же принято относить ее именно к первой группе, так как формально она полностью удовлетворяет ее требованиям.
Во-вторых, единственным четным числом, затесавшимся в группу «простые числа» является, естественно, двойка. Любое другое четное число сюда попасть попросту не может, так как уже по определению, кроме себя и единицы, делится еще и на два.
Простые числа, список которых, как было указано выше, можно начинать с единицы, представляют собой бесконечный ряд, такой же бесконечный, как и ряд натуральных чисел. Опираясь на основную теорему арифметики, можно прийти к выводу, что простые числа никогда не прерываются и никогда не заканчиваются, так как в противном случае неизбежно прервался бы и ряд натуральных чисел.
Простые числа не появляются в натуральном ряду беспорядочно, как это может показаться на первый взгляд. Внимательно проанализировав их, можно сразу заметить несколько особенностей, наиболее любопытные из которых связаны с так называемыми числами-«близнецами». Называют их так потому, что каким-то непостижимым образом они оказались по соседству друг с другом, разделенные только четным разграничителем (пять и семь, семнадцать и девятнадцать).
Если внимательно к ним присмотреться, то можно заметить, что сумма этих чисел всегда кратна трем. Более того, при делении на тройку левого собрата в остатке всегда остается двойка, а правого - единица. Кроме того, само распределение этих чисел по натуральному ряду можно спрогнозировать, если представить весь этот ряд в виде колебательных синусоид, основные точки которых образуются при делении чисел на три и два.
Простые числа являются не только объектом пристального рассмотрения со стороны математиков всего мира, но уже давно и успешно используются в составлении различных рядов чисел, что является основой, в том числе, для шифрографии. При этом следует признать, что огромное количество загадок, связанных с этими замечательными элементами, все еще ждут своих разгадок, многие вопросы имеют не только философское, но и практичное значение.
Все натуральные числа, кроме единицы подразделяются на простые и составные. Простое число - это натуральное число, которое имеет только два делителя: единицу и само себя . Все остальные называются составными. Исследованием свойств простых чисел занимается специальный раздел математики - теория чисел. В теории колец простые числа соотносят с неприводимыми элементами.
Приведем последовательность простых чисел начиная с 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, ... и т.д.
Согласно основной теореме арифметики каждое натуральное число, которое больше единицы можно представить в виде произведения простых чисел. Вместе с тем это является единственным способом представления натуральных чисел с точностью до порядка следования сомножителей. Исходя из этого, можно сказать, что простые числа - это элементарные части натуральных чисел.
Такое представление натурального числа называется разложением натурального числа на простые числа или факторизацией числа.
Одним из самых древних и эффективных способов вычисления простых чисел является «решето Эрастофена».
Практика показала, что после вычисления простых чисел с помощью решета Эрастофена требуется проверить, является ли данное число простым. Для этого разработаны специальные тесты, так называемые тесты простоты. Алгоритм этих тестов являются вероятностными. Чаще всего их применяют в криптографии.
Кстати сказать, что для некоторых классов чисел существуют специализированные эффективные тесты простоты. К примеру, для проверки чисел Мерсенна на простоту применяют тест Люка-Лемера, а для проверки на простоту чисел Ферма - тест Пепина.
Все мы знаем, что чисел бесконечно много. Справедливо возникает вопрос: сколько же тогда существует простых чисел? Простых чисел также бесконечное количество. Наиболее древним доказательством этого суждения является доказательство Евклида, которое изложено в «Началах». Доказательство Евклида имеет следующий вид:
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число невозможно разделить ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Таким образом, число должно делиться на некоторое простое число, не включённое в этот набор.
Теорема распределения простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).
За тысячи лет исследования простых чисел, было выявлено, что наибольшим известным простым числом является 243112609 − 1. Это число включает 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Это открытие было сделано 23 августа 2008 года на математическом факультете университета uCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.
Главной отличительной особенностью чисел Мерсенна является наличие высоко эффективного теста простоты Люка - Лемера. С его помощью простые числа Мерсенна на протяжении длительного периода времени являются самыми большими из известных простых чисел.
Однако по сей день многие вопросы относительно простых чисел не получили точных ответов. На 5-м Международном математическом конгрессе Эдмунд Ландау сформулировал основным проблемы в области простых чисел:
Проблема Гольдбаха или первая проблема Ландау заключается в том, что необходимо доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.
Вторая проблема Ландау требует найти ответ на вопрос: бесконечно ли множество «простых близнецов» - простых чисел, разность между которыми равна 2?
Гипотеза Лежандра или третья проблема Ландау такова: верно ли, что между n2 и (n + 1)2 всегда найдётся простое число?
Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?
Помимо вышеперечисленных проблем существует проблема определения бесконечного количества простых чисел во многих целочисленных последовательностях типа числа Фибоначчи, числа Ферма и т. д.
Перебор делителей. По определению число n является простым лишь в том случае, если оно не делится без остатка на 2 и другие целые числа, кроме 1 и самого себя. Приведенная выше формула позволяет удалить ненужные шаги и сэкономить время: например, после проверки того, делится ли число на 3, нет необходимости проверять, делится ли оно на 9.
- Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.
Узнайте о модульной арифметике. Операция "x mod y" (mod является сокращением латинского слова "modulo", то есть “модуль”) означает "поделить x на y и найти остаток". Иными словами, в модульной арифметике по достижении определенной величины, которую называют модулем , числа вновь "превращаются" в ноль. Например, часы отсчитывают время с модулем 12: они показывают 10, 11 и 12 часов, а затем возвращаются к 1.
- Во многих калькуляторах есть клавиша mod. В конце данного раздела показано, как вручную вычислять эту функцию для больших чисел.
Узнайте о подводных камнях малой теоремы Ферма. Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке "чисел Кармайкла" (составных чисел, которые удовлетворяют данному тесту) и "псевдопростых чисел Ферма" (эти числа соответствуют условиям теста лишь при некоторых значениях a ).
Если удобно, используйте тест Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма. Составное число не будет принято за простое, если провести расчеты для более ¼ значений a . Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.
Для больших чисел используйте модульную арифметику. Если у вас под рукой нет калькулятора с функцией mod или калькулятор не рассчитан на операции с такими большими числами, используйте свойства степеней и модульную арифметику, чтобы облегчить вычисления. Ниже приведен пример для 3 50 {\displaystyle 3^{50}} mod 50:
- Перепишите выражение в более удобном виде: mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
- (3 25 ∗ 3 25) {\displaystyle (3^{25}*3^{25})} mod 50 = mod 50 mod 50) mod 50. Здесь мы учли свойство модульного умножения.
- 3 25 {\displaystyle 3^{25}} mod 50 = 43.
- (3 25 {\displaystyle (3^{25}} mod 50 ∗ 3 25 {\displaystyle *3^{25}} mod 50) mod 50 = (43 ∗ 43) {\displaystyle (43*43)} mod 50.
- = 1849 {\displaystyle =1849} mod 50.
- = 49 {\displaystyle =49} .
Простым числом является натуральное число, которое делится только на себя и на единицу.
Остальные числа называют составными.
Простые натуральные числа
Но не все натуральные числа являются простыми числами.
Простыми натуральными числами являются лишь те из них, которые делятся только на себя и на единицу.
Примеры простых чисел:
2; 3; 5; 7; 11; 13;...
Простые целые числа
Из следует, что простыми числами являются только натуральные числа.
Это значит, что простые числа обязательно являются натуральными.
Но все натуральные числа являются одновременно целыми числами.
Таким образом, все простые числа являются целыми.
Примеры простых чисел:
2; 3; 5; 7; 11; 13; 17; 19; 23;...
Четные простые числа
Имеется только одно четное простое число - это число два.
Все остальные простые числа нечетные.
А почему не может быть простым числом четное число больше двух?
А потому, что любое четное число больше двух будет делиться на себя, не единицу и на два, т.е такое число всегда будет иметь три делителя, а возможно и больше.
