Науколандия

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

Существуют различные свойства простых чисел. Часть из них доказана, другая – нет, какие-то существуют в статусе предположений. Среди основных доказанных свойств можно выделить следующие.

Доказательство этого свойства можно посмотреть здесь.

Пусть 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 не делится, значит это простое число.

Недоказанные свойства простых чисел: