Генеалогические деревья

8

ГЕНЕАЛОГИЧЕСКИЕ ДЕРЕВЬЯ

А. А. ПАНОВ

В этой статье пойдет речь о математической классике — алгоритм Евклида и пифагоровых тройках. Алгоритм Евклида описан в εκklидовых «Началах» (около 300 г. до н. э.) и наверняка был известен задолго до этого. История пифагоровых троек прослеживается еще дальше. Замечательным памятником человека ккультуры является древнеавилонская глиняная таблица, содержащая пятнадцать пифагоровых троек. Она датируется 1700 годом до н. э.

Мы здесь попытаемся строить пыль с этих древних понятыми, поговорить о них на наглядном «языке деревьев». Этот язык оказывается полезным при решении некоторых уравнений и указывает, какая связь существует между алгоритмом Евклида и методом построения пифагоровых троек, недавно предложенным английским математиком А. Холлом.

Алгоритм Евклида
Алгоритм Евклида служит для нахождения наиболее общего делителя (НОД) двух натуральных чисел.

Пусть $(m, n)$ — пара положительных целых чисел:

1. если $m=n$, то число $d=m=n$ и есть наиболее общий делитель исходной пары чисел, если $m \neq n$, то перейти к 2);
2. большее число заменить на его разность с меньшим и перейти к 1).

Возможно, вы больше привели к следующему варианту шага 2:

2’) большее число заменить на его остаток от деления на меньшее и перейти к 1),
но это дело вкуса.

Задача 0. Докажите, что оба алгоритма 1), 2) и 1), 2’) приводят к одному и тому же результату.

Указание. Вспомните, что деление — это многоократное вычитание.

Во всяком случае, сам Евклид говорит о своем алгоритме как о «постоянном отличии меньше от большего» («Начала», Книга 7, Предложение П, перевод Д. Д. Мордухай-Болтовского). Именно этот алгоритм, основанный на многоократном вычитании, и будет объektом нашего исследования.

Продемонстрируем работу алгоритма на конкретном примере. Пусть $(m, n)=(20, 12)$. Тогда, записывая действия алгоритма справа налево, получим следующее цепочку:

$(4, 4) \leftarrow (8, 4) \leftarrow (8, 12) \leftarrow (20, 12)$.

Значит, НОД $(20, 12)=4$. Проделав то же самое для пары $(5, 3)$, получим цепочку

$(1, 1) \leftarrow (2, 1) \leftarrow (2, 3) \leftarrow (5, 3)$.

Ясно, что каждое число во второй цепочке получается из соответствующего числа в первой цепочке делением на 4.

Разобравшись с этим примером, ответьте на следующий вопрос.

Задача 1. Пусть $d=НОД (M, N)$. Положим $m=M/d, n=N/d$. Чему равен НОД $(m, n)$ и в чем сходство между действием алгоритма Евклида на пару $(M, N)$ и на пару $(m, n)$?

В дальнейшем мы ограничим только пары $(m, n)$, для которых НОД $(m, n)=1$. Такие пары будем называть простыми парами.

Генеалогия простых пар
Рассмотрим еще один пример. Применим алгоритм Евклида к простой паре $(3, 4)$:

$(1, 1) \leftarrow (2, 1) \leftarrow (3, 1) \leftarrow (3, 4)$.

Эта цепочка имеет общую часть с цепочкой для пары $(5, 3)$, и потому их можно обединить:

$(3, 1) \leftarrow (3, 4)$
$(2, 3) \leftarrow (5, 3)$

Можно добавить еще одну простую пару $(3, 2)$, и картина условия:

$(3, 1) \leftarrow (3, 4)$
$(2, 1) \leftarrow (2, 3) \leftarrow (5, 3)$
$(1, 2) \leftarrow (3, 2)$

10

Создается впечатление, что должно существовать общая картина, обведенная все простые пары. Чтобы выяснить ее строение, можно было бы добавить еще несколько простых пар. Так или иначе, в какой-то момент времени нам должны прийти в голову правильный вопрос: путь имеет простая пара $(m, n)$; от каких пар к ней могут идти стрелки?

Задача 2. Докажите, что если от пары $(M, N)$ в алгоритме Евклида идет стрелка к паре $(m, n)$, то либо $M=m+n$, $N=n$, либо $M=m$, $N=m+n$.

Эта задача подсказывает, что нужно ввести два преобразования $t_1$ и $t_2$, переводящих пару $(m, n)$ в пары
$$t_1(m, n)=(m+n, n),$$
$$t_2(m, n)=(m, m+n).$$
(1).

