АЛГОРИФМ ЕВКЛИДА И ЦЕПНЫЕ ДРОБИ

297

ному в главе 1, мы легко приходим к теореме, аналогичной тео-

реме 2; отсюда же в точности так же, как там, может быть уста-

новлена однозначная (с точностью до постоянных множителей)

разложимость многочленов на простые множители, служащая фунда-

ментом всей теории делимости.

Упомянем, наконец, что теорема Евклида о существовании беско-

нечного множества простых чисел вместе с её доказательством

легко переносится в. нашу новую область. Впрочем, существование

бесконечного множества абсолютно простых многочленов ещё проще

вытекает из того, что все двучлены первой степени, как читатель

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

гочленами.

S 9. Элементарная теория цепных дробей

Мы возвращаемся в область целых чисел. Выпишем снова непь

равенств, с помощью которых мы находим наибольший общий де-

литель чисел а и Ь:

где

а ba1 -4- П,

паз + а,

Гп 9 rn—10n

Т = rnan+1'

(5)

Мы можем переписать эту цепь в виде равносильной системы

равенств

rn—1

= ап+1.

В этом виде каждое из нацшх равенств описывает простую

арифметическую операцию: исключение целой части из неправильной