4. ДЕСЯТАЯ ПРОБЛЕМА ГИЛЬБЕРТА

4.1. История проблемы и ее решения

Задачами, приводящими к решению уравнений в целых числах, математики интересовались со времен Пифагора (VI в. до н.э.). Давно известно, что некоторые уравнения вообще не имеют решений в целых числах (например, 2x+2y=1, поскольку при любых целых x,y левая часть является четным числом). Другие имеют конечное число решений (например, x²+y²=2 сводится к x²=1, y²=1, т.е. получаются четыре решения). Наконец, бывают уравнения, имеющие бесконечно много решений в целых числах. В качестве примера рассмотрим уравнение 3x-7y=1. Решая относительно x, получаем

x = (7y+1)/3 = 2y + (y+1)/3.

Число (y+1)/3 должно быть целым, обозначим его через t, тогда y=3t-1, x=2y+t=7t-2. Какое бы t мы ни взяли, получается целое решение уравнения.

По каким признакам определить, имеет ли данное уравнение решения в целых числах, и если имеет - то сколько их? Прежде чем искать ответ на этот вопрос, следует уточнить класс уравнений, о котором идет речь. Имеются в виду уравнения типа P=Q, где P, Q - выражения, составленные из символов неизвестных (их может быть один, два, три и больше), из целых чисел и операций сложения, вычитания и умножения. Уравнения такого рода (при условии, что нас интересуют только целые решения) принято называть диофантовыми уравнениями (в честь Диофанта, который в III в. н.э. занимался задачами, приводящими к таким уравнениям). Говоря современным языком, речь идет о решении в целых числах уравнений вида P=0, где P - полином (от одной или нескольких переменных) с целыми коэффициентами.

Следующий способ решения любого уравнения первой степени с двумя неизвестными был известен еще в средние века. Пусть дано уравнение ax+by=c. Если наибольший общий делитель чисел a, b не является делителем числа c, то уравнение не имеет целых решений. Если является - делим обе стороны уравнения на этот общий делитель и начинаем применять метод редукции коэффициентов (как выше, при решении уравнения 3x-7y=1). Через конечное число шагов приходим к формулам вида x=dt+e, y=gt+h, которые при любом t дают решение исходного уравнения ax+by=c (решений в этом случае получается бесконечно много, поскольку всегда d, g<>0).

Далее, общий метод решения диофантовых уравнений второй степени с двумя неизвестными был найден Ж.Лагранжем в XVIII в.

К сожалению, это почти все сколько-нибудь общие результаты исчерпывающего характера. Остальные исследования давали множество тонких, но частных методов, применимых к уравнениям третьей, четвертой степени и т.д. весьма специальных видов (а то и только к отдельному уравнению). Чем объясняется этот контраст между первоначальными успехами и отсутствием дальнейшего продвижения (несмотря на исключительное развитие математики в целом)?

В августе 1900 г. в Париже состоялся II Международный конгресс математиков. 8 августа Д.Гильберт прочитал на нем доклад "Математические проблемы". Среди 23 проблем, решение которых (по мнению Д.Гильберта) совершенно необходимо было получить в наступающем XX в., десятую проблему он определил следующим образом (см. Д.Гильберт [1900]):

"Пусть задано диофантово уравнение с произвольным числом неизвестных и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах".

Сама формулировка показывает, что тогда, в 1900 г., с определенностью можно было говорить только о положительном решении десятой проблемы Гильберта - об "указании способа". Что для всего огромного разнообразия уравнений единый "способ решения" может отсутствовать - мысль о такой возможности в 1900 г. никому не приходила в голову. Лишь в 30-х гг. оформилось математически точное понятие алгоритма ("способа, который после конечного числа операций дает ответ", см. раздел 3.3). Пока класс всех возможных "способов" не был определен с математической точностью, нельзя было серьезно говорить о доказательстве невозможности общего "способа" для решения какого-либо вида задач.

К концу 40-х гг. вера в адекватность математически точного понятия алгоритма укоренилась уже настолько, что можно было серьезно ставить вопрос об отрицательном решении десятой проблемы Гильберта (и других классических проблем, касающихся существования алгоритмов). Т.е. можно было говорить о строгом доказательстве невозможности алгоритма, который по данному диофантову уравнению определял бы, имеет ли оно решение в целых числах или нет. Гипотезу, что десятая проблема Гильберта алгоритмически неразрешима, первым выдвинул (с достаточным на то основанием) американский математик М.Дэвис в 1949 г. Доказательство этой гипотезы растянулось на 20 лет - последний шаг был сделан только в 1970 г.

М.Дэвис наметил следующий путь доказательства своей гипотезы. Сначала он перешел от решения уравнений в целых числах к решению в натуральных числах (область, более привычная для теории алгоритмов).

