Докажите, что целые неотрицательные числа $x$, $y$
удовлетворяют уравнению
$$
x^2-mxy+y^2=1
$$
(где $m$ — данное целое число, большее единицы) тогда и только тогда, когда $x$ и $y$ —
соседние члены последовательности
$\phi_0=0$, $\phi_1=1$, $\phi_2=m$, $\phi_3=m^2-1$, $\phi_4=m^3-2m$,
$\phi_5=m^4-3m^2+1$, $\ldots$, в которой
$\phi_{k+1}=m\phi_k-\phi_{k-1}$ для всех $k\ge 1$.
Например, все решения уравнения $$x^2-3xy+y^2=1\tag1$$ в целых числах
$0\le x\lt y$ — это пары $$(0,1);~(1,3);~(3,8);~(8,21);~\ldots\tag2$$
соседних членов последовательности 0, 1, 3, 8, 21, 55, $\ldots$ определяемой условиями
$\phi_0=0$, $\phi_1=1$, $\phi_{k+1}=3\phi_k-\phi_{k-1}$
для всех $k\ge 1$.
(Этот красивый факт был использован в работе Ю. Матиясевича,
посвящённой 10-й проблеме Гильберта, о которой рассказывалось в предыдущем номере «Кванта».)
Решим эту задачу для $m=3$ (для других $m\gt1$ решение совершенно
аналогично). Мы должны доказать, что, во-первых, все пары чисел (2)
удовлетворяют уравнению (1) и, во-вторых, никакие другие пары
неотрицательных целых чисел этому уравнению не удовлетворяют. (Заметим, что эту вторую и более трудную часть решения многие читатели, приславшие письма,
упустили из виду.)
В последовательности (2) за каждой парой $(x,y)$ следует пара
$(x_1,y_1)$, которую можно получить из $(x,y)$ с помощью такого
преобразования:
$$
x_1=y,\quad y_1=3y-x.\tag3
$$
Это преобразование $(x,y)\to(y,3y-x)$ мы обозначим буквой $T$. Нетрудно
проверить, что если пара $(x,y)$ удовлетворяет уравнению (1), то пара
$(x_1,y_1=T(x,y)$ ему тоже удовлетворяет:
$$
x_1^2-3x_1y_1+y_1^2=y^2-3y(3y-x)+(3y-x)^2=y^2-3xy+x^2.\tag4
$$
Отсюда сразу видно, что все пары (2) удовлетворяют уравнению (1): ведь пара
$(0,1)$ ему удовлетворяет, а все остальные получаются из неё с помощью
конечного числа преобразований $T$.
Докажем теперь, что других решений $(x,y)$ в целых числах, подчинённых
условиям $0\le x\lt y$, у уравнения (1) нет. Пусть $(x_1,y_1)$ — одно из таких решений. Найдём такую пару $(x,y)$, из которой эти $x_1$ и $y_1$
получаются по формулам (3), — для этого достаточно выразить $x$ и $y$ через
$x_1$ и $y_1$:
$$
x=3x_1-y_1,\quad y=x_1.\tag5
$$
Такой переход от $(x_1,y_1)$ к $(x,y)$ — преобразование,
обратное к $T$ — мы будем обозначать через $T^{-1}$.
Из равенств (4) следует, что если пара $(x_1,y_1)$ удовлетворяет уравнению
(1), то пара $(x,y)=T^{-1}(x_1,y_1)$ ему также удовлетворяет. Покажем, что если, кроме того, $0\lt x_1\lt y_1$, то $$
0\le x\lt y.\tag6
$$
Представим равенство $x_1^2-3x_1y_1+y_1^2=1$ следующими двумя способами:
$$
\begin{gather*}
x_1^2+y_1(y_1-3x_1)=1,\tag7\\
x_1(x_1-y_1)+y_1(y_1-2x_1)=1.\tag8
\end{gather*}
$$
Из равенства (7) сразу следует ($x_1$ и $y_1$ положительны!), что $-x=y_1-3x_1\le0$, причём если $y_1-3x_1=0$, то $x_1=1$ и $y_1=3$. Из равенства (8) в свою очередь следует, что $y-x=y_1-2x_1\gt0$ (ведь $x_1-y_1$
отрицательно). Неравенства (6) доказаны. Заметим, что их можно переписать и так:
$$
0\le x\lt x_1,\tag9
$$
поскольку $x_1=y$. Итак, любое решение $(x_1,y_1)$, $0\lt x_1\lt y_1$, после
преобразования $T^{-1}$ переходит в решение $(x,y)$, для которого $0\le x\lt
y$. Если при этом $x\gt0$, то мы можем применить $T^{-1}$ ещё один или несколько раз, получая новые (меньшие по величине) решения. Действительно,
как показывает (9), величина целого числа х при каждом преобразовании
уменьшается. Поэтому через некоторое конечное число шагов мы должны будем
остановиться, а остановиться мы можем лишь тогда, когда получим решение
$(x,y)$, у которого $x=0$ и, следовательно, $y=1$. Таким образом, мы доказали, что из каждого решения $(x_1,y_1)$ за конечное число
преобразований $T^{-1}$ получается решение $(0,1)$. Отсюда следует, что каждое решение получится из $(0,1)$ за конечное число преобразований $T$
(т. е. что никаких других, отличных от (2), решений нет). Задача полностью
решена.
Более наглядно это решение можно представить так. Будем
изображать пару чисел $(x,y)$, как обычно, точкой плоскости. Тогда уравнение
$x^2-3xy+y^2=1$ задаёт на плоскости кривую, называемую гилерболой.
(На обложке нарисовано целое семейство гипербол, задаваемых уравнениями
$x^2-3xy+y^2=c$ с разными значениями параметра $c$, а интересующая нас —
жёлтого цвета.) Решить это уравнение в целых числах — значит указать все точки с целочисленными координатами, лежащие на гиперболе. Одну такую точку
указать легко: это — чёрная точка с координатами $(0,1)$. Все остальные (в
пределах угла $0\le x\lt y$), как мы доказали, получаются из неё последовательным применением преобразования $T\colon(x,y)\to(y,3y-x)$. Это преобразование $T$ плоскости обладает такими свойствами:
Переводит каждую прямую на плоскости снова в прямую (такие
преобразования называются линейными).
Переводит любую целочисленную точку снова в целочисленную.
Переводит в себя каждую гиперболу $x^2-3xy+y^2=c\ne0$ (и каждый из четырёх лучей с вершиной $(0,0)$, на которые распадается множество
$x^2-3xy+y^2=0$); каждая точка под действием $T$ «переезжает» по своей
гиперболе (или лучу) в своё новое положение; точка $(0,0)$ остаётся на месте. Такое преобразование называется гиперболическим поворотом с центром $(0,0)$ по аналогии с обычным «круговым» поворотом.
Теми же свойствами обладает и обратное преобразование
$T^{-1}$. Упомянем ещё одно интересное свойство этих преобразований:
Площадь любой фигуры при преобразовании не меняется. (Белые
четырёхугольники, расположенные в верхней полуплоскости, переходят друг в друга при преобразованиях $T$ и $T^{-1}$.)
Совершенно аналогично обстоит дело и при $m\gt3$. При $m=2$
все наши рассуждения также проходят без изменения, но геометрическая
интерпретация несколько меняется. Вместо свойства 3) соответствующее
преобразование $T\colon(x,y)\to(y,2y-x)$ обладает таким $3')$: оно переводит
каждую прямую $y-x=c$ в себя; каждая точка «сдвигается» по своей прямой (при
$c\ne0$), а все точки, лежащие на прямой $y-x=0$, просто остаются
неподвижными. (Такое преобразование называется сдвигом.) Проверьте
это и начертите соответствующую картинку сами.
Любопытно, что и для случая $m=1$, т. е. для уравнения
$x^2-xy+y^2=1$ (оно определяет на плоскости эллипс), можно выписать аналогичное преобразование
$T\colon(x,y)\to(y,y-x)$, которое переводит это уравнение и вообще каждый
эллипс $x^2-xy+y^2=c$ в себя. Это преобразование называется
эллиптическим поворотом. Оно так же, как и при $m\gt1$, переводит
все целочисленные решения уравнения друг в друга, но в данном случае решений
конечное количество (это не удивительно: ведь эллипс, в отличие от гипербол
и прямых, — фигура ограниченная), а именно шесть, и вместо схемы
$$
(0,1)\stackrel T\to(1,3)\stackrel T\to(3,8)\stackrel T\to(8,21)
\stackrel T\to\ldots,
$$
которую можно было бы нарисовать для уравнения (1), теперь получается такая:
$$
\colsep{0pt}{\begin{array}{ccccc}
(-1,0)&{}\stackrel T\to{}&(0,1)&{}\stackrel T\to{}&(1,1)\\
\mathllap{\scriptstyle T\,}{\uparrow}&&&&{\downarrow}\mathrlap{\scriptstyle\,T}\\
(-1,-1)&\underset T\gets&(0,-1)&\underset T\gets&(1,0)
\end{array}}
$$
