2015-02-04
618
177=14·12+9, 0<9<14;
-64=14·(-5)+6, 0<6<14;
154=14·11+0, 0=0<14.
Наибольший общий делитель
Всякое целое число делящее одновременно целые a, b,…, l – называется их общим делителем. Наибольший из общих делителей чисел a, b,…, l обозначают (a, b,…, l). Если (a, b,…, l)=1, то числа a, b,…, l называются взаимно простыми. Если каждое из чисел a, b,…, l взаимно просто с каждым другим из них, то числа называют попарно простыми. Очевидно, что числа попарно простые всегда и взаимно простые. В случае же двух чисел понятия «попарно простые» и «взаимно простые» совпадают.
Пример.
Найти НОД чисел 6, 10, 15.
Решение.
Выпишем все делители числа 6
±6, ±3, ±2, ±1.
Выпишем все делители числа 10
±10, ±5, ±2, ±1.
Выпишем все делителя числа 15
±15, ±5, ±3, ±1.
Общим делителем у всех трех чисел являются числа ±1. Наибольшим является 1.
Ответ: (6,10,15)=1.
Теорема.
Если a кратно b, то совокупность общих делителей чисел a и b совпадает с совокупностью делителей одного b; в частности (a, b)= b.
Доказательство.
Всякий общий делитель чисел a и b является делителем и одного b. Так как a кратно b, то всякий делитель числа b является так же делителем числа a, то есть является общим делителем чисел a и b. Таким образом, совокупность общих делителей чисел a и b совпадает с совокупностью делителей одного b. А так как наибольший делитель числа b есть само b, то (a, b)= b.
|
|
|
Теорема.
Если
a=b·q+c, (1)
то совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и c; в частности (a,b)=(b,c).
Доказательство.
Из (1) следует, что всякий общий делитель чисел a и b делит так же и c, следовательно, является общим делителем чисел b и c. Обратно, то же равенство показывает, что всякий общий делитель b и c делит a и, следовательно, является общим делителем чисел a и b. Таким образом, общие делители чисел a и b те же, что и общие делители чисел b и c; в частности, должны совпадать и наибольшие из этих делителей, то есть
(a, b)=(b, c).
