|
|
 |
Условие
Целые неотрицательные числа x и y удовлетворяют равенству x² – mxy + y² = 1 (1) тогда и только тогда, когда x и y – соседние члены последовательности (2): a0 = 0, a1 = 1, a2 = m, a3 = m² – 1, a4 = m³ – 2m, a5 = m4 – 3m² + 1, ..., в которой ak+1 = mak – ak–1 для любого k 0. Докажите это.
Решение
Для m = 1 нетрудно проверить, что при xy > 1 решений нет. Таким образом, решений конечное число, и все сводится к небольшому перебору.
Решим задачу для m = 3 (для других m > 1 решение совершенно аналогично).
Мы должны доказать, что, во-первых, все пары чисел (2) удовлетворяют
уравнению (1) и, во-вторых, никакие другие пары неотрицательных целых
чисел этому уравнению не удовлетворяют.
В последовательности (2) за каждой парой (x, y) следует пара (x', y') = (y, 3y – x). (3)
Преобразование (x, y) → (y, 3y – x) обозначим буквой T. Заметим, что если пара (x, y) удовлетворяет уравнению (1), то пара (x',y') = T(x, y) ему тоже удовлетворяет: y² – 3y(3y – x) + (3y – x)² = y² – 3xy + x². (4)
Отсюда сразу видно, что все пары (2) удовлетворяют уравнению (1): ведь
пара (0, 1) ему удовлетворяет, а все остальные получаются из неё
с помощью конечного числа преобразований T.
Докажем теперь, что других решений (x, y) в целых числах, подчиненных условиям 0 ≤ x < y, у уравнения (1) нет. Пусть (x', y') – одно из таких решений. Найдём такую пару (x, y), из которой эти x' и y'
получаются по формулам (3): x = 3x' – y', y = x'. (5)
Представим равенство x'² – 3x'y' + y'² = 1 следующими двумя способами:
x'² + y'(y' – 3x') = 1, (7)
x'(x' – y') + y'(y' – 2x') = 1. (8)
Из равенства (7) сразу следует (x' и y' положительны!), что –x = y' – 3x' ≤ 0.
Из равенства (8) следует, что y – x = y' – 2x' > 0 (ведь x' – y' отрицательно).
Заметим, что неравенства (6) можно переписать и так: 0 ≤ x < x'. (9)
Итак, любое решение (x', y'), 0 < x' < y', после преобразования T–1 переходит в решение (x, y), для которого 0 ≤ x < y.
Если при этом x > 0, то мы можем применить T–1 еще один или несколько раз, получая новые (меньшие по величине) решения.
Действительно, x при каждом преобразовании уменьшается. Поэтому через некоторое конечное число шагов мы должны будем остановиться, а остановиться мы можем лишь тогда, когда получим решение (x, y), у которого x = 0 и, следовательно, y = 1.
Отсюда следует, что каждое решение получится из (0, 1) за конечное число преобразований T, то есть что никаких других, отличных от (2), решений нет.
Замечания
Более наглядно это решение можно представить так. Будем изображать пару чисел (x, y) точкой плоскости. Тогда уравнение x² – 3xy + y² = 1 задаёт на плоскости гиперболу.
Решить это уравнение в целых числах – значит указать все точки
с целочисленными координатами, лежащие на гиперболе. Одну такую точку указать
легко – её координаты (0, 1). Все остальные (в пределах
угла 0 ≤ x < y), как мы доказали, получаются из неё последовательным применением преобразования T: (x, y) → (y, 3y – x). Это преобразование T плоскости обладает такими свойствами:
1) Переводит каждую прямую на плоскости снова в прямую (такие преобразования называются линейными).
2) Переводит любую целочисленную точку снова в целочисленную.
3) Переводит в себя каждую гиперболу x² – 3xy + y² = c ≠ 0 (и каждый из четырёх лучей с вершиной (0, 0), на которые распадается множество
x² – 3xy + y² = 0); каждая точка под действием T "переезжает" по своей гиперболе (или лучу) в свое новое положение; точка (0, 0) остаётся на месте. Такое преобразование называется гиперболическим поворотом с центром (0, 0) по аналогии с обычным "круговым" поворотом.
Теми же свойствами обладает и обратное преобразование T –1. Упомянем ещё одно интересное свойство этих преобразований:
4) Площадь любой фигуры при преобразовании не меняется.
Совершенно аналогично обстоит дело и при m > 3.
При m = 2 все наши рассуждения также проходят без изменения, но геометрическая интерпретация несколько меняется. Вместо свойства 3) соответствующее преобразование T: (x, y) → (y, 2y – x) обладает таким:
3') оно переводит каждую прямую y – x = c в себя; каждая точка "сдвигается" по своей прямой (при c ≠ 0), а все точки, лежащие на прямой
y – x = 0, просто остаются неподвижными. (Такое преобразование называется сдвигом.)
Для случая m = 1, то есть для уравнения x² – xy + y² = 1 (оно определяет на плоскости эллипс ), можно выписать аналогичное преобразование
T: (x, y) → (y, y – x), которое переводит это уравнение и вообще каждый эллипс x² – xy + y² = c в себя. Это преобразование называется эллиптическим поворотом. Оно так же, как и при m > 1, переводит все целочисленные решения уравнения друг в друга, но в данном случае решений всего шесть, и вместо схемы
(0, 1) → (1, 3) → (3, 8) → (8, 21) → ..., которую можно было бы нарисовать для уравнения (1), теперь получается такая:
2. Этот красивый факт был использован в работе Ю.В. Матиясевича, посвящённой десятой проблеме Гильберта, о которой рассказано в статье Ф. Варпаховского и А.Н. Колмогорова.