Упражнение 4.1. Покажите, что алгоритм, определяющий разрешимость диофантовых уравнений в целых числах, существует, если и только если существует алгоритм, определяющий их разрешимость в натуральных числах. (В своих рассуждениях можете использовать тот факт, что полином x²+y²+z²+t² при всевозможных целых значениях x, y, z, t принимает в качестве значений все натуральные числа. Это известная теорема Лагранжа о том, что каждое натуральное число представимо в виде суммы четырех квадратов, см. например, А.А.Бухштаб [1966]. )

Итак, М.Дэвис предлагал доказывать невозможность алгоритма, определяющего разрешимость диофантовых уравнений в натуральных числах. Каким же образом?

Упражнение 4.2. Пусть P(a, x₁, ..., x_n)=0 - диофантово уравнение, содержащее параметр a. Проверьте, что множество S тех значений a, для которых уравнение разрешимо в натуральных числах, является эффективно перечислимым.

Если бы удалось построить уравнение (с параметром a) такое, что множество S оказалось бы неразрешимым, то цель была бы достигнута. Простейший способ доказать, что S может быть неразрешимым (будучи эффективно перечислимым), - показать, что в качестве S, при подходящем выборе уравнения, может выступать произвольное эффективно перечислимое множество (как известно, среди эффективно перечислимых множеств существуют неразрешимые).

Исходя из таких соображений, М.Дэвис ввел понятие диофантовых представлений. Пусть R(a₁, ..., a_m) - предикат для натуральных чисел. Формулу

(Ex₁)...(Ex_n) P(a₁, ..., a_m, x₁, ..., x_n)=0,

где P - полином с целыми коэффициентами, будем называть диофантовым представлением предиката R, если эта формула истинна для тех и только тех наборов (a₁, ... a_m), для которых истинным является предикат R. Например, предикат "a - четное число" имеет следующее диофантово представление:

(Ex) a-2x=0.

Таким образом, диофантово представление предиката R - это диофантово уравнение с параметрами (a₁, .., a_m ), которое разрешимо (в натуральных числах), если и только если R(a₁, ..., a_m) истинно.

Ясно, что всякий предикат, обладающий диофантовым представлением, эффективно перечислим (упражнение 4.2). М.Дэвис предположил, что для всякого эффективно перечислимого предиката существует диофантово представление. Если это так, то отсюда вытекает алгоритмическая неразрешимость десятой проблемы Гильберта. Возьмем эффективно перечислимое неразрешимое множество S, построим диофантово представление a in S:

(Ex₁)...(Ex_n)P(a, x₁, ..., x_n) = 0.

Тогда невозможен алгоритм, определяющий по числу a, разрешимо ли уравнение P(a, x₁, ..., x_n)=0 в натуральных числах (что и требовалось).

В 1949 г. М.Дэвису удалось сделать только первый шаг в намеченном направлении: он показал, что всякий эффективно перечислимый предикат R(a₁, ..., a_m) можно представить в виде

(Ey)(Az<=y)(Ex₁)...(Ex_n) P(a₁, ..., a_m, y, z, x₁, ..., x_n) = 0.

Избавиться от квантора Az<=y М.Дэвису тогда не удалось.

Следующий успех был достигнут в 1960 г.: М.Дэвис совместно с Х.Патнэмом доказали, что для любого эффективно перечислимого предиката R(a₁, ..., a_m) можно получить представление вида

(Ex₁)...(Ex_n) X(a₁, ..., a_m, x₁, ..., x_n) = 0,

где выражение X получено из символов a₁, ..., a_m, x₁, ..., x_n и натуральных чисел применением операций сложения, вычитания, умножения и возведения в степень (например, x^2y+z - yz + 3 = 0). Правда, доказательство Дэвиса-Патнэма содержало пробел (они воспользовались не доказанной до сих пор гипотезой о существовании произвольно длинных арифметических прогрессий, состоящих только из простых чисел). Восполнить этот пробел удалось Дж.Робинсон в 1961 г. Уравнения вида X(a₁, ..., a_m, x₁, ..., x_n) = 0 были названы показательно-диофантовыми уравнениями. Из теоремы Дэвиса-Патнэма-Робинсон вытекала невозможность алгоритма, определяющего, разрешимо ли данное показательно-диофантово уравнение в натуральных числах. Это был крупный успех, однако до полной победы оставалось еще почти 10 лет.

Более того, даже после 1961 г. не все еще поверили, что дело удастся намеченным путем довести до конца (показав, что всякий эффективно перечислимый предикат обладает диофантовым представлением). Если взять предикаты "a - простое число" и "a - степень числа 2" и вообразить, что построены их диофантовы представления:

"a - простое число" <-> (Ex₁)...(Ex_n) P(a, x₁, ..., x_n) = 0,

"a - степень двойки" <-> (Ey₁)...(Ey_k) Q(a, y₁, ..., y_k) = 0,

то получится, что уравнение P=0 разрешимо, если и только если a - простое число, а уравнение Q=0 - если и только если a имеет вид 2^m. Такая возможность сильно противоречила сложившейся теоретико-числовой интуиции (согласно этой интуиции, простые числа и экспонента настолько далеко отстоят от полиномов, что между ними никогда нельзя будет установить простую связь). И тем не менее в 1970 г. советскому математику Юрию Владимировичу Матиясевичу (см. Ю.В.Матиясевич [1970]) удалось сделать последний и решающий шаг - получить диофантово представление экспоненты:

