936 = 2-324 + 288, 288 = 8 • 36 ;

Н. О. Д. равен последнему остатку 36. Часто можно немного сократить работу, используя отрицательные остатки, если они численно меньгпе соответствуюгцих положительных остатков. В выгпеупомянутом примере последние три гпага можно заменить двумя:

936 = 3 • 324 - 36, 324 = 9 • 36.

Возможность использования отрицательных остатков основана на том, что рассуждение, примененное к уравнению (2), остается в силе, если это уравнение заменить на уравнение

а = qb - с.

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

7. Другое доказательство основной теоремы. Применим теперь алгоритм Евклида для того чтобы дать новое доказательство основной теоремы, которое не зависит от приведенного в п. 4.

Начнем с одного простого замечания; ввиду своей очевидности оно может даже показаться излигпним. Пусть а, Ь, n - произвольные натуральные числа. Наибольший общий делитель па и пЬ есть п раз взятый наибольший общий делитель а и Ь. Хотя это и кажется очевидным, читатель может убедиться, что дать прямое доказательство этого факта, не используя ни алгоритма Евклида, ни основной теоремы арифметики, нелегко.

Однако из алгоритма Евклида результат следует немедленно. Можно предполагать, что а > Ь, Если разделить па на пЬ, то отногпение будет тем же, что и раньгпе (т. е. а остаток заменится на ПС вместо с. Уравнение (2) заменится на равенство

па = q пЬ + ПС.

Это, конечно, то же определение, что и в п. 5; оно здесь повторено, потому что настоящее рассмотрение не зависит от предыдущего.

То же самое применимо и к дальнейшим уравнениям: все они просто умножатся на п. Наконец, последний остаток, даюш;ий Н. О. Д. чисел па и пЬ, равен п/г, где /г - Н. О. Д. а и Ь.

Мы используем этот простой результат для доказательства следуюгцей теоремы, которую часто называют теоремой Евклида (она встречается в качестве предложения 30 книги VH). Если простое делит произведение двух чисел, то оно должно делить одно из этих чисел (или, возможно, каждое из них). Предположим, что простое р делит произведение па, но не делит а. Единственными делителями р являются 1 и р, поэтому единственный обгций множитель р и а равен 1. Следовательно, по только что доказанной теореме Н. О. Д. и па равен п. Далее ясно, что р делит пр, кроме того, р делит па по предположению. Следовательно, р есть обгций делитель пр и па и потому делит п, ибо каждый обгций делитель двух чисел является также делителем их Н. О. Д. Таким образом, мы доказали, что если р делит па и не делит а, то оно должно делить п, а это и есть теорема Евклида.

Теперь уже можно доказать единственность разложения на простые. Предположим, что число п имеег два разложения, скажем,

п = pgr ... = pqr...,

где все числа Pj Qj ..., р, д, г, ... простые. Так как р делит произведение p[qr...), то оно должно делить р или qr... . Если р делит р то р = р, так как эти числа простые. Если р делит qr..., повторим предыдугцее рассуждение; в конце концов, мы придем к заключению, что р равно одному из простых р, д, г, ... . Мы сможем сократить на обгцее простое р оба представления и вернуться к какому-нибудь другому числу, стояш;ему в левой части равенства, скажем, к q. Таким образом, можно установить, что слева и справа одинаковые простые, и оба представления совпадают.

Этим получено доказательство единственности разложения на множители, упоминаемое в п. 4. Его достоинство в том, что оно получается из обгцей теории (теории алгоритма Евклида), а не искусственным приемом, использованным в п. 4. С другой стороны, оно длиннее и менее непосредственно.

8. Одно СВОЙСТВО Н. о. д. Из алгоритма Евклида можно вывести одно замечательное свойство Н. О. Д., вовсе не очевидное из его построения с помогцью разложения на простые. Это свойство таково: наибольший общий делитель h двух натуральных чисел а и b представляется как разность между некоторым кратным а и некоторым кратным Ь, т. е.

h = ах - Ьу где X и у - натуральные числа.

Так как а и b кратны /г, любое число вида ах - by также кратно /г; мы утверждаем, что найдутся такие значения х и у для которых ах - by в точности равно h.

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

а{х + х) = Ь{у + у), а этого можно достичь, взяв произвольное число т и определив х и у с помогцью равенств

X + х = тЬ У + у = met-Числа х и у будут натуральными числами, если т взять настолько больгпим, чтобы было тЬ > х и та > у. Если х и у определены таким образом, то

ах - by = by - ах.

Будем говорить, что число линейно зависит от а и Ь если оно представляется в виде ах - by. Только что установленный результат показывает, что линейная зависимость от а и Ь не наругпается, если а и b поменять местами.

Имеют место следуюгцие два простых факта о линейной зависимости. Если какое-нибудь число линейно зависит от а и Ь, то тем же свойством обладает и любое кратное этого числа; действительно,

к{ах - by) = а кх - b ку. Сумма двух чисел, линейно зависягцих от а и Ь, также линейно зависит от а и Ь, ибо

{ахг - Ьуг) + {ах2 - Ьу2) = a{xi + Х2) - b{yi + У2).