АЛГОРИФМ ЕВКЛИДА И тШтныв ДРОВ“

воз

от ак. В этом и состоит главное значение рекуррентных формул

(8), на которых строится вся теория цепных дробей.

Теперь мы установим ряд важнейших свойств подходящих дро-

бей. Введём обозначение

— РАПА

В силу рекуррентных формул (8)

(р а -К-рк_ (q а

КА-1

К К 1.1

дк_1 ;

таким образом, все величины дк имеют одно и то же абсолютное

значение, а знаки их чередуются; замечая же, что в силу (7)

до —PoQ1 1

мы приходим к следующему важному предложению:

Теорема 1.

Отсюда, прежде всего, вытекает несократимость всех подходя-

щих дробей. В самом деле, если бы РК и делились на- одно и то

же число 1, то, очевидно, на него делилось бы и дк, что не-

возможно в силу теоремы 1.

а

несократима, то

Далее, если наша исходная дробь

и мы имеем:

п-1 qn-1a ¯ ( —

д

Таким образом (уже в четвёртый раз), мы доказали теорему о том,

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

ах -1—

имеет решения в целых х, у, на этот раз мы вместе с тем полу-

чили и такой метод отыскания этих решений, который на практике

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

а

в цепную дробь, и если

для этого надо разложить

1 )Прп-1•

то положить 1Y-1qn-1' У

Приме р. Пусть а мы находим:

1

1

1

5

6

1

4, у==—9, ах+Ьу