a=b^c <-> (Ex₁)...(Ex_n) P(a, b ,c ,x₁, ..., x_n) = 0.

С помощью этого представления легко исключить операцию возведения в степень из представлений Дэвиса-Патнэма-Робинсон и таким образом получить диофантово представление для любого эффективно перечислимого предиката. Тем самым в 1970 г. алгоритмическая неразрешимость десятой проблемы Гильберта была доказана полностью.

Алгоритмическая неразрешимость объясняет отмеченные выше трудности с решением диофантовых уравнений высоких степеней. Общего метода, определяющего, разрешимо ли любое данное диофантово уравнение, не существует. Поэтому всякий метод определения разрешимости неизбежно оказывается частным - применимым только к уравнениям специального вида. Одновременно такая принципиальная ограниченность всякого метода обеспечивает неограниченный простор для творчества в данной области математики.

В последующих разделах излагается доказательство существования диофантовых представлений для любого эффективно перечислимого предиката.

Упражнение 4.3. Покажите, что проблема разрешимости произвольного диофантова уравнения может быть сведена к проблеме разрешимости: а) системы диофантовых уравнений 2-й степени или б) диофантова уравнения 4-й степени. Таким образом, проблема разрешимости систем уравнений 2-й степени и уравнений 4-й степени оказывается уже алгоритмически неразрешимой. Не случайно поэтому, что до сих пор не найдены сколько-нибудь общие методы решения диофантовых уравнений 4-й степени.

4.2. Начало и план доказательства

Диофантово представление предиката является по существу формулой специального вида в языке EA (нужно только в уравнении P=0 перенести в правую сторону члены с отрицательными коэффициентами). Вспомним, что, доказывая представимость в EA любой вычислимой функции, мы уже получили некоторые специальные формулы EA, представляющие предикаты вида f(a₁, ..., a_m) = b, где f - произвольная вычислимая функция.

Упражнение 4.4. Проверьте по тексту раздела 3.3, что эти формулы были образованы с помощью только следующих средств:

а) элементарных формул вида s=t, s<t, где s, t - термы EA (полиномы с целыми положительными коэффициентами),

б) конъюнкции и дизъюнкции,

в) квантора существования,

г) ограниченного квантора всеобщности, а именно квантора Ax<=U, где U - линейная функция вида b₁y +b₂y₂+...+b_ky_k+c с натуральными коэффициентами b₁, b₂, ..., b_k, c.

В своей работе 1949 г. М.Дэвис также исходил из подобного результата. Важнейшей (с точки зрения наших целей) особенностью представляющих формул является отсутствие в них символов отрицания и неограниченных кванторов всеобщности. "Недостатком" отрицаний и кванторов всеобщности является то, что они выводят за пределы класса эффективно перечислимых предикатов (если R - эффективно перечислимый предикат, то ~R уже не обязательно таков, аналогично - в случае перехода от R(x,y) к (Ay)R(x,y)). Формулы, содержащие такие средства, в общем случае невозможно перевести в диофантовы представления.

Итак, мы начинаем с эффективно перечислимого предиката R(a₁, ..., a_m). Построим машину Тьюринга M(R), которая печатает на своей ленте все возможные наборы чисел a₁, ..., a_m, удовлетворяющие предикату R(a₁, ..., a_m). Тогда следующая функция вычислима:

f(a₁, ..., a_m, t) = 1, если после t шагов работы машины M(R) набор чисел a₁, ..., a_m на ленте уже напечатан,

f(a₁, ..., a_m, t) = 0, иначе.

По теореме о представимости можно построить формулу EA, которая представляет функцию f и содержит только средства, перечисленные в пп. а)-г) упражнения 4.4. Если F(a₁, ..., a_m, t ,w) - эта формула (w соответствует значению функции), то

R(a₁, ..., a_m) <-> (Et) F(a₁, ..., a_m, t, 1).

Тем самым доказано, что предикат R равносилен некоторой формуле, построенной только с помощью средств, перечисленных в а)-г). Теперь мы должны научиться преобразовывать такие формулы в диофантовы представления. Начнем "изнутри" - с элементарных формул. Формула вида s=t уже является диофантовым представлением (без кванторов). Формулу вида s<t можно заменить формулой (Ex)(s+x+1=t), которая уже является диофантовым представлением. Теперь можно переходить к средствам б)-г), с помощью которых строятся более сложные формулы.

Упражнение 4.5. Покажите, что конъюнкцию и дизъюнкцию двух диофантовых представлений (E)P=0, (E)Q=0 можно преобразовать в диофантово представление.

