4.5 ВЗАИМНАЯ ПРОСТОТА

Если то целые числа тип не имеют одинаковых простых сомножителей; в таком случае говорят, что они взаимно простые.

Это понятие настолько важно на практике, что следовало бы обзавестись для него специальным обозначением. Но, увы, теоретико-числовики еще не пришли к устраивающему всех соглашению, а потому мы взываем: Внемлите нам, о математики всего света! Больше медлить нельзя! Многие формулы можно сделать яснее уже сейчас, договорившись о новом обозначении! Согласимся же писать и говорить, что просто с если тип взаимно просты. Другими словами, давайте объявим, что

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

и это действительно так. Данное обстоятельство вытекает из более общего правила: доказанного в упр. 14.

Определение отношения упрощается, если воспользоваться представлением чисел в виде показателей простых. В силу правила (4.14) для имеем:

Более того, поскольку неотрицательны, это можно переписать в виде

А теперь можно установить важное правило, с помощью которого можно разъединять и объединять два отношения с одинаковой левой частью:

Ввиду соотношения (4.29) это правило представляет собой другой вариант следующего утверждения: тогда и только тогда, когда при неотрицательных .

Существует замечательный способ построения множества всех неотрицательных дробей носящий название дерева Штерна—Броко, поскольку он был открыт независимо друг от друга немецким математиком Морицем Штерном [357] и французским часовщиком Ахиллом Броко [41]. Суть этого способа в том, чтобы начать с двух дробей а затем повторить необходимое количество раз следующую операцию:

Новая дробь называется медиантой дробей . К примеру, первый шаг дает одну новую вставку между

следующий шаг добавляет две:

Последующий шаг добавляет четыре:

затем добавляется 8, 16 и т.д. новых вставок. Всю совокупность вставок можно представить в виде бесконечного бинарного дерева, верхние уровни которого выглядят так:

Каждая дробь имеет вид где — ближайший предок сверху слева, а — сверху справа. („Предком" является дробь, которая достижима, если следовать по ветвям вверх.) Подобное дерево радует глаз обильным урожаем закономерностей.

Но почему это дерево плодоносно? Почему, например, каждая медианта оказывается несократимой, когда созревает на этом дереве? (Если бы все числа были нечетны, то мы получали бы дроби вида четное/четное — тем не менее наше построение гарантирует, что дроби с нечетными числителями и знаменателями никогда не появляются рядом.) И почему все возможные дроби встречаются только однажды? Почему какая-нибудь дробь не может встретиться дважды или не встретиться вообще?

Все эти вопросы имеют на удивление простые ответы, в основе которых лежит следующий элементарный факт: если — последовательные дроби на любом шаге их построения, то

Это соотношение справедливо первоначально а когда мы вставляем новую медианту то надо проверить новые соотношения:

Оба этих уравнения эквивалентны исходному условию (4.31), которое они заменяют. Поэтому условие (4.31) инвариантно на всех шагах построения.

Кроме того, если и если все эти величины неотрицательны, то легко убедиться в том, что

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

Остается еще один вопрос: может ли какая-нибудь положительная дробь с оказаться пропущенной? Ответ отрицательный, ибо наше построение можно ограничить непосредственной окрестностью дроби в которой ее поведение легко поддается анализу. Вначале положим

где скобки у дроби указывают на то, что на самом деле ее здесь нет. Затем, если на некотором шаге

то наше построение образует дробь и здесь возможны три варианта. Либо и мы удовлетворены; либо и можно положить либо и можно положить Этот процесс не может продолжаться неограниченно, поскольку условия

означают, что

следовательно,

а это то же самое, что и согласно (4.31). С каждым шагом либо либо либо либо возрастают, так что мы должны быть удовлетворены после самое большее а шагов.

Последовательностью Фарея порядка обозначаемой через является множество всех несократимых дробей между 0 и 1, знаменатели которых не превосходят и которые расположены в возрастающем порядке. Так, если то

В общем случае последовательность можно получить, начав с и затем вставляя медианты всякий раз, когда это можно сделать, с тем чтобы не получить превышающий знаменатель. При этом ни одна дробь не будет пропущена, поскольку известно, что построение Штерна—Броко не пропускает ни одну из них, и поскольку медианта со знаменателем никогда не образуется из дроби, знаменатель которой (Другими словами, выделяет в дереве Штерна—Броко некоторое поддерево,

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

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

Если — простое число, то появится новых дробей; в противном случае их появится меньше так как подобный процесс порождает лишь дроби, имеющие взаимно простые с числители.

Еще в (4.5) было доказано — правда, в других терминах, - что если то можно найти целые числа а и такие, что

(На самом деле утверждалось, что но вместо можно подставить 1, вместо подставить вместо подставить Последовательность Фарея обеспечивает нас другим доказательством равенства (4.32), так как можно положить дробь равной дроби, которая предшествует дроби в последовательности Таким образом, (4.5) снова есть просто (4.31). К примеру, одним из решений уравнения является поскольку дробь предшествует дроби у в Из этого следует, что всегда можно найти решение уравнения если Аналогично, если то уравнение можно решить, полагая равной дроби, следующей за дробью

Последовательные тройки дробей последовательности Фарея обладают удивительным свойством, которое доказано в упр. 61. Но лучше прекратить дальнейшее обсуждение последовательностей Фарея, ибо в целом дерево Штерна—Броко оказывается гораздо более интересным.

И в самом деле, дерево Штерна—Броко можно рассматривать как систему счисления для представления рациональных чисел, поскольку каждая положительная несократимая дробь встречается в нем лишь один раз. Воспользуемся символами для идентификации левой и правой ветви при продвижении вниз по дереву от корня к некоторой определенной дроби; тогда строка символов будет однозначно идентифицировать местонахождение дроби в этом дереве. Так, означает продвижение вниз влево от к затем вправо к еще раз вправо к и, наконец, влево к строку можно рассматривать как

представление дроби При таком подходе каждая положительная дробь получает единственное представление в виде строки символов

Однако имеется небольшое затруднение: дробь соответствует пустой строке и необходимо подыскать ей какое-нибудь обозначение. Давайте условимся обозначать ее через I, поскольку этот символ напоминает цифру 1 и с него начинается слово „identity" (единица — Перев.).

Такого рода представление вызывает два естественных вопроса. (1) Если заданы целые положительные числа типе то какая строка символов соответствует дроби Если задана некоторая строка символов то какая дробь ей соответствует? Вопрос 2 выглядит попроще, поэтому займемся им в первую очередь. Пусть

где — некоторая строка символов Так,

В соответствии с нашим построением если являются ближайшими к (предшествующими и последующими) дробями на верхних уровнях нашего дерева. Первоначально затем либо либо последовательно заменяются медиантой по мере продвижения по дереву соответственно вправо или влево.

Но как облечь это действо в подходящие математические одежды? Некоторый опыт подсказывает, что наилучший способ — скроить -матрицу

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

Шаг влево заменяет следовательно,

(Это частный случай общего правила

умножения -матриц.) Точно так же оказывается, что

Поэтому если определить как -матрицы

то индукцией по длине мы получим простую формулу Разве не здорово? (Буквы исполняют две роли: роль матриц и роль символов в строковом представлении.) К примеру,

так что дроби-предки, которые охватывают дробь равны и Это построение дает ответ на вопрос 2:

А как насчет вопроса 1? Теперь, когда мы выяснили элементарную связь между узлами дерева и матрицами ответить на него уже просто. При заданной паре целых положительных чисел местоположение дроби в дереве Штерна—Броко можно установить „двоичным поиском":

Результатом работы (посылаемым на вывод) является требуемая строка символов

То же самое можно выполнить и другим способом, изменяя величины тип без использования переменной Если — некоторая -матрица, то

поскольку матрица схожа с матрицей с тем лишь отличием, что в матрице верхняя строка матрицы прибавлена к нижней. (Распишем это подробнее:

следовательно, Если алгоритм двоичного поиска выполняется применительно к некоторой дроби то первым

выводом алгоритма будет следовательно, при дальнейшем выполнении алгоритма будет ровно на 1 больше, чем если бы мы начинали с а не с Аналогичное обстоятельство имеет место и для так что получаем

Это значит, что алгоритм двоичного поиска можно преобразовать в следующую безматричную процедуру:

Так, если то с использованием этого упрощенного алгоритма последовательно получаем:

В дереве Штерна—Броко отсутствуют иррациональные числа, но зато присутствуют все „близкие" к ним рациональные числа. Так, если попытаться использовать алгоритм двоичного поиска с числом вместо дроби то получим бесконечную строку символов

Эту бесконечную строку можно рассматривать как представление числа в системе счисления Штерна—Броко, точно так же, как число можно представить в виде бесконечной десятичной дроби или в виде бесконечной двоичной дроби Между тем оказывается, что представление числа в системе Штерна—Броко обнаруживает устойчивую закономерность:

что эквивалентно частному случаю одного открытия, сделанного Эйлером [369] в возрасте 24 лет.

Исходя из этого представления, можно установить, что дроби

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

из этого списка с числителем и знаменателем . К примеру, дробь не служит столь же простым приближением, как дробь которая присутствует в списке и которая ближе к числу е. Мы можем убедиться в этом на основании того, что дерево Штерна—Броко не просто включает все рациональные числа — оно включает их в упорядоченном виде, а также на основании того, что все дроби с малыми числителем и знаменателем располагаются выше всех менее простых дробей. Так, дробь меньше дроби которая, в свою очередь, меньше числа способ позволяет находить прекрасные приближения. К примеру, дробь эта дробь получается из первых 16 символов представления числа в системе Штерна—Броко, а точность примерно такая же, как в случае -битового двоичного представления этого числа.

Бесконечное представление некоторого иррационального числа можно получить путем простой модификации безматричной процедуры двоичного поиска:

(Эти шаги должны быть повторены бесконечное число раз, пока не надоест.) Если число а — рациональное, то бесконечное представление, полученное этим способом, аналогично прежнему, но к (конечному) представлению справа присоединяются символы . К примеру, если то получаем что соответствует бесконечной последовательности дробей стремящейся в пределе к 1. Такое положение дел в точности соответствует обычному двоичному представлению, если рассматривать как 0 и как 1: точно так же, как каждое вещественное число х из [0, 1) имеет бесконечное двоичное представление не оканчивающееся одними цифрами 1, так и каждое вещественное число из имеет бесконечное представление Штерна—Броко не оканчивающееся одними символами Таким образом, имеется сохраняющее порядок взаимно однозначное соответствие между [0, 1) и если исходить из соответствия

Существует тесная связь между алгоритмом Евклида и представлением Штерна—Броко рациональных чисел. Если то получаем символов затем символов после чего символов и т. д. Числа — это не что иное, как величины, фигурировавшие в алгоритме Евклида. (Нужно проявить некоторую изобретательность, чтобы обеспечить отсутствие в конце бесконечного числа символов Подобная взаимосвязь будет исследована в гл. 6.