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

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

Как вычислить факториал?

В условие (16) входит r!; этот-то факториал и «мешает» нам. Вспомним, что факториал фигурирует в выражении для биномиальных коэффициентов ¹⁰: при t ≥ r

(  t r ) =

t(t – 1) ... (t – r + 1) r!

,

то есть

r! =

t(t – 1) ... (t – r + 1) (tr)

.

Многочлен, стоящий в числителе, имеет довольно сложную структуру. Попытаемся заменить его более простым — а именно, многочленом t^r. При t ≥ r имеем:

tr (tr)  =  tr  t(t – 1) ... (t – r + 1)  · r! =  =  ( 1 +  1 t – 1 )( 1 +  2 t – 2 )  · ... ·  ( 1 +  r – 1 t – r + 1 )  · r! ≥ r!.

(19)

Легко видеть, что

r! =  lim  t→∞  tr (tr)  ,

(20)

однако эта запись факториала нам ничего не даст, поскольку t, будучи параметром в искомой системе уравнений, сможет принимать любые, сколь угодно большие, но конечные значения. Но мы и не будем переходить к пределу, а воспользуемся целочисленностью r! — из (19) и (20) следует, что при достаточно больших t

r! =    tr (tr)    .

(21)

Лемма 4. Формула (21) верна как только t≥2r^r+2.

Лемма 4 позволяет преобразовать условие (16) в эквивалентную ему относительно параметров r и s систему (проверьте эквивалентность!)

ì

ï

í

ï

î

t = 2rr+2,

c = (tr),

tr = s · c + (x3 – 1),

(x3 – 1) + x4 = c.

(22)

(23)

(24)

(25)

Здесь условия (22), (24) и (25) имеют требуемый вид, и нам остаётся лишь найти систему экспоненциально диофантовых уравнений, эквивалентных условию (23) относительно параметров r, t и c.

Итак, нам осталось «избавиться» от биномиального коэффициента.