Тепер мы можем двигаться в обратном порядке. Начнем с пары $(1, 1)$ и применим к ней оба преобразования $t_1$ и $t_2$ ($t_1$ действует по стрелке, идущей вверх, $t_2$ — по стрелке, идущей вниз). Получим две новые пары — $(2, 1)$ и $(1, 2)$. К каждой из них снова применим $t_1$ и $t_2$ и т. д.

Каждая пара здесь порождает две новые пары, и этот процесс продолжается впервые до бесконечности. Как и следовало ожидать, рисунок 1 содержит в качестве фрагментов все предыдущее картини, только стрелки здесь обращены в другую сторону.

Рис. 1.

Задача 3. Докажите, что любая пара $(m, n)$ на рисунке 1 простая.

Задача 4. Докажите, что каждая простая пара содержится на рисунке 1 и притом только один раз.

После этих задач to, что изображено на рисунке 1, естественно называть генеологическим деревом простых пар.

Задача 5. Пусть пара $(m, n)$ лежит на генеологическом дереве на рисунке 1. Существует единственный путь, соединяющий ее с начальной парой $(1, 1)$. Покажите, что движение по этому пути против стрелок соответствует применению к паре $(m, n)$ алгоритма Евклида.

Итак, генеологическое дерево на рисунке 1 содержит все простые пары. Применение алгоритма Евклида к паре $(m, n)$ эквивалентно движению по дереву против стрелок.

Уравнение $XY=Z^2$
Изменим теперь тему разговора и попытаемся найти все целочисленные решения $(X, Y, Z)$ уравнения
$$XY=Z^2.$$

Ограничим лишь положительные $X, Y, Z$. Пример: $X=3$, $Y=12$, $Z=6$.

Казалось бы, о чем говорить? Для заданного $Z$ отискание решения уравнения свойства к разложению числа $Z^2$ на два сомножителя, и для каждой $Z$ можно даже подсчитать число решения.

Задача 6. Заффиксируем $Z$ и путь $Z=p_1^{a_1}p_2^{a_2}...p_l^{a_l}$ — разложение $Z$ на простые сомножители. Докажите, что число решения уравнения (2) равно $(2a_1+1)(2a_2+1)...(2a_l+1)$.

Однако я хочу предложить другую точку зрения.

Задача 7. Пусть $(X, Y, Z)$ — решение уравнения (2); докажите, что при $d>0$ тройка $(dX, dY, dZ)$ — тоже решение. Пусть $(X, Y, Z)$ — решение уравнения (2) и НОД $(X, Y)=d$; докажите, что $(X/d, Y/d, Z/d)$ тоже решение уравнения (2) и при этом НОД $(X/d, Y/d)=1$.

Таким образом, при отискании всех решений $(X, Y, Z)$ уравнения (2) мы можем ограничиться только теми, для которых НОД $(X, Y)=1$; будем назвать их примитивными. Все остальные получаются из примитивных простым умножением.

Задача 8. Пусть $(X, Y, Z)$ — примитивное решение уравнения (2). Докажите, что найдется такая простая пара $(m, n)$, что $X=m^2$, $Y=n^2$, $Z=mn$.

Тепер ясно, что соответствия $X=m^2$, $Y=n^2$, $Z=mn$ (3) осуществляется взаимно однозначное соответствие между простыми парами $(m, n)$ и примитивными решениями $(X, Y, Z)$ уравнения (2).

Это значит, что мы в полной мере можем воспользоваться нашими предыдущими результатами о простых парах. Например, используя соответствие (3), заменим на рисунке 1 каждую простую пару $(m, n)$ соответствующим ей примитивным решением $(X, Y, Z)$. Получившееся дерево естественно называть генеологическим деревом примитивных решений уравнения (2). Оно содержит все без

11

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

Задание 9. Пусть пара $(m, n)$ порождает при помощи (3) решения $(X, Y, Z)$. Обозначим решение, пороженное парой $t_1(m, n) = (m+n, n)$, через $T_1(X, Y, Z)$ и решение, пороженное $t_2(m, n) = (m, m+n)$, — через $T_2(X, Y, Z)$. Доказите, что

$$T_1(X, Y, Z) = (X+Y+2Z, Y, Y+Z),$$
$$T_2(X, Y, Z) = (X, X+Y+2Z, X+Z).$$

Все это означает, что генеалогическая дерево на рисунке 2 возникает непосредственно при помощи преобразования $T_1$ и $T_2$. Мы исходим из очередного решения (1, 1, 1) и начинаем действовать на него преобразования $T_1$ и $T_2$. Стрелка, идущая вверх, соответствует действию $T_1$, стрелка, идущая вниз, — действию $T_2$.

Рис. 2.

Рисунок 2 выглядает весма привлекательным и позволяет получитьясное представление об устройстве множества всех примитивных решений уравнения (2). Но все-tаки уравнение $XY=Z^2$, как мы уже говорили, допускает и более простой подход. Поэтому перейдем к рассмотрению более содержательного примера.

Пифагороны тройки

Итак, уравнение
$$X^2+Y^2=Z^2.$$
Его целочисленные положительные решения $(X, Y, Z)$ называются пифагороны тройками. Самый первый пример пифагоровой тройки — это, конечно, тройка (3, 4, 5). Нам бы хотелось и для этого уравнения построить дерево решений — генеалогическое дерево пифагоровых тройки, подобное тому, что на рисунке 2. Как это сделать? Если следовать тому, что было сделано для уравнения $XY=Z^2$, то необходимо:

(I) среди всех пифагоровых троек выделить примитивные;

(II) для примитивных пифагоровых троек $(X, Y, Z)$ выписать подходящие соответствия $X=X(m,n), Y=Y(m,n), Z=Z(m,n)$ на подобные соответствий (3);

(III) построить генеалогическое дерево для пар $(m, n)$ и заменить на нем каждую пару $(m, n)$ на порожденную его тройку $(X(m, n), Y(m, n), Z(m, n))$.

To, что связано с пунктами (I) и (II), уже давно известно. Мы сообщим необходимые факты без каких бы то ни было комментариев и доказательств, отсылая читателя в случае необходимости к статье С. М. Воронина и А. Г. Кулагина («Квант», 1987, № 1, с. 11).

Пифагорова тройка $(X, Y, Z)$ называется примитивной, если НОД $(X, Y)=1$ и при этом $X$ нечетно, а $Y$ четно. Тройка (3, 4, 5), например, примитивна.

Известно, что для любой пифагоровой тройки $(x, y, z)$ существует такая единственная примитивная пифагорова тройка $(X, Y, Z)$ и такое единственное натуральное число $d$, что либо $(x, y, z)=(dX, dY, dZ)$, либо $(x, y, z)=(dY, dX, dZ)$. Тем самым, перечислив все примитивные пифагороны тройки, мы получаем возможность перечислять и все вообщепи-fontовы тройки.

Целочисленная пара $(m, n)$ называется примитивной, если $m>n, n>0$, НОД $(m, n)=1$ и числа $m, n$ имеют разную четность. Пара (2, 1), например, примитивна.

Известно, что соответствия $X=m^2-n^2, Y=2mn, Z=m^2+n^2$ (4) осуществляют взаимно однозначное соответствие между множеством всех примитивных пар и множеством всех примитивных пифагоровых троек. Пара (2, 1), например, при помощи соответствий (4) порождает тройку (3, 4, 5).

Что касается пункта (III) нашей программы построения генеалогического дерева, то он был реализован английским математиком А. Холлом.

Генеалогия пифагоровых троек

В небольший заметке, опубликован в 1970 году в журнале «Mathematical Gazette», А. Холл предлагает

12

следующий способ построения генеалогического дерева для примитивных пар и примитивных пифагоровых troek. Вводятся три преобразования $t_1, t_2$ и $t_3$:

$$t_1(m, n) = (2m - n, m),$$
$$t_2(m, n) = (2m + n, m),$$
$$t_3(m, n) = (m + 2n, n).$$

При помощи этих преобразований, начиная с пары (2, 1), строится генеалогическое дерево. Здесь направление вверх соответствует преобразования $t_1$, горизонтальное направление — преобразование $t_2$, направление вниз — преобразование $t_3$.

Задача 10. Пусть пара $(m, n)$ порождает при помощи соответствий (4) пифагорову troйку $(X, Y, Z)$. Пифагорову troйку, порожденную парой $t_1$ $(m, n)$, обозначаем через $T_1(X, Y, Z)$; troйку, порожденную парой $t_2$ $(m, n)$, — через $T_2(X, Y, Z)$; наконец, troйку, порожденную парой $t_3$ $(m, n)$, — через $T_3(X, Y, Z)$. Докажите, что

$$T_1(X, Y, Z) = (X - 2Y + 2Z, 2X - Y + 2Z, 2X - 2Y + 3Z),$$
$$T_2(X, Y, Z) = (X + 2Y + 2Z, 2X + Y + 2Z, 2X + 2Y + 3Z),$$
$$T_3(X, Y, Z) = (-X + 2Y + 2Z, -2X + Y + 2Z, -2X + 2Y + 3Z).$$

