Свойства простых чисел
Существуют различные свойства простых чисел. Часть из них доказана, другая – нет, какие-то существуют в статусе предположений. Среди основных доказанных свойств можно выделить следующие.
- Множество простых чисел бесконечно (т. е. среди простых чисел нет наибольшего).
Доказательство этого свойства можно посмотреть здесь.
- Среди простых делителей составного числа есть хотя бы один, квадрат которого меньше или равен данному составному числу.
Пусть p – наименьший простой делитель числа n. Докажем, что p2 ≤ n.
Если p — делитель составного числа n, тогда должен существовать другой делитель q числа n такой, что n = pq. Поскольку p наименьший простой делитель, то делителей меньше его быть не может, поэтому q ≥ p. Из этого следует, что p * p ≤ p * q, т. е. p2 ≤ pq или p2 ≤ n.
Это свойство используют при проверке числа на простоту. Если всегда существует простой делитель составного числа, квадрат которого меньше этого числа или равен ему, то незачем искать остальные делители, чтобы сделать вывод о том, что проверяемое число составное. Поэтому можно ограничиться проверкой делимости числа n на простые делители p, для которых p2 ≤ n.
Обычно при этом из n извлекают корень и округляют до целого. После этого перебирают все делители до полученного числа. Если ни один из них не является делителем для n, то значит других простых делителей нет и исследуемое число простое.
Например, проверим число 37 на простоту. Корень из 37, округленный до целого в меньшую сторону, равен 6. Следовательно, надо проверить делимость на 2, 3, 4, 5, 6. Ни на одно из этих чисел 37 не делится, значит это простое число.
- Все натуральные числа можно представить в виде суммы двадцати простых слагаемых.
- «Малая теорема Ферма»: если p – простое число, такое что число n на него не делится, то число np - 1 - 1 всегда делится на p. Например, 34 не делится на 3, но 343-1 - 1 = 342 - 1 = 1156 - 1 = 1155 делится на 3.
Недоказанные свойства простых чисел:
- Любое четное число можно выразить в виде суммы двух простых чисел. Например, 16 = 11 + 5, 64 = 23 + 41, 66 = 29 + 37.
- Любое большое нечетное число можно представить в виде суммы трех простых нечетных чисел.
- Любые большие четные числа можно представить в виде суммы четырех простых нечетных чисел.
- Любое четное число можно представить в виде разности двух простых чисел.