Таким образом, если в нашем процессе преобразования, начинающемся с элементарных формул, встречаются символы &, V, мы знаем, как от них освободиться. Если встретился символ E, он может остаться на своем месте (если (E)P=0 - диофантово представление, то (EE)P=0 - также). Но что делать, если встретился квантор Az<=t ? Пусть то, что находилось за ним, мы уже привели к виду диофантова представления

(Az<=t)(Ex₁)...(Ex_n) P(b₁, ..., b_k, y, x₁, ..., x_n) = 0 (1)

(напомним, что t - линейная функция с натуральными коэффициентами от b₁, ..., b_k). Мы хотим заменить (1) диофантовым представлением вида

(Ey₁)...(Ey_s)Q(b₁, ..., b_k, y, ..., y_s) = 0, (2)

но как это сделать?

Оказывается, что это очень сложная задача: преобразовать формулу вида (1) в формулу вида (2). Будем называть ее задачей устранения ограниченного квантора всеобщности (короче: устранения A<=). Решив эту задачу, мы тем самым решим до конца задачу преобразования формул, образованных с помощью средств а)-г), в диофантовы представления, т.е. одновременно докажем существование представлений для любых эффективно перечислимых предикатов.

Итак, решаем задачу устранения A<=. План наших действий:

1) Подробно исследовать свойства решений уравнения x²-(a²-1)y²=1 (a>1). Оказывается, это уравнение имеет в натуральных числах бесконечно много решений. Если n-е решение обозначить через (x_n(a), y_n(a)), то x_n(a) и y_n(a) растут экспоненциально по n. Этим и обусловлен наш интерес к данному уравнению.

2) Опираясь на полученную информацию, построить диофантово представление предиката

R(a, x ,y, n) <-> x=x_n(a) & y=y_n(a),

т.е. предиката, который при фиксированном a требует от x и y экспоненциального роста по n.

3) Используя диофантово представление предиката R, получить диофантово представление экспоненты, т.е. предиката x=y^z & v>=3.

4) Получить диофантовы представления для числа сочетаний и факториала (т.е. для предикатов x=C_y^z и x=y!).

5) Используя все полученные диофантовы представления, научиться устранять A<=.

Задачи 1), 2) были решены Ю.В.Матиясевичем, задачи 3), 4) - Дж.Робинсон, задача 5) - совместно М.Дэвисом, Х.Патнэмом и Дж.Робинсон.

Чтобы сделать наши рассуждения по возможности наглядными, воспользуемся языком сравнений. Сравнение - это нечто вроде равенства, только не точное равенство, а равенство с точностью до слагаемого, кратного модулю (по которому рассматривается сравнение). Например, число 18 сравнимо с 78 по модулю 10:

18 = 78 mod 10,

поскольку 78=18+6*10. Число сравнимо с нулем по модулю m, если и только если оно делится на m: x = 0 mod m означает, что x=0+k*m для некоторого k.

Упражнение 4.6. Докажите следующие свойства сравнений (позволяющие обращаться с ними как с обычными равенствами):

a = a mod m,

a = b mod m -> b = a mod m,

a = b mod m & b = c mod m -> a = c mod m,

a = b mod m & a₁ = b₁ mod m -> a+a₁ = b+b₁ mod m,

a = b mod m & a₁ = b₁ mod m -> a*a₁ = b*b₁ mod m,

a*c = b*c mod m -> a = b mod m, если c взаимно просто с m,

a*c = b*c mоd (c*m) -> a = b mod m, если c взаимно просто с m.

4.3. Исследование уравнения Ферма

Уравнение x²-Dy² =1 (где D>0) играет центральную роль в теории диофантовых уравнений второй степени с двумя неизвестными. Если коэффициент D является полным квадратом (D=k²), то решение уравнения сводится к системам линейных уравнений:

x² - k²y² = (x - ky) (x + ky) = 1,

x-ky=1 & x+ky=1 -> x=1 & y=0,

x-ky=-1 & x+ky=-1 -> x=-1 & y=0.

Таким образом, получаются только два решения.

Значительно более интересен случай, когда D не является полным квадратом. Совершенно неожиданно в этом случае уравнение x² - Dy² = 1 всегда имеет бесконечно много решений в натуральных числах! Это знал еще П.Ферма в XVII в., но первое строгое доказательство было дано только Ж.Лагранжем (XVIII в.). Простейшим для анализа уравнение Ферма оказывается при D=a²-1:

x² - (a² - 1)y² = 1.

Два его решения можно угадать (проверьте): x=1 & y=0, x=a & y=1. Остальные решения (в натуральных числах) получаются с помощью следующего остроумного рассуждения. Возьмем выражение (a+sqrt(a²-1))ⁿ и разложим его по формуле бинома Ньютона. В результате часть членов будут целыми числами, другая же часть будет содержать множитель sqrt(a²-1). Например, для n=2

(a+sqrt(a²-1)) ² = a² + 2a sqrt(a²-1) + (a²-1).

Сводя вместе члены в каждой части, получаем

(a+sqrt(a²-1))ⁿ = x_n(a) + y_n(a) sqrt(a²-1),

где x_n(a), y_n(a) - натуральные числа (например, x₂(a)=2a² -1 & y₂(a)=2a). Аналогично

(a-sqrt(a²-1))ⁿ = x_n(a) - y_n(a) sqrt(a²-1)

(с теми же x_n, y_n - проверьте, что это действительно так!). Перемножая оба последних равенства, получаем

(a²-a²+1)ⁿ = x_n² - (a²-1)y_n² ,

x_n² - (a²-1)y_n² = 1.

Таким образом, при любом n>=0 пара чисел x=x_n(a), y=y_n(a) является решением уравнения x² - (a² -1)y² = 1. При n=0, 1 получаются уже известные нам тривиальные решения (1,0), (a,1), при n=2 - новое решение (2a²-1, 2a).

Из нашего определения чисел x_n(a), y_n(a) легко получить рекуррентные соотношения, позволяющие вычислить x_m+n, y_m+n, если уже известны x_m, y_m, x_n, y_n (m, n >= 0):

x_m+n(a) = x_m(a) x_n(a) + y_m(a) y_n(a)(a²-1),

y_m+n(a) = x_m(a) y_n(a) + y_m(a) x_n(a).

В частности, при m=1:

x_n+1(a) = a x_n(a) + (a²-1) y_n(a),

y_n+1(a) = x_n(a) + a y_n(a).

Упражнение 4.7. Докажите эти соотношения. Докажите также, что x_n(a), y_n(a) возрастают по n (т.е. что действительно получается бесконечно много решений уравнения x²-(a²-1)y²=1).

Оказывается, что последовательность {(x_n, y_n) | n>=0} исчерпывает все решения нашего уравнения.

ЛЕММА 1. При a>1

x²-(a²-1)y=1 <-> (En)(x=x_n(a) & y=y_n(a)).

Д о к а з а т е л ь с т в о. 1) Влево. Это мы уже знаем.

2) Вправо. Пусть числа x,y удовлетворяют уравнению. Если x<=1, то x=1 и y=0, т.е. x=x₀(a) и y=y₀(a).

Пусть теперь x>1. Тогда y>0. Если мы рассчитываем показать, что x=x_n(a) & y=y_n(a) для некоторого n>0, то x,y должны выражаться через x_n-1, y_n-1 в соответствии с известными нам рекуррентными соотношениями, т.е. должно существовать решение (u,v) нашего уравнения такое, что

x = au + (a²-1)v,

y = u+av.

Решая эту систему относительно u, v, получаем

u = ax - (a²-1)y,

v = -x + ay. (3)

Таким образом, u, v - целые числа.

Упражнение 4.8. Проверьте, что u²-(a²-1)v²=1 (т.е. что (u, v) является решением уравнения), а также, что 0<u<x и v>=0.

Итак, если пара (x, y) является решением уравнения x²-(a²-1)y²=1, то числа x, y выражаются по формулам (3) через другое решение (u, v) этого уравнения, такое, что u<x. Если оказывается, что также u>1, то пара (u, v) выражается аналогично через решение (u', v') такое, что u'<u. "Спуск" может удаваться только конечное число (скажем, n) раз, и после этого будет достигнута ситуация, когда u<=1, т.е. u=x₀(a) и v=y₀(a) и, таким образом, x=x_n(a) & y=y_n(a).

Лемма 1 доказана.

Все это очень красиво, но почему уравнением Ферма заинтересовались, решая десятую проблему Гильберта? Заинтересовались им при поиске диофантова представления экспоненты. Найти такое представление, скажем, для предиката

Q(b) <-> (En)b=2ⁿ

- это значит найти диофантово уравнение P(b, z₁, ..., z_k)=0 с параметром b, такое, что решение (z₁, ..., z_k ) существует, если и только если b является степенью числа 2. Таким образом, диофантово условие P=0 должно "заставить" параметр b расти со скоростью экспоненты. Уравнение Ферма дает как раз нечто подобное.

ЛЕММА 2. При a>1 и n>=0

aⁿ <= x_n(a) <= (a+sqrt(a²-1))ⁿ.

Д о к а з а т е л ь с т в о.

x_n(a) - y_n(a)sqrt(a²-1) = (a+sqrt(a²-1))ⁿ = aⁿ + C_n¹ a^n-1 sqrt(a²-1) + ...,

что и требовалось доказать.

Таким образом, x_n(a) растет по n со скоростью экспоненты (хотя и не следует точно ни одной из экспонент вида (a+a₁)ⁿ), и это достигнуто через диофантово условие на x

(Ey)(x² - (a²-1) y² =1).

Именно поэтому уравнение Ферма интересно как отправная точка в поисках диофантова представления экспоненты. (Эти соображения принадлежат Дж.Робинсон и относятся еще к 1952 г.)

По идее Ю.В.Матиясевича, теперь мы должны провести исследование остатков, получающихся при взаимном делении чисел x_n(a), y_n(a).