Теперь при помощи преобразования $T_1, T_2, T_3$ построим еще одно генеалогическое дерево, но уже началосься с troйки (3, 4, 5).

Замечательный результат Холла заключается в том, что генеалогическое дерево на рисунке 3 содержит все без исключения примитивные пары; значит, генеалогическое дерево на рисунке 4 содержит все без исключения пары (2, 1).

К каждой паре $(m, n)$ на рисунке 3 подходитровно одна стрелка. Для преобразования $u_1, u_2, u_3$ это соответствует следующему факту.

Задача 13. Пусть пара $(M, N)$ примитивна и $(M, N) \neq (2, 1)$. Докажите, что тогда только одна из трех пар $(m, n) = u_i(M, N)$, $i = 1, 2, 3$, будет примитивной. При этом $m + n < M + N$.

И, наконец, завершаюшая

Задача 14. Докажите, что каждая примитивная пара содержится на генеалогическом дереве на рисунке 3 и при этом только один раз (а также каждая примитивная пифаговая troйка на рисунке 4).

Другие генеалоги

В 1978 году в скандинавском математическом журнале «Normat» была опубликована статья Е. Сельмара, в которой установлен, что существуют

13

еше два генеологических деревьев, содержащих все без исключений и повторений примитивные пифагоровы трейки (рис. 5).

Первое из них строится при помощи преобразования
$$T_1(X, Y, Z) = (2X - Y + Z, 2X + 2Y + 2Z, 2X + Y + 3Z),$$
$$T_2(X, Y, Z) = (2X + Y + Z, 2X - 2Y + 2Z, 2X - Y + 3Z),$$
$$T_3(X, Y, Z) = (2X + Y - Z, -2X + 2Y + 2Z, -2X + Y + 3Z).$$

Второе — при помощи преобразования
$$T_1(X, Y, Z) = (X - 2Y + 2Z, 2X - Y + 2Z, 2X - 2Y + 3Z),$$
$$T_2(X, Y, Z) = (2X + Y + Z, 2X - 2Y + 2Z, 2X - Y + 3Z),$$
$$T_3(X, Y, Z) = (-2X + 3Y + 3Z, -6X + 2Y + 6Z, -6X + 3Y + 7Z).$$

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

Подводя итоги
В связи с тем, что было расссказано, имеется несколько вопросов, которые необходимо если не решить, то по крайней мере задать. Например, почему для управления $XY = Z^2$ от каждой решения отходят две стрелки, а на генеологическом дереве для $X^2 + Y^2 = Z^2$ — три? Далее, почему для управления $X^2 + Y^2 = Z^2$ построено три генеологических деревьев, а для $XY = Z^2$ — только одно, и существует ли для этих управления другие деревья? Наконец, как бы найдены преобразования $T_1$, $T_2$, $T_3$, позволяющие строить генеологические деревья для пифагоровых трейки?

Наше построение генеологического дерева для управления $XY = Z^2$ напрямую связано с алгоритмом Евклида и выгладит достаточно мотивированным, чего нельзя сказать об управлении $X^2 + Y^2 = Z^2$. Однако между этим управлениями имеется связь, оправдывающая попытки сделать для одного из них то, что было сделано для другого. Действительно, записем управление $X^2 + Y^2 = Z^2$ в виде $Z^2 - X^2 = Y^2$ и разложим левую часть на множители: $(Z - X)(Z + X) = Y^2$. Сделав замену $U = Z - X$, $V = Z + X$, $W = Y$, приходим к управлению $UV = W^2$. Таким образом, существует замена, переводящая управление $X^2 + Y^2 = Z^2$ в управление $XY = Z^2$.

Имеется еще цель ряда управления, допускающих замену, переводящую их в $XY = Z^2$. Таким управлениями будут, скажем, $X^2 + Y^2 = 2Z^2$ и $X^2 + 3Y^2 = Z^2$. Вы можете попытаться построить генеологические деревья и для этих управлений.

Необходимо сказать еще об одном заменаальном управлении — управлении Маркова:
$$X^2 + Y^2 + Z^2 = 3XYZ.$$

Оно обладает уже привящным для нас свойством — все его решения, кроме двух очень низких (1, 1, 1) и (2, 1, 1), организуют в генеологическое дерево. Об этом подробно расссказано в увеличительной стате М. Г. Крейна («Квант», 1985, № 4, с. 13). Это дерево вполне аналогично генеологическому дереву для управления $XY = Z^2$. Существует ли какая-то связь между этим управлениями? Какие еще управления обладают подобными свойствами?

Так что тут есть о чем еще подумать.