Уравнения первой степени с двумя неизвестными.

Некоторые сведения и теории целых чисел.

Пусть - рациональное число, . Пусть . Используя алгоритм Евклида, последовательно получаем:

…

Соединяя вместе полученные формулы, получаем:

(1.1)

Определение 2.1. Выражение, стоящее в правой части равенства (1.1), называется конечной цепной дробью.

Обозначим .

Замечание. Числа называется коэффициентами цепной дроби (1.1). Из построения ясно, что коэффициент -целое число, а остальные – натуральные числа.

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

Более конкретно, подходящие дроби соответствующего порядка – это дроби вида

, , и т.д.

Ясно, что последняя подходящая дробь есть число .

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

Теорема 1.1. Для подходящей дроби k-го порядка имеет место следующая рекуррентная формула:

= (1.2)

Для вычисления подходящих дробей удобно принимать алгоритм, основанный на следующем правиле (см. [9]). Пусть - первые коэффициенты цепной дроби (1.1). Образуем матрицы второго порядка

, , …, .

Справедливо соотношение:

· · …· = (1.3)

Т.е. перемножив указанные матрицы, мы получаем «в перевернутом виде» подходящие дроби и .

Пример.

Найдем все подходящие дроби числа . С помощью алгоритма Евклида раскладываем в цепную дробь:

= [2; 1; 3; 4; 2]

, , , ,

Находим подходящие дроби по формуле (1.3):

· = , , .

Далее,

· = , т.е. ,

= , т.е. .

Рассмотрим теперь основные свойства подходящих дробей.

1°. Знаменатели подходящих дробей – натуральные числа и образуют неубывающую последовательность, которая со второго члена становится строго возрастающей.

Доказательство.

Действительно,

, где .

Значит,

2°. Числители и знаменатели двух соседних подходящих дробей связаны соотношением:

. (1.4)

Доказательство .

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

откуда и следует формула (1.4).

3°. Все подходящие дроби несократимы.

Доказательство.

Действительно, если , то согласно (1.4): . Следовательно, .

4°. Подходящие дроби четного порядка образуют возрастающую, а нечетного - убывающую последовательности.

Пользуясь формулами (1.2) и (1.4), получаем:

= .

Таким образом, если четное, получаем , если нечетное, получаем

5°. Каждая подходящая дробь четного порядка меньше соседних подходящих дробей и .

Доказательство.

Рассмотрим разность

то есть . Заменяя на , получаем

, то есть .

Следствие. Каждая подходящая дробь нечетного порядка больше соседних подходящих дробей.

6°. Любая подходящая дробь четного порядка меньше любой подходящей дроби нечетного порядка.

Доказательство.

Рассмотрим подходящие дроби и Пусть сначала . Тогда, на основании свойств 4° и 5°, имеем

Пусть теперь . Тогда применяем свойство 4° и следствие, имеем

> > .

Итак, при любом соотношении между и имеем .

Суммируя информацию о поведении подходящих дробей, мы получаем следующее важное свойство.

7°. Если - положительная дробь, то при ее разложении в цепную дробь четные подходящие дроби образуют возрастающие приближения по недостатку, а нечетные - убывающие приближения по избытку.

Доказательство.

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

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

Рассмотрим теперь вопрос о том, насколько хорошо подходящие дроби приближают число .

8°. Если - положительная дробь и - подходящая дробь порядка, то .

Доказательство.

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

= .

На основании свойства 1° получаем , более того, заметим, что при это неравенство является строгим.

Неопределенные уравнения.

Применяя теперь изученные цепные дроби к решению уравнений вида

a b , (1.5)

где a, b, c- целые числа, , . В качестве равнения (1.5) мы будем рассматривать целые числа x, y. Уравнение типа (1.5) называется неопределенными (или диофантовыми). Такое название связано с тем, что как мы видим, в случае разрешимости уравнения (1.5) имеет бесконечно много решений.

Рассмотрим вопрос о разрешимости уравнения (1.5).

Теорема 1.2. Для существования решения уравнения (1.5) необходимо и достаточно, чтобы c d=(a, b).

Доказательство.

Необходимость. Если ( ) – некоторое решение (1.5), то

, но тогда и c d.

Достаточность. Пусть c d, тогда, сократив коэффициенты a, b, c на d, мы можем считать, что (a, b)=1.

Без ограничения общности полагаем, что . Рассмотрим сначала случай . Разложим в цепную дробь и пусть -соответствующие подходящие дроби. Так как дробь несократима, получаем , . В силу (1.4) имеем , откуда , или . Умножая обе части последнего равенства на , получаем

т.е. числа , , дают решение уравнения (1.5).

Если , то найдем решение ( ) уравнения ax+b’y=c,

где b’=- b. Тогда ( ) будет решением исходного уравнения.

Следствие. Если (a, b)=1, то уравнение (1.5) разрешимо.

Рассмотрим вопрос о нахождении общего решения уравнения (1.5).

Теорема 1.3. Пусть (a, b)=1 и ( ) – некоторое решение уравнение (2.5). Тогда общее решение уравнения (1.5) может быть записано в виде

, , (1.6)

Доказательство.

Необходимость. Покажем, что любая пара чисел (x, y), удовлетворяющих (1.6), дает решение (1.5). Действительно,

a( )+b = a +b .

Достаточность. С другой стороны, пусть(x, y) - произвольное решение уравнения (1.5).

Тогда имеем соотношения

a b ,

a +b .

Вычитая из первого равенства второе, получим

a( +b( )=0, или

a( =-b( ). (1.7)

Поскольку (a, b)=1, левая часть делится на a, то делится на a, т.е. , или , .

Подставляя значение в (1.7), получаем:

a( )=-b , и поэтому

=- , x= - ,

Таким образом, произвольное решение (x, y) уравнения (1.5) имеет вид (1.6). Полученный результат полностью решает вопрос о нахождении всех целочисленных решений уравнения первой степени с двумя неизвестными.

Пример.

Решите в целых числах уравнение