Что такое простое число?

«Странный вопрос, — удивится читатель. — Каждый знает, что простое число — это число, большее единицы, которое делится только на единицу и на себя». Конечно, это так, но с таким определением работать нелегко — ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей — всех натуральных чисел, кроме 1 и самого числа. Лучше сказать так: число p является простым, если p>1 и p не делится ни на какое число, меньшее p и отличное от 1. Для наших же целей больше подходит следующее определение: число p является простым, если p>1, и для любого числа q, меньшего p, Н.О.Д.(q, p) = 1.

В этом определении нет ограничения q ≠ 1 и, что более важно, оно позволяет переменное число условий Н.О.Д.(1, p) = 1, Н.О.Д.(2, p) = 1,..., Н.О.Д.(p–1, p) = 1 свести в одно условие:

Н.О.Д.((p–1)!, p) = 1.

Сделанное замечание позволяет нам написать первую систему условий, эквивалентную условию (11) относительно параметра p:

ì í î

p = r + 1 s = r!, Н.О.Д.(s, p) = 1.

(15)

(16)

(17)

Первое из этих условий имеет искомый вид экспоненциально диофантова (более того, диофантова) уравнения, а третье легко приводится к такому же виду за счёт введения двух новых неизвестных:

Лемма 3. Условие (17) эквивалентно относительно параметров p, s условию

x1·s – x2·p = 1.

(18)

Так как уравнение (18) экспоненциально диофантово, то нам осталось лишь найти систему экспоненциально диофантовых уравнений, эквивалентную относительно параметров r и s условию (16).

Дата добавления: 2014-01-03