То, что существуют числа, которые не делятся ни на какое другое число, люди знали еще в древности. Последовательность простых чисел имеет примерно следующий вид:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Доказательство того, что этих чисел бесконечно много, дал еще Евклид , живший в 300 г до н.э. Примерно в те же годы другой греческий математик, Эратосфен , придумал довольно-таки простой алгоритм получения простых чисел, суть которого была в последовательном вычеркивании чисел из таблицы. Те оставшиеся числа, которые ни на что не делились, и были простыми. Алгоритм называется «решето Эратосфена» и за счет своей простоты (в нем нет операций умножения или деления, только сложение) используется в компьютерной технике до сих пор.

Видимо, уже во время Эратосфена стало ясно, что какого-либо четкого критерия, является ли число простым, не существует — это можно проверить лишь экспериментально. Существуют различные способы для упрощения процесса (например, очевидно, что число не должно быть четным), но простой алгоритм проверки не найден до сих пор, и скорее всего найден не будет: чтобы узнать, простое число или нет, надо попытаться разделить его на все меньшие числа.

Подчиняются ли простые числа каким-либо законам? Да, и они довольно любопытны.

Так, например, французский математик Мерсенн еще в 16 веке обнаружил, что много простых чисел имеет вид 2^N — 1, эти числа названы числами Мерсенна. Еще незадолго до этого, в 1588 году, итальянский математик Катальди обнаружил простое число 2 19 — 1 = 524287 (по классификации Мерсена оно называется M19). Сегодня это число кажется весьма коротким, однако даже сейчас с калькулятором проверка его простоты заняла бы не один день, а для 16 века это было действительно огромной работой.

На 200 лет позже математик Эйлер нашел другое простое число 2 31 — 1 = 2147483647. Опять же, необходимый объем вычислений каждый может представить сам. Он же выдвинул гипотезу (названную позже «проблемой Эйлера», или «бинарной проблемой Гольдбаха»), суть которой проста: каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Например, можно взять 2 любых четных числа: 123456 и 888777888.

С помощью компьютера можно найти их сумму в виде двух простых чисел: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересно здесь то, что точное доказательство этой теоремы не найдено до сих пор, хотя с помощью компьютеров она была проверена до чисел с 18 нулями.

Существует и другая теорема математика Пьера Ферма , открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4*k+1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4*111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197*19197 + 8710*8710.

Теорема была доказана Эйлером лишь через 100 лет.

И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.

Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И.М. Первушин из Пермского уезда доказал простоту числа 2 61 — 1 = 2305843009213693951 . Даже сейчас бытовые калькуляторы не могут работать со столь длинными числами, а на то время это была поистине гигантская работа, и как это было сделано, не очень ясно до сих пор. Хотя действительно существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно.

Современность

Актуальны ли простые числа сегодня? Еще как! Простые числа являются основой современной криптографии, так что большинство людей пользуются ими каждый день, даже не задумываясь об этом. Любой процесс аутентификации, например, регистрация телефона в сети, банковские платежи и прочее, требуют криптографических алгоритмов.

Суть идеи тут крайне проста и лежит в основе алгоритма RSA , предложенного еще в 1975 году. Отправитель и получатель совместно выбирают так называемый «закрытый ключ», который хранится в надежном месте. Этот ключ представляет собой, как, наверное, читатели уже догадались, простое число. Вторая часть — «открытый ключ», тоже простое число, формируется отправителем и передается в виде произведения вместе с сообщением открытым текстом, его можно опубликовать даже в газете. Суть алгоритма в том, что не зная «закрытой части», получить исходный текст невозможно.

К примеру, если взять два простых числа 444388979 и 444388909, то «закрытым ключом» будет 444388979, а открыто будут передано произведение 197481533549433911 (444388979*444388909). Лишь зная вторую половинку, можно вычислить недостающее число и расшифровать им текст.

В чем тут хитрость? А в том, что произведение двух простых чисел вычислить несложно, а вот обратной операции не существует — если не знать первой части, то такая процедура может быть выполнена лишь перебором. И если взять действительно большие простые числа (например, в 2000 символов длиной), то декодирование их произведения займет несколько лет даже на современном компьютере (к тому времени сообщение станет давно неактуальным).

Гениальность данной схемы в том, что в самом алгоритме нет ничего секретного — он открыт и все данные лежат на поверхности (и алгоритм, и таблицы больших простых чисел известны). Сам шифр вместе с открытым ключом можно передавать как угодно, в любом открытом виде. Но не зная секретной части ключа, которую выбрал отправитель, зашифрованный текст мы не получим. Для примера можно сказать, что описание алгоритма RSA было напечатано в журнале в 1977 году, там же был приведен пример шифра. Лишь в 1993 году при помощи распределенных вычислений на компьютерах 600 добровольцев, был получен правильный ответ.

