Элементы алгебры: комплексные числа, системы линейных уравнений, многочлены. Ильин С.Н. - 58 стр.

      3. НОД (ta, tb) = t НОД (a, b).
      4. НОД (НОД (a, b), c) = НОД (a, НОД (b, c)).
      Докажем свойство 3 (проверка остальных свойств предлагается
в качестве упражнения). Введем обозначения: НОД (a, b) = d,
НОД (ta, tb) = f . Так как d | a, d | b, то td | ta, td | tb. Следовательно,
td | f , тем самым, f = tdg для некоторого g . Тогда tdg = f | ta, что
с учетом целостности влечет dg | a, аналогично, tdg = f | tb влечет
dg | b. Значит, dg | НОД (a, b) = d, откуда g | 1. Получаем, что f и td —
ассоциированные элементы.C
      Элементы a, b ∈ R, для которых НОД (a, b) = 1, называются
взаимно простыми.
      Двойственным образом к НОД определяется понятие наименьшего
общего кратного (НОК): m = НОК (a, b), если
      1’) a | m, b | m;
      2’) a | c, b | c ⇒ m | c.
Предложение 6.3 Пусть R — целостное кольцо, a, b ∈ R. Если
d = НОД (a, b), m = НОК (a, b), то ab = md.
Доказательство. Если a = 0 или b = 0, то m = 0 и равенство
ab = md тривиально верно, поэтому можно считать, что a 6= 0, b 6= 0
и, следовательно, d 6= 0.
        Согласно условию верны равенства a = a0 d, b = b0 d, откуда ab =
(a0 b0 d)d. Положим m = a0 b0 d и докажем, что m = НОК (a, b). Имеем:
a | ab0 = a0 b0 d = m и, аналогично, b | a0 b = a0 b0 d = m, тем самым
выполнено условие 1’) определения НОК.
        Пусть теперь a | c и b | c. Тогда с учетом свойства 3 НОД из
ab | ca, ab | cb выводим md = ab | НОД (ca, cb) = c НОД (a, b) = cd.
Таким образом, md | cd, следовательно, m | c, то есть, для m выполнено
и условие 2’).C
        Согласно доказанному предложению для вычисления НОК
элементов достаточно найти их НОД и поделить на него произведение
исходных элементов. В кольце K[X] для вычисления НОД (a, b) обычно
используют метод, называемый алгоритмом Евклида. В силу
свойства 2 НОД можно ограничиться случаем, когда a и b отличны от
нуля.
        Введем обозначения a = r−1 , b = r0 и положим k = 0.

                                     56