АЛГОРИФМ ЕВКЛИДА И цВПнЫВ ДРОБИ

295

При этом

кроме рациональных чисел и многочленов вида

только сами рациональные числа к простым многочленам не при-

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

единицу не причисляют к простым числам.

Соотношение (4), совершенно аналогичное соотношению между

делимым, делителем, частным и остатком в теории целых чисел,

может и здесь стать исходной точкой для построения алгорифма

Евклида и тем самым как бы в зародыше уже содержит в себе

всю теорию делимости. В случае целых чисел решающим моментом

было то, что при всяком делении остаток меньше делителя; именно

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

же многочленов у нас сте пе нь остатка всегда меньше степени

делителя. Но так как натуральное число, что бы оно ни означало,

при непрестанном понижении через конечное число шагов должно

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

Формальная сторона алгорифма протекает в столь полной ана-

логии со случаем целых чисел, что нам нет надобности воспроиз-

водить ее здесь в деталях- Мы делим А (х) на В (х), затем В (х)

на первый остаток, затем первый остаток на второй и т. д. Покуда

остаток не есть число (т. е. имеет положительную степень), степень

следующего остатка будет ниже степени данного; если же мы при-

дом к остатку степени () (т. е. к рациональному числу), то следую-

щий остаток равен нулю. Таким образом, во всех случаях рано

или поздно остаток обратится в нуль. Обозначая через R п (х)

последний остаток, отличный от нуля (он может, в частности, ока-

заться и числом), мы будем иметь, как и в случае целых чисел,

соотношения

Rn_9 (Х) (Х) (Х) + Rn (Х),

Rn_1 (Х) (Х) (Х).

Первое из них показывает, если учесть второе, что и (х)

делится на Rn(x); восходя же в цепи полученных равенств все

выше и выше, мы в конечном счёте убедимся, как в случае целых

чисел, что и оба исходных многочлена делятся на Rn(x). Итак,

R п (х) есть общий делитель двух данных многочленов. Но далее,

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

же, как и в случае целых чисел, убеждаемся, что всякий общий

делитель D (х) многочленов А (х) и В (х) есть вместе с тем дели-

тель и многочлена Rn(x). Таким образом, (х) есть такой общий

делитель многочленов А (х) и В (х), который делится на всякий

другой их общий делитель. Естественно поэтому называть R

наибольшим общим делителем многочленов А (х) и В(х); это тем

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

величине, .и поэтому обычное в теории целых чисел определение

наибольшего общего делителя не может быть перенесено в область