4. Непрерывные дроби. Диофантовы уравнения

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

Например, в применении к числам 840 и 611 алгорифм Евклида дает ряд равенств

которые, между прочим, показывают, что (840, 611) = 1. Но из этих равенств, с другой стороны, получаются следующие:

Комбинируя последние равенства, мы приходим к следующему разложению числа

Выражение вида

где все числа а целые положительные, называется непрерывной дробью. Алгорифм Евклида дает метод для представления всякого рационального числа в виде такой непрерывной дроби.

Упражнение. Разложите в непрерывные дроби рациональные числа

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

где a, b, с - данные целые числа, и требуется найти целые решения х, у. Полное решение уравнения этого типа может быть найдено посредством алгорифма Евклида.

Прежде всего этот алгорифм позволит нам определить d = (a, b); затем, как мы знаем, при надлежащем выборе целых чисел k и l выполняется равенство

Итак, уравнение (8) имеет частное решение х = k, у = l в том случае, если с = d. Вообще, если с есть кратное d:

то из равенства (9) мы выводим

так что в этом случае уравнение (8) имеет частное решение х = х^* = kq, у = у^* = lq. Обратно, если уравнение (8) имеет при данном с хоть одно решение х, у, то с должно быть кратным d = (а, b): действительно, d делит и а и b, следовательно, должно делить с. Мы доказали, таким образом, что уравнение (8) имеет (хоть одно) решение в том и только в том случае, если с кратно (а, b).

Посмотрим теперь, как, зная одно решение х = х^*, у = у^* уравнения (8), определить все прочие решения. Пусть х = х', у = у' есть какое-либо другое решение; тогда х = х' - х^*, у = у' - у^* есть решение "однородного" уравнения

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

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

Обращаясь теперь к уравнению (10), мы видим, что общее его решение имеет вид где r - произвольное целое число. (Предоставляем доказательство читателю в качестве упражнения. Указание. Разделите на (а, b) и воспользуйтесь упражнением на стр. 72.) Затем окончательно будем иметь общее решение уравнения (8):

Подведем итоги. Линейное диофантово уравнение ах + by = с, где a, b и с - целые числа, имеет целые решения в том и только в том случае, если с кратно (а, b). В этом случае частное решение х = x^*, у = у^* может быть найдено посредством алгорифма Евклида, а общее имеет вид:

где r - произвольное целое число.

Примеры. Уравнение 3х + 6у = 22 не имеет целых решений, так как (3, 6) = 3 не делит 22.

Уравнение 7х + 11y = 13 имеет частное решение х = -39, у = 26, которое находится с помощью следующих вычислений:

Отсюда следует

Остальные решения даются формулами:

где r - произвольное целое число.

Упражнение. Решите диофантовы уравнения:

a) 3x - 4у = 29;

b) 11x + 12y = 58;

c) 153x - 34y = 51.