Так что простые числа оказались вовсе не столь просты, и их история на этом явно не заканчивается.

Перебор делителей. По определению число 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} .

    • В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.

    Yandex.RTB R-A-339285-1

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

    Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.

    Определение 1

    Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .

    Определение 2

    Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.

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

    Определение 3

    Простые числа – это натуральные числа, имеющие только два положительных делителя.

    Определение 4

    Составное число – это натуральное число, имеющее более двух положительных делителей.

    Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а, то есть оно будет делиться само на себя и на 1 . Дадим определение целых чисел.

    Определение 5

    Натуральные числа, которые не являются простыми, называют составными.

    Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.

    Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

    Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.

    Рассмотрим теорему, которая объясняет последнее утверждение.

    Теорема 1

    Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

    Доказательство 1

    Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.

    Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 < b 1 < b было выполнено.

    Из условия видно, что а делится на b , b делится на b 1 , значит, понятие делимости выражается таким образом: a = b · q и b = b 1 · q 1 , откуда a = b 1 · (q 1 · q) , где q и q 1 являются целыми числами. По правилу умножения целых чисел имеем, что произведение целых чисел – целое число с равенством вида a = b 1 · (q 1 · q) . Видно, что b 1 – это делитель для числа а. Неравенство 1 < b 1 < b не соответствует, потому как получим, что b является наименьшим положительным и отличным от 1 делителем а.

    Теорема 2

    Простых чисел бесконечно много.

    Доказательство 2

    Предположительно возьмем конечное количество натуральных чисел n и обозначим как p 1 , p 2 , … , p n . Рассмотрим вариант нахождения простого числа, отличного от указанных.

    Примем на рассмотрение число р, которое равняется p 1 , p 2 , … , p n + 1 . Оно не равняется каждому из чисел, соответствующих простым числам вида p 1 , p 2 , … , p n . Число р является простым. Тогда считается, что теорема доказана. Если оно составное, тогда нужно принять обозначение p n + 1 и показать несовпадение делителя ни с одним из p 1 , p 2 , … , p n .

    Если это было бы не так, тогда, исходя из свойства делимости произведения p 1 , p 2 , … , p n , получим, что оно делилось бы на p n + 1 . Заметим, что на выражение p n + 1 делится число р равняется сумме p 1 , p 2 , … , p n + 1 . Получим, что на выражение p n + 1 должно делиться второе слагаемое этой суммы, которое равняется 1 , но это невозможно.

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

    Так как простых чисел очень много, то таблицы ограничивают числами 100 , 1000 , 10000 и так далее.

    При составлении таблицы простых чисел следует учитывать то, что для такой задачи необходима последовательная проверка чисел, начиная с 2 до 100 . При отсутствии делителя оно фиксируется в таблицу, если оно составное, то в таблицу не заносится.

    Рассмотрим пошагово.

    Если начать с числа 2 , то оно имеет только 2 делителя: 2 и 1, значит, его можно занести в таблицу. Также и с числом 3 . Число 4 является составным, следует разложить его еще на 2 и 2 . Число 5 является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа 100 .

    Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.

    Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа 2 , 3 , 4 , … , 50 .

    Теперь необходимо зачеркнуть все числа, которые кратны 2 . Произвести последовательное зачеркивание. Получим таблицу вида:

    Переходим к вычеркиванию чисел, кратных 5 . Получим:

    Вычеркиваем числа, кратные 7 , 11 . В конечном итоге таблица получает вид

    Перейдем к формулировке теоремы.

    Теорема 3

    Наименьший положительный и отличный от 1 делитель основного числа а не превосходит a , где a является арифметическим корнем заданного числа.

    Доказательство 3

    Необходимо обозначить b наименьший делитель составного числа а. Существует такое целое число q , где a = b · q , причем имеем, что b ≤ q . Недопустимо неравенство вида b > q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .

    Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа, которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .

    Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n . В примере, где n = 50 , у нас имеется, что n = 50 . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50 . Поиск чисел производится при помощи вычеркивания.

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

    Пример 1

    Доказать что число 898989898989898989 является составным.

    Решение

    Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.

    Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.

    Пример 2

    Определить составное или простое число 11723 .

    Решение

    Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .

    Отсюда видим, что 11723 < 200 , то 200 2 = 40 000 , а 11 723 < 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

    Для более точной оценки числа 11723 необходимо записать выражение 108 2 = 11 664 , а 109 2 = 11 881 , то 108 2 < 11 723 < 109 2 . Отсюда следует, что 11723 < 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

    При разложении получим, что 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 – это все простые числа. Весь данный процесс можно изобразить как деление столбиком. То есть разделить 11723 на 19 . Число 19 является одним из его множителей, так как получим деление без остатка. Изобразим деление столбиком:

    Отсюда следует, что 11723 является составным числом, потому как кроме себя и 1 имеет делитель 19 .

    Ответ: 11723 является составным числом.

    Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter