чтобы вектор 64 оставался выше прямой, а если к нему прибавить е, то мы перескочим через прямую. Как видите, = 2.

Векторы получаются всё более длинные, поэтому алгоритм и назвали «вытягиванием носов».

Далее, ё = ё + а. Взяв а2 = 3, попадаем как раз на прямую. Итак, UQ = 1, = 2, = 3,

1 1 , 1 10 7 •

«0 +

= 1 +

а, + -

Можно доказать, что этот алгоритм всегда даёт целые числа а,

а,, а

1> "2>

рис. 2

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

Доказательство этого факта несложно. Главное - это то, что прямая с уравнением у=Ах в какой-либо

системе координат задаётся также уравнением х = \у

в системе координат с переставленными осями абсцисс и ординат. А прямая с уравнением у = Ах в системе с базисными векторами е (на оси х) и / (на оси у) задаётся при А = а+В уравнением z = Biv в системе с базисными векторами e+af (на оси w)Hf (на оси 2). Цепная дробь получается при последовательном применении (поочерёдно) этих двух (очевидных) фактов.

Я докажу две леммы, которые составляют основу геометрии чисел.

Две леммы геометрии чисел

Лемма 1. Рассмотрим на плоскости с координатной сеткой «пустой» параллелограмм с вершинами в узлах сетки, т. е. такой, что ни внутри, ни на его границе нет других узлов сетки, например, как на рис. 2. Плош;адь этого параллелограмма равна 1.

Конечно, не так трудно посчитать плош;адь параллелограмма, но я расскажу, как эту задачу решает физик. С точки зрения математиков это не доказательство, оно не использует аксиом.

в «исповеди» жан-жака руссо написано, что, когда он начал учиться в школе и научился раскрывать скобки, он рис. 3

вывел замечательную формулу - формулу квадрата суммы:

(а + Ь) = а+ 2аЬ + Ь. но, хотя он сам это открыл и не сомневался, что раскрывал скобки правильно, поверить в эту формулу не мог - до тех пор, пока не нашёл другое

доказательство, без скобок. Вот это доказательство: разрежем квадрат со стороной а+ 6 на четыре части (рис. 3), откуда видно, что его площадь равна a+ab + ba + b. После этого все сомнения пропадают.

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

Так вот, эту лемму я сейчас докажу физическим способом, «по Руссо».

Доказательство леммы 1. Сдвигая наш параллелограмм на всевозможные комбинации векторов, на которые он натянут, мы можем покрыть всю плоскость равными параллелограммами, подобно тому, как её покрывали единичные квадратики, образованные линиями координатной сетки (рис. 4).

Возьмём кусок плоскости большой плош;ади А и посчитаем, сколько в нём, с одной стороны, наших параллелограммов, с другой стороны, целых точек. Пусть плош;адь параллелограмма равна S, тогда, если плош;адь А очень велика, число параллелограммов приблизительно равно A/S (этот кусок плоскости не обязательно состоит из целых параллелограммов, поэтому равенство будет неточным; впрочем, можно взять кусок, состо-яш;ий из целых параллелограммов, тогда получится точное равенство). Понятно, что число целых точек примерно равно А.

Посчитаем теперь число целых точек в нашей области другим способом. На каждый параллелограмм приходится 4 точки (его вершины),

но при этом мы считаем каждую вершину 4 раза, и если мы посчитаем число всех вершин всех параллелограммов, то получится в 4 раза больше, чем число всех целых точек вообш;е. Поэтому целых точек и параллелограммов одинаковое количество. Получается, что А ~A/S при очень большом А. Значит, S=l.

Замечание. Это рассуждение легко обобш;ается на случай, когда у параллелограмма с вершинами в целых точках есть еш;ё k целых точек внутри и I целых точек на сторонах. Плош;адь такого параллелограмма S = 1 + k + yl. Читателю предлагается самому найти коэффициенты р и у и тем самым получить ответ (его можно проверить экспериментально при небольших кш1).

Рис. 4

Лемма 2 (формула площади параллелограмма). Рассмотрим параллелограмм, натянутый на векторы с координатами (а, ft) и (c,d) (числа а, Ъ, с, d не обязательно целые), рис. 5. Будем считать, что его площадь имеет знак плюс, если поворот от первого вектора ко второму идёт в ту же сторону, что и поворот от оси Ох к оси Оу, и знак минус в противном случае. Тогда

а Ъ с d

число

а b с d

= ad-bc называется определителем матрицы " )) Доказательство. Площадь параллелограмма является линейной функцией вектора: если заменить первый вектор на сумму двух других, то соответствующие площади сложатся. Кроме того, если векторы переставить, то площадь изменит знак (по условию про ориентацию). Из этих двух фактов и из того, что площадь единичного квадрата равна единице, сразу вытекает, что

а b с d

- единственно возможная формула.

Это единственная функция, которая линейна по первому аргументу, линейна по второму, антисимметрична (меняет знак при их перестановке) и равна 1 на двух базисных векторах.

в алгебре эта наука называется теорией определителей. Чтобы повысить авторитет своей науки, алгебраисты скрывают, что их определители - это просто площади, объёмы и т. п., потому что, если определять их как ужасные многочлены, построенные по сложным правилам, вся наука об определителях становится абсолютно непонятной. Если же начать с того, что определителем называется площадь или объём, то все теоремы, какие есть в теории определителей, совершенно очевидны и мгновенно получают доказательства, которые я называю физическими, доказательствами в стиле Руссо.

Вернёмся к нашему алгоритму. Векторы и определяют единичный квадратик, и поэтому соответствующий определитель равен единице. Возьмём вектор ej. От ё к ё вращение в отрицательную сторону, внутри и на сторонах параллелограмма, натянутого на эти векторы, нет целых точек, поэтому этот определитель равен -1. Продолжая дальше, мы видим, что построение на каждом шаге такое: имеется параллелограмм (натянутый на векторы и ё), к одной его стороне (e j) мы прибавляем другую несколько раз, заменяем первую сторону на эту сумму (ё = е { + а-гё) и меняем стороны местами. Абсолютная величина площади не меняется, меняется только знак. Пусть iqk,Pk) - координаты вектора ё; qviPk - целые числа. 10