Нод и нок нескольких целых чисел.
Опр.:
Пусть
.
Целое число
называется общим делителем
,
если
Опр.:
Пусть
,
хотя бы одно из которых не равно нулю.
Наибольшим общим делителем
называется целое число
,
которое является общим делителем
и кратно любому их общему делителю.
Лемма1:
Если существует
,
то
.
,
.
Пусть
- общий делитель
.
Тогда
Лемма2:
Если
и
,
то
.
общий
делитель
,
но аналогично получаем
,
тогда
Лемма3:
Если
(не обязательно деление с остатком), то
1)
2)
.
Докажем сразу свойство 2, т.е. свойство
1 – частный случай свойства 2.
тогда
. Пусть
Алгоритм Евклида
Пусть
,
тогда
остаток равен нулю. Остатки от делений
– это целые неотрицательные числа,
которые удовлетворяют условию:
.
Эта последовательность не может быть
бесконечной. Значит, на каком-то шаге
деления получится остаток =0. Этим и
объясняется последнее равенство (1).
Равенство (1) – алгоритм Евклида.
Т:
ТЕОРЕМА ЕВКЛИДА: Последний не равный
нулю остаток в алгоритме Евклида равен
Докажем, что
- общий делитель
.
Следуем по алгоритму Евклида снизу
вверх.
,
но тогда
Пусть
,
докажем, что
.
По алгоритму Евклида сверху вниз
Следствие:
Если
,
то
существует и единственный с точностью
до знака.
Единственность следует из леммы 2. Если
,
то существование следует из условия
.
Если
,
то существование НОД следует из алгоритма
Евклида.
Пример: Найти НОД(525,231). 1) 525=231*2+63, 2) 231=63*3+42, 3) 63=42*1+21, 4) 42=21*2+0. Ответ: 21.
Т:
О ЛИНЕЙНОМ ВЫРАЖЕНИИ НОД: Если
,
то существуют целые
такие, что
.
Предположим, что
.
Пусть
Пример: Найти линейное выражение НОД(525,231)=21. 21=63+42*
*(–1)=63+(213+63*(–3))*(–1)=231*(–1)+63*(1+3)=231*(–1)+63*4=
=231*(–1)+5251+231*(–2)*4=231*(–1)+525*4+231*(–9);
21=524*4+231*(–9).
Св-во:
–
наименьшее натуральное число
,
которое представимо в виде
То,
что
выражается в виде
доказано ранее в теореме О ЛИНЕЙНОМ
ВЫРАЖЕНИИ.
Св-во:
–
наибольший общий делитель чисел
.
Пусть
,
– общий делитель чисел
.
,
т.к.
Наименьшее общее кратное
Опр.:
Пусть
целые ненулевые числа. Целое число
называют из общим кратным, если
Опр.:
.
Натуральное число
называют наименьшим общим кратным чисел
,
если оно является их общим кратным и
при этом оно делит любое общее кратное
чисел
и
.
Св-во:
Если
существует, то оно единственное.
общее
кратное
,
но при этом
.
Аналогично получаем, то
Св-во:
Если
существует, то оно является наименьшим
по величине натуральным числом, которое
кратно и
,
и
.
Пусть
,
– общее кратное чисел
,
тогда
Св-во.:
при любой комбинации знаков +/–.
Т.:
Формула связи НОК и НОД:
.
,
тогда
– общее кратное.
– общее кратное
,
,
но
,
тогда по свойству
Пример:
Найти
.
.
Следствие:
.
Очевидно.
Св-во:
Пусть
,
тогда
.
1)
2)