Сначала, пусть n фиксировано, n>0 (при n=0 мы имели бы x₀(a)=1, и ничего интересного не получается). Будем изучать остатки от деления x_N(a) на x_n(a), где N=0, 1, 2, ... Для этого рассмотрим по модулю x_n(a) известные рекуррентные соотношения для x_m+n, y_m+n (по модулю x_n - это значит, что мы будем пренебрегать слагаемыми, кратными x_n ):

x_m+n(a) = x_m(a) x_n(a) + y_m(a) y_n(a)(a -1) = (a²-1)y_my_n,

y_m+n(a) = x_m(a) y_n(a) + y_m(a) x_n(a) = x_my_n.

Подставляя m+n вместо m, получаем

x_m+2n = (a²-1)y_m+n y_n = (a²-1)x_my_n²,

y_m+2n = x_m+ny_n = (a²-1)y_my_n² .

Заметим теперь, что x_n²-(a²-1)y_n² =1, т.е. по модулю x_n

(a²-1)y_n ² = x _n ² - 1 = -1.

Подставляя вместо (a²-1)y_n число -1, получаем

x_m+2n = - x_m, (4)

y_m+2n = - y_m.

Подставляя здесь m+2n вместо m, имеем

x_m+4n = - x_m+2n = x_m,

y_m+4n = - y_m+2n = y_m.

Таким образом, остатки от деления x (a) на x (a) меняются по N с периодом 4n. Поэтому достаточно изучить поведение остатков при N=0, 1, 2, ..., 4n-1.

Согласно (4)

x₀ = x₀, x₁ = x₁, ..., x_2n-1 = x_2n-1,

x_2n = - x₀, x_2n+1 = - x₁, ..., x_4n-1 = - x_2n-1.

Аналогично для y_N(a). Дело, однако, еще не доведено до конца, поскольку числа x_n+1 , ..., x_2n-1, участвующие в характеристике остатков, все еще больше делителя x_n. Чтобы довести дело до конца, рассмотрим соотношения, выражающие x_2n, y_2n через x_2n-m, y_2n-m, x_m, y_m :

x_2n = x_2n-m x_m + (a²-1)y_2n-m y_m,

y_2n = x_2n-m y_m + y_2n-m x_m.

Решая эту систему относительно x_2n-m, y_2n-m, получаем

x_2n-m = x_2n x_m - (a²-1)y_2n y_m,

y_2n-m = y_2n x_-m - x_2n y_m.

Учитывая, что x_2n = - x₀ = -1, y_2n = - y₀ = 0 (по модулю x_n), имеем

x_2n--m = - x_m,

y_2n-m = y_2m.

Теперь нашу характеристику остатков от деления x_N(a) на x_n(a) (внутри периода 4n) можно довести до конца:

x ₀ = x ₀, x ₁ = x ₁, ..., x _n-1 = x _n-1,

x_n = - x_n, x_n+1 = - x_n-1, ..., x_2n-1 = - x₁,

x_2n = - x₀, x_2n+1 = - x₁, ..., x_3n-1 = - x_n-1,

x_3n = x_n, x_3n+1 = x_n-1, ..., x_4n-1 = x₁.

Ясно, что вместо x_n и -x_n здесь можно было написать просто нуль, но это нарушило бы симметрию.)

Имея такую характеристику, можно доказать следующую лемму Ю.В.Матиясевича.

ЛЕММА 3. Пусть a>=3, n>=1, 0<m<n. Тогда для всех N

x_N(a) = x_m(a) mod x_n(a) <-> (N = +m mod 4n)V(N = -m mod 4n).

Д о к а з а т е л ь с т в о. 1) Влево. Если N=4kn+m или N=4kn-m, то x_N=x_m mod x_n вытекает непосредственно из полученной выше характеристики.

2) Вправо. Пусть известно, что x_N=x_m mod x_n, где 0<m<n. Разделим число N на 4n и найдем остаток: N=4kn+m', где 0<=m'<4n. Если 0<m'<n, то из нашей характеристики следует, что m'=m и N=4kn+m, что и требовалось. Если 3n<m', то из характеристики следует, что m'=4n-m и N=4(k+1)n-m.

Упражнение 4.9. Покажите, что третий случай m'=0 или n<=m'<=3n невозможен (учтите, что при a>2: i<n -> x_i(a) < x_n(a)/2).

Лемма 3 доказана.

Теперь мы должны провести аналогичное исследование остатков от деления y_N(a) на y_n(a) (n>=1 фиксировано, N=0, 1, 2, ...).

Упражнение 4.10. Проведите это исследование самостоятельно. Период получится длиной в 2n, а внутри периода остатки будут вести себя таким образом:

y₀ = y₀, y₁ = y₁, ..., y_n-1 = y_n-1,

y_n = - y_n, y_n+1 = - y_n-1, ..., y_2n-1 = - y₁.

Из всего этого нас интересует только условие, при котором y_N(a) делится на y_n(a) (еще одна лемма Ю.В.Матиясевича):

ЛЕММА 4. Пусть a>=2, n>=1. Тогда y_N(a) делится на y_n(a), сли и только если N делится на n.

Д о к а з а т е л ь с т в о вытекает непосредственно из полученной характеристики.

Еще одна важная лемма Ю.В.Матиясевича дает условие, при котором y_N(a) делится не только на y_n(a), но и на y_n²(a).

ЛЕММА 5. Пусть a>=2. Тогда y_N(a) делится на y_n(a), если и только если N делится на ny_n(a).

Д о к а з а т е л ь с т в о. Легко проверить (индукцией по k), что по модулю y_n²

x_kn = x_n^k,

y_kn = kx_n^k-1y_n.

1) Импликация вправо. Если y_N делится на y_n² , то по лемме 4: N = kn. Если y_kn делится на y_n² , то число kx_n^k-1y_n также должно делиться на y_n² , т.е. kx_n^k-1 должно делиться на y_N. Поскольку x_n²-(a²-1)y_n² =1, то x_n не может иметь общих делителей с y_n, поэтому на y_n должно делиться само число k. Так как N=kn, то теперь ny_n делит N, что и требовалось.

2) Влево. Если ny_n делит N, то N=kn, где y_n делит k. Поэтому y_n² делит kx_n^k-1y_n, т.е. y_n² делит и y_kn = y_N , что и требовалось.

Лемма 5 доказана.

В дальнейшем нам потребуются еще три леммы. Первая из них принадлежит Дж.Робинсон, остальные две тривиальны.

ЛЕММА 6. При a>=2 и n>=0

x_n(a) = 1 mod(a-1),

y_n(a) = n mod(a-1).

ЛЕММА 7. При a,a'>=2 и b>=1, если a = a' mod b, для всех n:

x_n(a) <-> x_n(a') mod b,

y_n(a) <-> y_n(a') mod b.

ЛЕММА 8. При a>=2 и k>=0 по модулю 2

x_2k = 1, x_2k+1 = a, y_2k = 0, y_2k = 1.

Упражнение 4.11. Докажите эти леммы с помощью индукции.

4.4. Диофантово представление последовательности решений уравнения Ферма

Сейчас мы должны построить диофантово представление для предиката

Q(a, x, y, n) <-> a>=3 & x=x_n(a) & y=y_n(a).

Какие "диофантовы условия" следует наложить на числа x, y, чтобы "заставить" их равняться x_n(a) и y_n(a)? Прежде всего, разумеется, условие

E₁: x² - (a²-1) y² = 1.

Отсюда следует, что существует ni такое, что x=x_ni(a) и y=y_ni(a). Само значение ni мы пока не знаем. Но какие условия следует наложить на x, y, чтобы оказалось, что ni=n? Из леммы 6 мы знаем, что y = n mod(a-1), поэтому можно было бы потребовать y =n mod(a-1), тогда отсюда следовало бы ni = n mod(a-1). К сожалению, если n>=a-1, то отсюда еще нельзя будет вывести, что ni=n.

Чтобы обойти эту трудность, приходится идти в обход в самом прямом смысле. Введем новое уравнение Ферма со свободным параметром a' и обозначим некоторое его решение через (x', y'):

E₂: x'² - (a'²-1) y'² = 1.

И теперь потребуем не y = n mod(a-1), а

E₃: y' = n mod(a'-1)

