Второй способ нахождения линейного представления наибольшего общего делителя

ax + by = r

Исходные числа a и b тоже можно представить в виде линейной комбинации a и b:

Запишем это в общем виде

Разделим a на b с остатком.

Подставим вместо a и b их представления

Приведя подобные, получим

или

Повторяя подобное деление необходимое число раз, получим

(при этом коэффициенты для следующего остатка легко находятся через коэффициенты предыдущего остатка).

Пример.

Для контроля вычислений можно проверять для каждого столбца выполнение равенства . Например, 64·4 + 81·(-3) = 13.

Окончательно имеем: 64·19 + 81·(-15) = 1.

Свойства НОД

1. Если любое положительное число, то

.

Доказательство:

Обозначим . Имеем разложение:

.

Умножим это равенство на :

является делителем чисел и и является линейной комбинацией этих чисел. Следовательно, является наибольшим общим делителем этих чисел:

.

2. Если - любой делитель и , то

Согласно предыдущему:

.

Деля это равенство на , имеем:

.

В частности,

3. Если и взаимно просты и делится на , то делится на .

Действительно, так как и взаимно просты, то найдутся целые числа и , такие что

.

Умножим это равенство на и запишем так:

. (1)

Так как делится на , то левая часть равенства делится на . Поэтому и делится на .

4. Если и взаимно просты, то .

В силу равенства (1) всякий общий делитель и делит . Значит, делит . Но и делит . Поэтому .

Свойства НОК.

1.Всякое кратное чисел называется их общим кратным. Наименьшее из общих кратных называется наименьшим общим кратным чисел . Обозначается: .

2. Свойства кратного двух чисел.

Пусть .

Тогда .

Пусть - кратное и .

Тогда . Но кратно и . Поэтому

- целое число.

Но , поэтому .

Получаем формулу:

.

При любом целом будет кратным и .

При получаем наименьшее общее кратное:

.

Следовательно

Доказаны следующие теоремы.

1) Совокупность общих кратных двух чисел совпадает с совокупностью кратных наименьшего общего кратного этих чисел.

2) Это наименьшее кратное равно произведению чисел, поделенному на их наибольший общий делитель.

3. Наименьшее общее кратное трех и более чисел находится по следующему правилу.

.

Если числа и взаимно просты, то и .

И вообще, если - попарно просты, то