Алгебраическая операция. Коммутативные и ассоциативные операции. Смежные классы по подгруппе. Теорема Лагранжа, страница 4

Наибольший общий делитель. Алгоритм Евклида

1.Наибольший общий делитель.

Определение 1. Целое число  называется общим делителем целых чисел , если каждое из этих чисел делится на .

Определение 2. Целое число  называется наибольшим общим делителем чисел , если :

1)  является общим делителем этих чисел;

2)  делится на любой общий делитель чисел .

Теорема 1. Наибольший общий делитель чисел  определён однозначно с точностью до знака (т.е. если  и  наибольшие общие делители чисел , то либо , либо )

Доказательство. Пусть  и  - наибольшие общие делители чисел . Т.к.  - наибольший общий делитель, то он делится на любой общий делитель этих чисел, в частности на , т.е. . Точно так же получаем, что . Но тогда ,  - целое, и , поэтому , и аналогично, . Но эти неравенства одновременно имеют место лишь в случае .

Условимся всегда рассматривать положительное значение наибольшего общего делителя чисел . Обозначение: .

Пример. . Действительно, множество положительных делителей числа 135 есть , а для числа –180 такое множество имеет вид . Пересечение этих множеств . Число 45 является общим делителем чисел 135 и –180  и делится на все остальные общие делители этих чисел. Значит, . Заметим, что 45 – наибольший по величине положительный общий делитель чисел 135 и –180.

Упражнение. Для любых целых чисел  их наибольший общий делитель является  большим по величине положительным общим делителем. Доказать.

2. Алгоритм Евклида

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

Лемма 1. Если , то .

Доказательство. Т.к.  и , то  - общий делитель  и . Если  - любой общий делитель чисел  и , то он – делитель . Оба условия выполнены, значит .

Лемма 2. Если , где ,  и  отличны от нуля, то .

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

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

Равенство  доказано.

Алгоритм Евклида состоит в следующем. Сначала  делят на  (). если , то по лемме 1 . В противном случае . Делим  на . Если , то , но тогда и . Если  не делится на , то получится остаток . Делим  на  и т.д.

Остатки, получаемые в процессе деления, убывают и являются натуральными числами, значит, на некотором шаге получим деление без остатка.

Последний не равный нулю остаток является наибольшим общим делителем чисел  и . Сформулируем это утверждение в виде теоремы.

Теорема 2. Если

, ,

, ,

, ,

………………………….

, ,

,

то

Доказательство. По лемме 2 из первой строки получаем , из второй строки снова по лемме 2: , из третьей: , т.д. Значит . Но  и по лемме 1: .

Пример. Найдём .

Следствие из теоремы 2. Пусть , . тогда существуют такие целые числа  и , что . Другими словами, наибольший общий делитель двух чисел можно представить в виде линейной комбинации этих чисел с целыми коэффициентами.

Схема доказательства. Проходя последовательность равенств в алгоритме Евклида снизу вверх и выражая каждый раз  через всё более ранние остатки, получим выражение  через  и

Продолжение примера.

Цепные дроби

1.  Представление рациональных чисел конечными цепными дробями.

Пусть , , ,  - целые. Число  можно представить в виде дроби особого вида. Это представление получается из алгоритма Евклида. Применим алгоритм Евклида к числам  и . Получим:

,                             ,

,                            ,

,                           ,