* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

292 х я ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ Если г ^>0 то будем делить Ь на г и обозначим соответственно через а и г частное и остаток этого деления, так что х а а * = \ г+г* если г веб ещё не нуль, делим образом: = г а + г а Г 1 а 3 3 а 3 т а (0 ^ г < г,); а (2) г х на г и получаем аналогичным а (0 ^ г < г ). 3 а Так как 6 ^ > Г | ^ г ^ > г ^ > ^ = 0 , то начатый таким образом про­ цесс после конечного числа шагов должен оборваться, т. е. рано или поздно мы должны прийти к остатку, равному нулю. Пусть впервые г | = 0, так что л + Тогда т есть наибольший общий делитель чисел а и Ь. Чтобы в этом убедиться, покажем, прежде всего, что а и Ь делятся на г . В силу последнего написанного равенства r _ делится на г ; но тогда предпоследнее (не выписанное нами) равенство п л n t л 'п-а = ' -1ап + ' в п л а л (3) показывает, что и г _ делится на г . Продвигаясь далее (в обрат­ ном порядке) в цепи построенных нами равенств, мы убедимся, что на г делятся и г _з, r _j, . . . , r а в конечном счёте в силу равенств (2) и (1) — числа а и й. Теперь покажем, что всякий общий дели­ тель d чисел а и b будет и делителем числа г (этим, очевидно, и будет установлено, что г есть н а и б о л ь ш и й общий делитель чисел а и Ь). Для этого нам снова придётся пройти цепь построен­ ных нами равенств, но на этот раз — сверху вниз. Равенство (1), которое может быть записано в виде п л rt Xt п п г =а х — Ьа и показывает нам, что всякий общий делитель d чисел а и b есть вместе с тем делитель числа г \ но в таком случае равенство (2) аналогичным образом показывает, что и г делится на d, и т. д. В конечном счёте мы придём к равенству (3); так как при этом делимость чисел г _ и г _, на d уже будет установлена, то это равенство и покажет нам, что г делится на d. Этот способ отыскания наибольшего общего делителя двух чисел с помощью алгорифма Евклида в большинстве случаев оказывается самым коротким и потому практически наиболее выгодным. С тео­ ретической стороны интересно отметить, что в только что прове­ дённом рассуждении мы попутно доказали теорему о том, что вся­ кий общий делитель двух чисел есть делитель их наибольшего общего делителя. Теперь мы покажем, как на основе алгорифма Евклида может быть построена вся теория делимости. Равенство (1) показывает х а л а л п