Наибольший общий делитель
Ключевые слова: НОД, НСД, лекции, найбільший спільний дільник.
Определение. Число d ∈ Z , делящее одновременно числа а , b , c , ... , k ∈ Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) .
Теорема (Свойство 1). Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv .
Доказательство. Рассмотрим множество P = { au + bv | u,v ∈ Z }. Очевидно, что P ⊆ Z , а знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , b , 0 ∈ P . Пусть x , y ∈ P и y ≠ 0 . Тогда остаток от деления x на y принадлежит P . Действительно: x = yq + r , 0 ≤ r < y , r = x – yq = ( au1 + bv1 ) – ( au2 + bv2 ) q = a ( u1 – u2q )+ b ( v1 – v2 q ) ∈ P . Пусть d ∈ P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r1 , 0 ≤ r1 < d , a ∈ P , d ∈ P , значит r1 ∈ P , следовательно r1 = 0. Аналогичными рассуждениями получается, что b делится на d , значит d - общий делитель a и b . Далее, раз d ∈ P , то d = au0 + bv0 . Если теперь d1 - общий делитель a и b , то d1 | ( au0 + bv0 ), т.е. d1 | d . Значит d ≥ d1 и d - наибольший общий делитель.
Свойство 2. Для любых целых чисел а и k , очевидно, справедливо: ( а , kа ) = а ; (1, а ) = 1.
Свойство 3. Если a = bq + c , то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и с , в частности, ( a , b ) = ( b , c ). Доказательство. Пусть d | a , d | b , тогда d | c . Пусть d | c , d | b , тогда d | a .
Свойство 4. Пусть a , b и m - произвольные целые числа. Тогда ( am , bm ) = m ( a , b ). Доказательство. Если d - наибольший общий делитель чисел а и b , то dm | am и dm | bm , т.е. dm - делитель am и bm . Покажем, что dm - наибольший общий делитель этих чисел. Поскольку d - наибольший общий делитель чисел а и b , то, согласно свойству 1, для некоторых целых чисел u и v выполнено равенство d = au + bv . Умножив это равенство на m , получим равенство: dm = amu + bmv . Видно, что если некоторое число s делит одновременно am и bm , то s обязано делить и dm , т.е. s ≤ dm , следовательно, dm - наибольший общий делитель.
Свойство 5. Пусть s - делитель а и b . Тогда:
Определение. Число d ∈ Z , делящее одновременно числа а , b , c , ... , k ∈ Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) .
Теорема (Свойство 1). Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv .
Доказательство. Рассмотрим множество P = { au + bv | u,v ∈ Z }. Очевидно, что P ⊆ Z , а знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , b , 0 ∈ P . Пусть x , y ∈ P и y ≠ 0 . Тогда остаток от деления x на y принадлежит P . Действительно: x = yq + r , 0 ≤ r < y , r = x – yq = ( au1 + bv1 ) – ( au2 + bv2 ) q = a ( u1 – u2q )+ b ( v1 – v2 q ) ∈ P . Пусть d ∈ P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r1 , 0 ≤ r1 < d , a ∈ P , d ∈ P , значит r1 ∈ P , следовательно r1 = 0. Аналогичными рассуждениями получается, что b делится на d , значит d - общий делитель a и b . Далее, раз d ∈ P , то d = au0 + bv0 . Если теперь d1 - общий делитель a и b , то d1 | ( au0 + bv0 ), т.е. d1 | d . Значит d ≥ d1 и d - наибольший общий делитель.
Свойство 2. Для любых целых чисел а и k , очевидно, справедливо: ( а , kа ) = а ; (1, а ) = 1.
Свойство 3. Если a = bq + c , то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и с , в частности, ( a , b ) = ( b , c ). Доказательство. Пусть d | a , d | b , тогда d | c . Пусть d | c , d | b , тогда d | a .
Свойство 4. Пусть a , b и m - произвольные целые числа. Тогда ( am , bm ) = m ( a , b ). Доказательство. Если d - наибольший общий делитель чисел а и b , то dm | am и dm | bm , т.е. dm - делитель am и bm . Покажем, что dm - наибольший общий делитель этих чисел. Поскольку d - наибольший общий делитель чисел а и b , то, согласно свойству 1, для некоторых целых чисел u и v выполнено равенство d = au + bv . Умножив это равенство на m , получим равенство: dm = amu + bmv . Видно, что если некоторое число s делит одновременно am и bm , то s обязано делить и dm , т.е. s ≤ dm , следовательно, dm - наибольший общий делитель.
Свойство 5. Пусть s - делитель а и b . Тогда:
Доказательство.
Свойство 6. Очевидно теперь, что
Свойство 7. Если ( a , b ) = 1, то ( ac , b ) = ( c , b ). Доказательство . Пусть ( c, b ) = d . Имеем: d | b , d | c , следовательно d | ac , т.е. d - делитель ас и b . Пусть теперь ( ac , b ) = s . Имеем: s | b , s | ac , s - делитель b , т.е. либо s = 1, либо s не делит а . Это означает, что s | c , значит s | d . Итак, d и s делятся друг на друга, т.е. d = s .
Похожие материалы:
Примеры решений задач
Готовые работы