Метка: линейное представление НОД

НОД двух многочленов

Для многочленов, также как и для множества целых чисел, можно определить наибольший общий делитель (НОД) и наименьшее общее кратное.

При определении понятия НОД, для начала необходимо ознакомиться с понятием общего делителя двух многочленов. Заранее для краткости и удобства договоримся, что в дальнейшем под понятиями общего делителя и наибольшего общего делителя мы будем подразумевать их аналоги на множестве P[x].

Определение 1 (общий делитель)

Пусть даны f(x),g(x)∈P[x], причем f(x),g(x)≠0. Тогда общим делителем этих многочленов будет являться многочлен d(x)∈P[x] при условии, что f(x)⋮d(x) и g(x)⋮d(x).

Замечание. Любая ненулевая константа является общим делителем для любых двух многочленов.

Пример 1. Пусть f(x)=x8−1, g(x)=x4−1. Для того, чтобы найти общие делители разложим эти многочлены по формуле разности квадратов: f(x)=x8−1=(x4−1)(x4+1)=(x2−1)(x2+1)(x4+1)==(x−1)(x+1)(x2+1)(x4+1),

g(x)=x4−1=(x2−1)(x2+1)=(x−1)(x+1)(x2+1).
Как мы видим, общими делителями являются (x−1), (x+1) и (x2+1).

Было бы некорректно применять такое определение НОД, по которому наибольшим общим делителем двух многочленов является их общий делитель наибольшей степени, т.к. оно является слишком обобщенным. Поэтому мы введём такое понятие:

Определение 2 (наибольший общий делитель)

Пусть даны f(x),g(x)∈P[x], причем f(x),g(x)≠0. Тогда многочлен d(x)∈P[x] будет являться их наибольшим общим делителем, если сам будет являться их общим делителем, который делится на любые другие общие делители f(x) и g(x). Обозначение: d(x)=(f(x),g(x)) — НОД для f(x),g(x)∈P[x].

Замечание. Пусть f(x)=0 и g(x)=0. Тогда НОД(f(x),g(x))=0.

Лемма. НОД определен (если существует) с точностью до постоянного ненулевого множителя.

Пусть даны f(x),g(x)∈P[x], для которых d1(x),d2(x)∈P[x] — два НОД.

Тогда, по определению, d1(x)⋮d2(x) и d2(x)⋮d1(x). По свойству делимости (f(x)⋮g(x)∧g(x)⋮f(x)⇔∃c∈P∗:f(x)=c⋅g(x)) d1(x)=c1⋅d2(x), c1∈P∗, c1=const.

Пусть ∃c2∈P∗, c2=const. Тогда, если d2(x) — общий делитель для f(x) и g(x) (по определению), то и c2⋅d2(x) — тоже общий делитель. Соответственно, если d2(x) — НОД, т.е. делится на любой другой общий делитель (по определению), то и c2⋅d2(x) — тоже является НОД.

Пример 2. Возьмём те же f(x) и g(x), что и в примере 1: f(x)=x8−1, g(x)=x4−1. Чтобы найти НОД этих многочленов, разложим их так же, как и в предыдущем примере: f(x)=x8−1=(x4−1)(x4+1)=(x2−1)(x2+1)(x4+1)==(x−1)(x+1)(x2+1)(x4+1),

g(x)=x4−1=(x2−1)(x2+1)=(x−1)(x+1)(x2+1).
Очевидно, что наибольшим общим делителем будет являться (x4−1).

Теперь разберем способ получения НОД двух многочленов. Находить его можно таким же способом, что и для двух целых чисел, — алгоритмом Евклида (или алгоритмом последовательного деления).

Замечание. С помощью этого алгоритма доказывается существование НОД двух многочленов.

Пример 3. Построим НОД для двух многочленов с помощью алгоритма Евклида. Пусть даны f(x)=x4+x3−3x2−4x−1 и g(x)=x4+x3−x−1.

x4 + x3 − 3x2 − 4x − 1  
x4 + x3     − x − 1  
      − 3x2 − 3x      
x4 + x3 − x − 1
1            
  x4 + x3 − x − 1  
  x4 + x3          
        − x − 1  
− 3x2 − 3x      
− 13x2          
        − 3x2 − 3x  
        − 3x2 − 3x  
              0  
− x − 1      
3x            

Последний ненулевой остаток и будет являться НОД этих многочленов, т.е. НОД(f(x),g(x))=−x−1.

Может возникнуть случай, когда НОД двух многочленов будет равен 1. При этом говорят, что многочлены являются взаимно простыми.

Пример 4. Пусть даны f(x)=−x3+x−1 и g(x)=x−2. Найдем их НОД. Для удобства умножим f(x) на −1, получим f(x)=x3−x+1.

x3 + 0x2 − x + 1  
x3 + 2x2          
    2x2 − x + 1  
    2x2 − 4x      
        3x + 1  
        3x − 6  
            7  
x − 2        
x2 + 2x + 3    

Таким образом, многочлен q(x)=x2+2x+3 — частное деления многочленов, а r(x)=7 — остаток. Дальнейшее деление можно не продолжать, т.к. и так понятно, что в следующем остатке мы получим 0, т.е. 7 будет последним ненулевым остатком, после умножения которого на 17, НОД(f(x),g(x))=1. Следовательно, f(x) и g(x) — взаимно простые.

Также стоит упомянуть и линейное представление НОД:d(x)=f(x)⋅u(x)+g(x)⋅v(x),

где f(x),g(x),u(x),v(x)∈P[x], а d(x)=(f(x),g(x)).

Примеры решения задач

  1. Определить наибольший общий делитель многочленов:
    1. f(x)=x2−9 и g(x)=x3−27;
    2. f(x)=x5+x3+x и g(x)=x4+x3+x;
    Решение (пример a.)

    Решение (пример b.)
  2. Пользуясь алгоритмом Евклида, убедиться в том, что многочлены f(x) и g(x) взаимно простые, и подобрать u(x) и v(x) так, чтобы f(x)⋅u(x)+g(x)⋅v(x)=1: f(x)=3x3−2x2+x+2,g(x)=x2−x+1.

    Решение
  3. Пользуясь алгоритмом Евклида, найти многочлены u(x) и v(x) такие, чтобы они удовлетворяли равенству f(x)⋅u(x)+g(x)⋅v(x)=d(x), где d(x) — НОД многочленов f(x) и g(x): f(x)=x4+2x3−x2−4x−2,g(x)=x4+x3−x2−2x−2.

    Решение

Тест на проверку знаний по теме «НОД двух многочленов»

  1. Фадеев Д. К. Лекции по алгебре: Учебное пособие для вузов. — М., Наука. Главная редакция физико-математической литературы, 1984. — 416 с., стр. 168-170
  2. Курош А. Г. Курс высшей алгебры — И., Наука. Главная редакция физико-математической литературы, 1968. — 431 с., стр. 137-141
  3. Личный конспект, составленный на основе лекций Белозерова Г.С.