Заменим плюс на минус

Мы уже говорили о пользе симметрии в геометрических задачах. Своего рода симметрией в алгебре является замена плюса на минус.

Так, если какое-либо выражение от √ d равно p + q √ d и мы всюду в этом выражении заменим √ d на –√ d, то естественно ожидать, что новое выражение окажется равным сопряженному числу p – q √ d. Мы будем пользоваться таким очевидным частным случаем этого свойства (a и b — рациональны, √ d — нет):

5. Доказать, что уравнение

(x + y √5)⁴ + (z + t √5)⁴ = 2 + √5

не имеет решений в рациональных числах x, y, z, t.

Можно, конечно, найти отдельно сумму членов левой части, не содержащих √5 (она должна быть равна 2), и отдельно — коэффициент при √5 (он должен равняться 1). Но что делать с полученной громоздкой системой неясно. Вместо этого воспользуемся (4) и заменим плюс перед √5 на минус!

(x – y √5)⁴ + (z – t √5)⁴ = 2 – √5.

Слева стоит неотрицательное число, справа — отрицательное.

6. Доказать, что существует бесконечно много пар (x; y) натуральных чисел, для которых x ² отличается от 2 y ² на 1:

Несколько таких пар с небольшими (x; y) легко найти подбором: это (1; 1), (3; 2), (7; 5), (17; 12),... (рис. 1). Как продолжить этот набор? Можно ли записать общую формулу для этих решений?

Рис. 1. Проходят ли эти гиперболы через бесконечное число узлов клетчатой бумаги?

Найти ответы на эти вопросы нам поможет число 1 + √2. Закономерность, позволяющая получать всё новые и новые решения (x; y), указана в таблице:

Какой будет шестая строчка?

Видно, что коэффициенты x_n, y_n в числе

x_n + y_n √2 = (1 + √2) ⁿ

будут давать нужную пару. Доказать это поможет колонка таблицы из сопряжённых чисел (мы снова применяем (4)):

x_n – y_n √2 = (1 – √2) ⁿ.

Перемножив два последних равенства, получим

и интересующее нас выражение попеременно равно то 1, то –1. Складывая и вычитая эти же два равенства, мы получим явное выражение для x_n и y_n:

Можно ли в решении этой задачи про целые числа обойтись без иррациональных чисел 1 + √2 и 1 – √2? Теперь, зная ответ, мы можем легко выразить (x_{n +1}; y_{n +1}) через предыдущую пару (x_n; y_n): из x_{n +1} + y_{n +1}√2 = (x_n + y_n √2)(1 + √2) вытекает

До этого рекуррентного соотношения можно было, видимо, догадаться по нескольким первым решениям, а потом проверить, что

Добавив начальное условие x ₁ = 1, y ₁ = 1, отсюда (по индукции) можно было бы заключить, что | x_n ² – 2 y_n ²| = 1 для любого n. Далее, выразив обратно (x_n; y_n): через (x_{n +1}; y_{n +1}), «методом спуска» ([8]) можно доказать, что найденной серией исчерпываются все решения уравнения (5) в натуральных числах (x; y). Подобным же образом решается любое «уравнение Пелля» x ² – dy ² = c (а к уравнениям такого типа сводится любое квадратное уравнение в целых числах x, y), но у исходного уравнения может быть несколько серий решений ([7]).

Рекуррентные соотношения типа (6) возникают не только в теории чисел, но и в разных задачах анализа, теории вероятностей. Вот характерный пример комбинаторной задачи такого типа (она предлагалась на последней международной олимпиаде в Лондоне):

7 (М595). В вершине A правильного восьмиугольника сидит лягушка. Из любой вершины восьмиугольника, кроме вершины E, противоположной A, она может прыгнуть в любую из двух соседних вершин. Попав в E, лягушка останавливается и остаётся там. Найти количество e_m различных способов, которыми лягушка может попасть из вершины A в E ровно за m прыжков.

Если раскрасить вершины восьмиугольника через одну в чёрный и белый цвет (рис. 2), сразу станет ясно, что e _{2 k –1} = 0 при любом k: цвет вершин при каждом прыжке меняется. Обозначим через a_n и c_n количество способов, которым лягушка может за 2 n прыжков, попасть из вершины A, соответственно, в вершину A и в одну из вершин C (из соображений симметрии ясно, что в каждую из вершин, обозначенных на рисунке буквой C, можно попасть одним и тем же числом способов). Как легко проверить (см. рис.2а,б,в,г),

a ₁ = 2, c ₁ = 1;

А интересующее нас число e _{2 n} равно, очевидно, 2 c_{n –1} (рис. 2д).

а) c 1 = 1

б) a 1 = 2

в) an +1 = 2 an + 2 cn

г) cn +1 = an + 2 cn

д) e 2 n = 2 cn –1

Как же найти явную формулу для a_n и c_n? Запишем наше рекуррентное соотношение (7) так:

и — как вы уже, конечно, догадались — ещё так:

Отсюда по индукции, пользуясь (7), получаем:

Поэтому

а так как e _{2 n} = 2 c_{n –1}, получаем окончательно

Задача решена. Неясно только, как в этой задаче (и в предыдущей задаче 6) можно было додуматься до формул, содержащих ±√2, — ведь в задаче речь идёт о целых числах! (Для участников олимпиады и читателей «Кванта» задача 7 была облегчена тем, что в формулировке указывался ответ — «Квант», 1979, № 11, М595).

Однако «сопряжённые числа» возникли бы совершенно автоматически, если бы мы владели началами линейной алгебры (см. [12]), и применили стандартные правила этой науки к решению уравнений (7). Эти правила предлагают сначала выяснить, какие геометрические прогрессии (a_n = a ₀λ ⁿ, c_n = c ₀λ ⁿ) удовлетворяют данному рекуррентному соотношению. Значения, для которых такие прогрессии существуют, — они называются характеристическими значениями или собственными числами — определяются из некоторого уравнения (оно тоже называется характеристическим). Для (7) характеристическое уравнение имеет вид λ² – 4λ + 2 = 0, его корни — как раз 2 + √2 и 2 – √2. Зная эти корни, любое решение рекуррентного соотношения мы можем получить как «линейную комбинацию» соответствующих геометрических прогрессий ([11]). «Начальное условие» (в нашем случае a ₁ = 2, c ₁ = 1) определяет нужное нам решение однозначно.

Неудивительно, что даже самые простые рекуррентные целочисленные последовательности, для которых характеристическое уравнение — квадратное с целыми коэффициентами (примеры — те же (6) и (7) или последовательность Фибоначчи 1, 1, 2, 3, 5, 8,..., F_{n +1} = F_n + F_{n –1}; см. [9], [10]), выражаются, как функции номера, с помощью «сопряжённых» квадратичных иррациональностей.

Заметим, что большее характеристическое число определяет скорость роста последовательности: при больши́х n в задаче 7

e_n» (2 + √2) ⁿ /√2.

Можно сказать это ещё так:

Для задачи 6 аналогичное наблюдение:

Интересное продолжение этого факта мы увидим в следующей задаче с бо́льшим числом «сопряжённых» иррациональностей.