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

ax + by = r

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

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

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

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

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

или

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

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

Пример.

q
x				-1		-5		-81
y					-3		-15

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

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

Свойства НОД

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

.

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

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

.

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

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

.

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

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

.

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

.

В частности,

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

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

.

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

. (1)

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

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

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

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

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

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

Пусть .

Тогда .

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

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

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

Но , поэтому .

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

.

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

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

.

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

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

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

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

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

.

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

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