Целые числа и решетки.

Вот две задачи.

1. Даны два взаимно простых целых числа и . Найти пары целых чисел и таких, что

            (1)

2. В плоской квадратной решетке через два узла проведена прямая. Найти узлы, которые находятся на минимальном (не равном нулю) расстоянии от этой прямой.

Это разные формулировки одной и той же задачи. Прежде чем читать дальше попробуйте сами разобраться в этом и найти решение задачи.

Эквивалентность задач.

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

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

Т.е. и взаимно простые целые числа. Координаты искомого узла (также целые числа) обозначим вектором .

Расстояние от искомого узла до прямой равно

            (2)

Здесь S - площадь параллелограмма, построенного на векторах и . Она равна модулю векторного произведения:

            (3)

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

Решение задачи.

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

Не ограничивая общность, положим

            (4)

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

Однозначно определяется следующая цепочка разложений (все вводимые ниже числа являются целыми и положительными):

            (5)

где

            (6)

Методом математической индукции нетрудно доказать, что

            (7)

            (8)

В силу (6) при каком-то k = n получим и цепочка (5) обрывается. Учитывая (7) и (8) при k = n, имеем

            (9)

Т.е. b₁ = A_n , b₂ = D_n        (10)

является решением уравнения (1).

Нетрудно показать, что множество пар вида

            (11)

где k - любое целое число, составляет полный набор решений уравнения (1). При этом (10) выделяется тем, что приводит к минимуму модуля вектора b. .Более того, можно доказать, что

            (12)

при всех целых k. Равенство в (12) будет лишь при .

Обобщения.

Геометрическая интерпретация дает больший простор для модификаций и обобщений задачи. Ниже приведен ряд возможных вариантов.

1. Прямая может проходить только через один узел решетки ( отношение не является рациональным числом). Задача приобретает смысл, если ввести какие-то ограничения на вектор . Например, искать ближайший узел внутри заданного круга.
2. Решетка не является квадратной.
3. Трехмерная кубическая решетка. Можно ли найти полное решение в общем случае? Попробуйте найти решение для частных случаев. Докажите, используя свойства трехмерной элементарной ячейки, что для любой тройки целых чисел , не имеющих общего делителя, найдутся две тройки целых чисел и таких, что

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