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

«Странный вопрос, — удивится читатель. — Каждый знает, что простое число — это число, большее единицы, которое делится только на единицу и на себя». Конечно, это так, но с таким определением работать нелегко — ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей — всех натуральных чисел, кроме 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).