(в расчете, что a'-1 можно будет сделать больше n). Поскольку для некоторого mi имеет место x' = x_mi(a') & y' = y_mi(a'), то по лемме 6 y' = mi mod(a'-1) и поэтому

mi = n mod(a'-1). (1)

Но так как мы "ушли в сторону" от исходного уравнения, от успеха пользы никакой не будет, если мы не сумеем найти "обратный путь" - нужно подходящим образом связать решение (x', y') с интересующим нас решением (x, y). Введем для этого новый модуль сравнения, обозначим его через X и потребуем, чтобы выполнялось условие

E₄: a' = a mod X & x' = x mod X.

Тогда новые числа a', x' не будут "слишком сильно отличаться" от старых a, x, причем, изменяя X, мы можем надеяться добиться максимально тесной связи. Теперь по лемме 7 a' = a mod X дает

x = x_ni(a) = x_ni(a') mod X,

x' = x_mi(a') = x_mi(a) mod X.

По условию x' = x mod X* отсюда получается

x_mi(a) = x_ni(a) mod X. (2)

Чтобы создать условия для применения леммы 3 (она здесь сама напрашивается), модуль X следует сделать решением уравнения Ферма с параметром a. Введем поэтому еще одно число Y и условие

E₄: X² - (a²-1) Y² = 1.

Отсюда X=x_N(a) и Y=y_N(a) для некоторого N и (2) принимает вид

x_mi(a) = x_ni(a) mod x_N(a).

При a>=3 здесь можно было бы применить лемму 3, однако надо обеспечить еще 0<ni<N, поэтому введем условие

E₆: 0<x<X

(поскольку 0<x_ni(a)=x<X=x_N(a) и x_i(a) возрастает по i). Наконец, по лемме 3

mi = +-ni mod 4N. (3)

Сравним это с (1):

mi = n mod(a'-1).

Наша конечная цель - обеспечить ni=n, т.е. оба последних сравнения нужно "свести вместе" к одному модулю. Для этого нужно найти достаточно большой общий делитель чисел 4N и a'-1. Числом a'-1 мы можем распоряжаться относительно свободно, но как получить делитель числа N, которое само нам неизвестно? Здесь помощь оказывает лемма 5: y_ni²(a) делит y_N(a), если и только если ni*y_ni(a) делит N. Короче: y² делит Y, если и только если ni*y делит N. Поэтому, если мы потребуем

E₇: y делит Y,

то 4y будет делителем 4N (мы опускаем неизвестное число ni, которое не сумели бы сделать делителем модуля a'-1). Теперь нужно потребовать еще

E₈: 4y делит a'-1

(будем надеяться, что это требование не будет противоречить остальным условиям, наложенным на a'). Тогда (1) вместе с (3) дает

mi = +-ni mod 4y & mi = n mod 4y

и отсюда

n = +-ni mod 4y.

Другими словами, n+ni или n-ni делится на 4y. Поскольку y=y_ni(a) возрастает по ni, то y>=ni, поэтому мы можем смело потребовать также

E₉: n<=y

(напомним, что мы добиваемся равенства ni=n, т.е. желательно "наделить" n свойствами, присущими ni). Рассмотрим теперь отдельно две упомянутые возможности:

1) n+ni делится на 4y. Поскольку n+ni<=2y, то это возможно только при n=ni=0, что и требовалось.

2) n-ni делится на 4y. Поскольку |n-ni|<=y, то это возможно только при n=ni, что и требовалось.

Вспомнив, что x=x_ni(a) и y=y_ni(a), мы можем утверждать теперь, что из условия

a>=3 & E a'x'y'XY (E₁&E₂&E₃&E₄&E₅&E₆&E₇&E₈&E₉) (4)

вытекает, что x=x_n(a) и y=y_n(a), т.е. Q(a, x, y, n).

Упражнение 4.12. Покажите, как (4) можно преобразовать в диофантово представление вида (E)P=0. Оцените число кванторов E, степень полинома P и сумму модулей его коэффициентов.

Решение нашей задачи будет завершено лишь, если удастся показать, что из Q(a, x, y, n) , т.е. из a>=3 & x=x_n(a) & y=y_n(a) также следует условие (4). (В частности, только тогда и будет установлена взаимная непротиворечивость требований E_i.)

Итак, зная, что а>=3 & x=x_n(a) & y=y_n(a), мы должны найти числа a', x' ,y' ,X, Y такие, что имеют место E_i для всех i=1, 2, ..., 9. Отметим сразу, что выполнение E₁ уже обеспечено леммой 1, а выполнение E₉ - тем обстоятельством, что y_n(a)>=n для всех n.

Числа X, Y (решение того же уравнения, что x, y) определим следующим образом: пусть N - любое число, делящееся на ny_n(a)=ny; возьмем X=x_N(a) и Y=y_N(a). Этим будет обеспечено условие E₅, а по лемме 5 тогда y делит Y, что обеспечивает E₇.

Остается указать число a', определяющее вспомогательное уравнение, и его решение x', y'. При этом мы должны выполнить следующие условия:

E₂: x'² - (a'²-1) y'² = 1,

E₃: y' = n mod(a'-1),

E₄: a' = a mod X & x' = x mod X,

E₈: a' = 1 mod 4y.

Случай n=0 (тогда x=1, y=0) здесь приходится разбирать отдельно. Тогда E₈ требует a'=1, затем E₃ требует y'=0, E₂ - x'=1, наконец, E₄ требует a = 1 mod X. Только последнее требование грозит "нарушить гармонию", но, к счастью, из-за y=0 мы вынуждены были выбрать N=0, поэтому X=1!

Пусть теперь n>0. Тогда y>0. Руководствуясь E₄ и E₇ , сначала укажем a'. Если бы модули X, 4y оказались взаимно простыми, существование числа a' вытекало бы из китайской теоремы об остатках (см. раздел 3.3). Убедимся, что X и 4y действительно взаимно просты. Во-первых, X должно быть нечетным числом. Этого можно добиться, если взять число N четным (лемма 8). (Напомним, что до сих пор мы требовали от N лишь делимость на ny.) Во-вторых, y и X не имеют общих делителей, поскольку y² делит Y, а X²-(a²-1)Y²=1. Таким образом, существование числа a', удовлетворяющего условиям E₄ и E₈, обеспечено (причем, очевидно, можно выбрать a'>1).

Остается определить x', y'. Возьмем x'=x_n(a') и y'=y_n(a'), тогда автоматически выполняется E₂, а по лемме 6 - и E₃. Наконец, так как x=x_n(a) и a'=a mod X, то по лемме x'=x mod X, т.е. обеспечена вторая половина условия E₄.

Это все, что требовалось: из Q(a, x, y, n) мы вывели (4).