совершенных чисел. Первые пять четных совершенных чисел таковы:

6, 28, 496, 8128, 33 550 336. До сих пор мы рассматривали делители одного числа. Но можно также исследовать обгцие делители двух или более чисел. Любой обгций делитель двух чисел тип должен состоять в точности из тех простых, которые входят и в ш, и в п. Если таких простых нет, то ш и n не имеют обгцего делителя, отличного от 1, и называются взаимно простыми. Например, числа

2829 = 3-23-41 и 6850 = 2 • 5 • 137 взаимно просты.

Если тип имеют обгцие множители, то их наибольший общий делитель (Н. О. Д.) получится, если мы перемножим различные обгцие простые множители тип,, взяв каждый из них в наибольшей степени, делягцей и ш, и п.

Например, Н. О. Д. чисел

3132 = 2. 3 • 29 и 7200 = 2 • 3 • 5

равен 2 • 3 или 36. Ясно, что показатель каждого простого в Н. О. Д. равен меньшему из показателей, с которыми это простое входит в числа тип.

Очевидно также, что обгцие делители тип - это в точности все делители их Н. О. Д. Формулируя все эти утверждения, мы, конечно, пользуемся основной теоремой арифметики.

Аналогичная ситуация возникает и при рассмотрении общих кратных данных двух чисел. Среди всевозможных обгцих кратных имеется наименьшее общее кратное (Н. О. К.); оно равно произведению простых, входягцих хотя бы в одно из чисел т и n и взятых с наибольшим из двух показателей, с которыми они входят в эти числа. Например, для двух записанных выше чисел (3132 и 7200) Н. О. К. равно

2. 3 • 5 • 29.

Обш;ие кратные двух данных чисел суть всевозможные кратные их Н. О. К.

Эти рассмотрения легко переносятся и на случай более чем двух чисел. Важно отметить, что здесь имеются два вида возможной взаимной простоты. Говорят, что некоторые числа яв-

ляются взаимно простыми если не существует числа, большего 1, делящего каждое из них; эти числа называются попарно взаимно простыми если никакие два из них не имеют общего множителя, большего 1. Чтобы имел место первый случай, достаточно, чтобы не было простого, делящего все числа; а во втором случае нужно, чтобы ни одно простое не делило сразу два из этих чисел.

Имеется ряд простых теорем, которые кажутся очевидными, но в действительности очевидны лишь благодаря единственности разложения на простые. Например, если число делит произведение двух чисел и взаимно просто с одним из них, то оно должно делить другое. Действительно, если а делит be и взаимно просто с Ь, то разложение на простые а входит в разложение на простые Ьс, но не имеет общих множителей с b и поэтому содержится в разложении с.

6. Алгоритм Евклида. В предложении 2 книги VH Евклид дал систематический способ, или алгоритм для нахождения наибольшего общего делителя двух данных чисел. Этот алгоритм приводит к новому - по сравнению с изложенным в двух предыдущих пунктах - подходу к вопросам делимости. Поэтому мы начинаем изложение заново, не предполагая известным ничего, кроме определения отношения делимости.

Пусть аиЬ - два данных натуральных числа; предположим, что а > Ь, Мы попытаемся исследовать общие делители а и Ь. Если а делится на Ь, то общие делители аи b просто совпадают с делителями b и этим полностью характеризуются. Если а не делится на Ь, то а можно представить в виде суммы некоторого кратного b и остатка, меньшего чем Ь:

а = qb + е где е<Ь. (2)

Процесс «деления с остатком» выражает тот факт, что всякое а, не кратное Ь, должно встретиться где-то между двумя последовательными кратными Ь. Если а лежит между qb и (д + 1)6, то

а = qb + е где О < с < 6. Из равенства (2) следует, что любой общий делитель бис является также делителем а. Кроме того, любой общий делитель а и b делит с, так как е - а - qb.

Следовательно, общие делители а и Ь, если такие найдутся, совпадают с общими делителями b и с. Задача нахождения общих делителей а и b сводится поэтому к такой же задаче для чисел бис, соответственно меньших, чем а и Ь,

Суть алгоритма состоит в повторении этого рассуждения. Если b делится на с, то общие делители b и с состоят просто из всех делителей с. Если нет, то представим b в виде

b = ГС + где d < с. (3)

Общие делители b и с совпадают с общими делителями end.

Этот процесс может закончиться, только когда осуществится точная делимость, т. е. когда мы дойдем в последовательности а, Ь, с, ... до некоторого числа, являющегося делителем предыдущего. С другой стороны, ясно, что процесс должен окончиться, так как убывающая последовательность а, Ь, с, ... натуральных чисел не может быть бесконечной.

Предположим для определенности, что процесс закончится, когда мы дойдем до числа /г, являющегося делителем предыдущего числа д. Тогда последние два уравнения в ряду (2), (3), ... таковы:

f = vg + h, (4)

д = wh. (5)

Общие делители а и b являются также общими делителями b и с и d и так далее вплоть до д и h. Так как h делит д общие делители дик состоят просто из всех делителей h. Число h можно рассматривать как последний остаток в алгоритме Евклида перед осуществлением точной делимости, т. е. как последний ненулевой остаток.

Таким образом, мы доказали, что общие делители двух данных натуральных чисел а и b состоят из всех делителей некоторого натурального числа h (Н. О. Д. чисел а и Ь); это число является последним ненулевым остатком при применении алгоритма Евклида к числам а и Ь,

В качестве численного примера возьмем числа 3132 и 7200, которые уже были использованы в п. 5. Последовательные шаги алгоритма в этом случае таковы:

7200 = 2-3132 +936, 3132 = 3- 936 +324,