Простые числа в математике
Простые числа — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.
Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом.
13 ÷ 4 = 3 (остаток 1).
Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.
30 не является примером простого числа, потому что его можно разделить на 1,2,3,5,6,10,15,30. Таким образом, 30 является примером составного числа, поскольку оно имеет более двух факторов.
Ноль, единица и числа меньше единицы не считаются простыми числами.
Основная теорема арифметики, лемма Евклида
Основная идея теоремы арифметики — это любое целое число больше 1 либо является простым числом, либо может быть получено путем умножения простых чисел вместе.
Фундаментальная теорема арифметики (название которой указывает на ее основную важность) гласит, что любое число может быть учтено в уникальном списке простых чисел.
Простое число (2,3,5,7,11. ) против составного (4=2×2, 6=2×3, 8=2x2x2, 12=2x2x3. ).
Этот ряд примеров можно продолжить:
- 10 равно 2×5;
- 11 — простое число;
- 12 — 2×2×3;
- 13 — это простое число;
- 14 равно 2×7;
- 15 равно 3×5;
- 16 равно 2×2×2×2;
- 17 является простым и т.д.
Таким образом, они либо простые, либо простые числа, умноженные друг на друга.
Число 42. Можем ли мы получить 42, умножив только простые числа?
Да, 2, 3 и 7 являются простыми числами, и при умножении вместе они составляют 42.
Число 7. 7 уже является простым числом
Число 22. 22 может быть получено путем умножения простых чисел 2 и 11 вместе.
Никакая другая комбинация простых чисел не будет работать.
Лемма — это, как правило, незначительное, доказанное утверждение, которое используется в качестве ступеньки к доказательству более сложной математической теории. По этой причине она также известна как «вспомогательная теорема».
В теории чисел лемма Евклида — это лемма, которая отражает фундаментальное свойство простых чисел, а именно: если простое число p делит произведение ab двух целых чисел a и b, то p должно разделить, по крайней мере, одно из этих целых чисел a и b.
Если p = 19, a = 133, b = 143, то ab = 133 × 143 = 19019, и поскольку это делится на 19, лемма подразумевает, что один или оба из 133 или 143 также должны быть. На самом деле 133 = 19 × 7.
Если предпосылка леммы не выполняется, т. е. p является составным числом, его следствие может быть либо истинным, либо ложным.
В случае p = 10, a = 4, b = 15 составное число 10 делит ab = 4 × 15 = 60, но 10 не делит ни 4, ни 15.
Это свойство является ключевым в доказательстве фундаментальной теоремы арифметики. Лемма Евклида показывает, что в целых числах неприводимые элементы также являются простыми элементами.
Таким образом, изучение чисел в основном сводится к изучению свойств простых чисел. Математики на протяжении тысячелетий довольно много выяснили о простых числах. Одно из самых известных доказательств Евклида показывает, что существует бесконечно много простых чисел.
Как определить простые числа
Сначала попробуйте разделить его на 2 и посмотреть, получится ли целое число. Если да, то оно не может быть простым числом. Если вы не получите целое число, затем попробуйте разделить его на простые числа: 3, 5, 7, 11 (9 делится на 3) и так далее, всегда делясь на простое число.
8 простых чисел до 20: 2, 3, 5, 7, 11, 13, 17 и 19.
Первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Таблица простых чисел до 1000:
| 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 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 |
| 173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 |
| 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |
| 281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 |
| 349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 |
| 409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 |
| 463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |
| 541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 |
| 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 |
| 659 | 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |
| 733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 |
| 809 | 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |
| 863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 |
| 941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
2 — наименьшее простое число. Это также единственное четное простое число — все остальные четные числа могут быть разделены сами по себе на 1 и 2, что означает, что у них будет, по крайней мере, 3 фактора.
Один из самых известных математиков классической эпохи, Евклид, записал доказательство того, что не существует самого большого простого числа. Самое большое известное простое число (по состоянию на ноябрь 2020 года) составляет 282 589 933-1, число, которое имеет 24 862 048 цифр при записи в базе 10. До этого самым большим известным простым числом было 277 232 917-1, состоящее из 23 249 425 цифр.
За исключением 2 и 3, все остальные простые числа могут быть выражены в общей форме как 6n + 1 или 6n — 1, где n — натуральное число.
Чтобы определить, является ли число простым или составным, нужно решить пример на делимость в следующем порядке (от простого к сложному): 2, 5, 3, 11, 7, и 13. Если вы обнаружите, что число делится на одно из них, и вы знаете, что оно составное, не нужно выполнять остальные тесты.
Если число меньше 121 не делится на 2, 3, 5 или 7, оно простое; в противном случае оно составное.
Если число меньше 289 не делится на 2, 3, 5, 7, 11, или 13, это простое число; в противном случае оно составное.
Примеры решения задач
Является ли 19 простым числом или нет?
Как понять, что число простое можно двумя способами.
Формула для простого числа равна 6n + 1
Запишем данное число в виде 6n + 1.
6(3) + 1 = 18 + 1 = 19
Проверьте на наличие факторов 19
Следовательно, с помощью обоих методов докажем, что 19 имеет только два фактора 1 и 19, что означает простое число.
53 — это простое число или нет?
Как доказать, что число простое, используя приведенную ниже формулу. Чтобы узнать простые числа, превышающие 40, можно:
n2 + n + 41, где n = 0, 1, 2, . 39
32 + 3 + 41 = 9 + 3 + 41 = 53
53 имеет только факторы 1 и 53.
Итак, 53 является простым числом по обоим методам.
Является ли число простым или составным?
Число 185 заканчивается на 5, поэтому оно делится на 5. Оно составное.
Как проверить простое ли число 243?
Число 243 заканчивается нечетным числом, поэтому оно не делится на 2. Он не заканчивается на 5 или 0, поэтому он не делится на 5. Его цифровой корень равен 9 (потому что 2 + 4 + 3 = 9), так что оно делится на 3.
Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Составное число – это натуральное число, имеющее более двух положительных делителей.
Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а , то есть оно будет делиться само на себя и на 1 . Дадим определение целых чисел.
Натуральные числа, которые не являются простыми, называют составными.
Простые числа: 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 , 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 делителем а .
Простых чисел бесконечно много.
Предположительно возьмем конечное количество натуральных чисел 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 . Произвести последовательное зачеркивание. Получим таблицу вида:
Далее вычеркиваем все числа, кратные 3 . Получаем таблицу вида:
Переходим к вычеркиванию чисел, кратных 5 . Получим:
Вычеркиваем числа, кратные 7 , 11 . В конечном итоге таблица получает вид
Перейдем к формулировке теоремы.
Наименьший положительный и отличный от 1 делитель основного числа а не превосходит a , где a является арифметическим корнем заданного числа.
Необходимо обозначить 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 . Поиск чисел производится при помощи вычеркивания.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Доказать что число 898989898989898989 является составным.
Решение
Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.
Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.
Определить составное или простое число 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 .
Алгоритм проверки на простоту за O (log N)
Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма: 
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю. Ее смысл очень похож на быстрое возведение в степень.
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Как проверить число на простоту?
Как быстро проверить, является ли данное натуральное число n простым? Такая задача часто возникает на практике. Один из примеров — шифр RSA 1 . Это асимметричный шифр: шифрование производится закрытым ключом (известен только отправителю), а расшифровка — открытым (известен всем). Чтобы сгенерировать такую пару ключей для шифра RSA, нужно выбрать два больших числа p и q, причем оба числа должны быть простыми — иначе шифр невозможно будет расшифровать.
Проще всего действовать по определению, перебирая все числа от 1 до n и проверяя, не является ли какое-то из них делителем. Этот способ можно немного усовершенствовать: если n = ab, то меньший из двух делителей a и b окажется меньше или равен \(\sqrt
Время работы такого алгоритма, однако, будет огромным. Например, если в двоичной записи числа n тысяча разрядов (это минимальная длина криптографического ключа RSA, гарантирующая безопасность), то число проверок равно \(\sqrt
Начнем с малой теоремы Ферма (МТФ): если n — простое число, то для любого a от 1 до n − 1 число a n − 1 при делении на n дает остаток 1 (т. е. a n − 1 ≡ 1(mod n)). Значит, если мы вдруг нашли такое a, что остаток оказался другим, то n заведомо не простое! Разумеется, перебирать все a в попытке найти нужное — затея не лучше, чем перебирать возможные делители. Но мы попробуем угадать a, выбирая его случайным образом.
Эта идея не такая безнадежная, как может показаться на первый взгляд. Действительно, пусть оказалось, что a0 n − 1 \(\not≡\) 1(mod n), а a1 n − 1 ≡ 1(mod n) (т. е. если мы выбрали a0 , то мы угадали, а если выбрали a1, то нет). Тогда (a0 ⋅ a1) n − 1 ≡ a0 n − 1 ⋅ a1 n − 1 ≡ a0 n − 1 \(\not≡\) 1(mod n) . Таким образом, если мы угадали с выбором a0, то также удачным будет выбор a0 ⋅ a1. Более того, если a0 взаимно просто с n, то для разных значений a1 числа a1 ⋅ a2 будут различны по модулю n. Таким образом, среди всех чисел от 1 до n − 1, взаимно простых с n, окажется не менее половины «удачных»: действительно, каждому «неудачному» числу a1 соответствует как минимум одно уникальное «удачное», равное остатку от деления a0 ⋅ a1 на n (где a0 — одно фиксированное «удачное» число).
Итак, алгоритм — его называют тестом Ферма — действует так. Выбираем случайное a в диапазоне от 2 до n − 1 (число 1 выбирать бессмысленно). Если a не взаимно просто с n — это можно быстро проверить с помощью алгоритма Евклида 2 , то n заведомо составное. Иначе вычисляем остаток от деления a n − 1 на n, и если он не равен 1, то n — составное. Если же равен, то вероятность того, что мы выбрали «неудачное» a, а для другого a получился бы неединичный остаток, не превосходит 1/2. Возвести a в большую степень можно методом последовательного деления показателя пополам («быстрое возведение в степень»); при этом после каждого шага лучше брать остаток по модулю n, чтобы избежать слишком больших чисел. Повторяя алгоритм k раз, каждый раз выбирая случайное a независимо, мы уменьшим эту вероятность до 1/2 k , что очень быстро стремится к нулю с ростом k.
Подведем итог. Если тест Ферма отвечает, что n составное, то он совершенно точно прав; если говорит, что простое — то может ошибиться, но с очень малой вероятностью. Эту вероятность мы контролируем за счет изменения параметра k — например, можем сделать ее меньше, чем вероятность сбоя техники. Тогда на практике алгоритм будет неотличим от точного — а работает он намного быстрее, чем перебор делителей!
К сожалению, у теста Ферма есть фатальный недостаток. Существуют так называемые числа Кармайкла: эти вредные числа не являются простыми, но удовлетворяют МТФ для любого a, взаимно простого с n. В таком случае мы не сможем найти ни одного «удачного» a0, и приведенное выше рассуждение недействительно. (Вероятность же случайно наткнуться на число a, не взаимно простое с n, мала.) Самые маленькие числа Кармайкла: 561, 1105, 1729. Числа Кармайкла относительно редки, однако, к сожалению, их бесконечно много 3 . (Иначе можно было бы «починить» тест Ферма, добавив в начале сверку с конечным списком чисел Кармайкла.)
Итак, получается алгоритм: выбираем случайное a от 2 до n − 1, взаимно простое с n (если нашлось не взаимно простое — немедленно отвечаем, что n составное); вычисляем остаток от деления \(a^<\frac
Существуют и другие вероятностные тесты на простоту. А можно ли построить алгоритм проверки на простоту, который работает быстро и при этом выдает ответ точно, а не с некоторой (пусть и сколь угодно близкой к 1) вероятностью? Такие тесты называются детерминированными. Таков тест Миллера (1976). Этот тест быстрый и детерминированный, однако доказательство того, что он работает правильно, опирается на недоказанное утверждение — расширенную гипотезу Римана. Быстрый детерминированный тест, корректность которого доказана полностью, был предложен сравнительно недавно — это тест Агравала — Каяла — Саксены или AKS-тест (2002). Однако вероятностные тесты все еще работают быстрее, чем AKS-тест.
1 Подробнее о шифре RSA читайте в статье В.А. Успенского «Как теория чисел помогает в шифровальном деле» (Соросовский образовательный журнал, 1996, №6).
2 Вагутен В. Алгоритм Евклида и основная теорема арифметики («Квант», 1972, №6); Абрамов С. Самый знаменитый алгоритм («Квант», 1985, №11).