292
ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ
Если то будем делить Ь на и обозначим соответственно
через а, и частное и остаток этого деления, так что
(2)
если всё ещё не нуль, делим на и получаем аналогичным
образом:
7203 -1- (() r2)•
Так как ... то начатый таким образом про-
цесс после конечного числа шагов должен оборваться, т. е. рано
или поздно мы должны прийти к остатку, равному нулю. Пусть
так что
впервые
гпапн.
Тогда r есть наибольший общий делитель чисел а и Ь. Чтобы
в этом убедиться, покажем, прежде всего, что а и Ь делятся на rn.
В силу последнего написанного равенства rn_1 делится на ; но
тогда предпоследнее (не выписанное нами) равенство
(3)
показывает, что и rn_2 делится на rn. Продвигаясь далее (в обрат-
ном порядке) в цепи построенных нами равенств, мы убедимся, что
, 71, а в конечном счёте в силу равенств
на делятся и гп_з, •
числа а и Ь. Теперь покажем, что всякий общий дели-
тель d чисел а и Ь будет и делителем числа rn (этим, очевидно,
и будет установлено, что r есть н аи больгций общий делитель
чисел а и Ь). Для этого нам снова придётся пройти цепь построен-
— сверху вниз. Равенство (1),
ных нами равенств, но на этот раз
которое может быть записано в виде
— baj,
показывает нам, что всякий общий делитель d чисел а и Ь есть
вместе с тем делитель числа но в таком случае равенство (2)
аиалогичным образом показывает, что и делится на d, и т. д.
В конечном счёте мы придём к равенству (З); так как при этом
и rn_l на d уже будет устаиовлена, то это
делимость чисел
равенство и покажет нам, что rn делится на d.
Этот способ отыскаиия наибольшего общего делителя двух чисел
с помощью алгорифма Евклида в большинстве случаев оказывается
самым коротким и потому практически наиболее выгодным. С тео-
ретической стороны интересно отметить, что в только что прове-
денном рассуждении мы попутно доказали теорему о том, что вся-
кий общий делитель двух чисел есть делитель их наибольшего
общего делителя.
Теперь мы покажем, как на основе алгорифма Евклида может
быть построена вся теория делимости. Равенство (1) показывает