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

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

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

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

Пусть даны $f\left(x\right), g\left(x\right) \in P\left[x\right],$ причем $f\left(x\right), g\left(x\right) \neq 0.$ Тогда общим делителем этих многочленов будет являться многочлен $d\left(x\right) \in P\left[x\right]$ при условии, что $f\left(x\right) \vdots d\left(x\right)$ и $g\left(x\right) \vdots d\left(x\right).$

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

Пример 1. Пусть $f\left(x\right) = x^8-1,$ $g\left(x\right) = x^4-1.$ Для того, чтобы найти общие делители разложим эти многочлены по формуле разности квадратов: $$f\left(x\right) = x^8-1 = \left(x^4-1\right)\left(x^4 + 1\right) = \left(x^2-1\right)\left(x^2 + 1\right)\left(x^4 + 1\right) =\\= \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right)\left(x^4 + 1\right),$$ $$g\left(x\right) = x^4-1 = \left(x^2-1\right)\left(x^2 + 1\right) = \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right).$$Как мы видим, общими делителями являются $\left(x-1\right),$ $\left(x + 1\right)$ и $\left(x^2 + 1\right).$

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

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

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

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

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

Пусть даны $f\left(x\right), g\left(x\right) \in P\left[x\right],$ для которых $d_1\left(x\right), d_2\left(x\right) \in P\left[x\right]$ — два НОД.

Тогда, по определению, $d_1\left(x\right) \vdots d_2\left(x\right)$ и $d_2\left(x\right) \vdots d_1\left(x\right).$ По свойству делимости $\left(f\left(x\right) \vdots g\left(x\right) \wedge g\left(x\right) \vdots f\left(x\right) \Leftrightarrow \exists c \in P^*: f\left(x\right) = c \cdot g\left(x\right)\right)$ $d_1\left(x\right) = c_1 \cdot d_2\left(x\right),$ $c_1 \in P^*,$ $c_1 = \text{const}.$

Пусть $\exists c_2 \in P^*,$ $c_2 = \text{const}.$ Тогда, если $d_2\left(x\right)$ — общий делитель для $f\left(x\right)$ и $g\left(x\right)$ (по определению), то и $c_2 \cdot d_2\left(x\right)$ — тоже общий делитель. Соответственно, если $d_2\left(x\right)$ — НОД, т.е. делится на любой другой общий делитель (по определению), то и $c_2 \cdot d_2\left(x\right)$ — тоже является НОД.

Пример 2. Возьмём те же $f\left(x\right)$ и $g\left(x\right),$ что и в примере 1: $f\left(x\right) = x^8-1,$ $g\left(x\right) = x^4-1.$ Чтобы найти НОД этих многочленов, разложим их так же, как и в предыдущем примере: $$f\left(x\right) = x^8-1 = \left(x^4-1\right)\left(x^4 + 1\right) = \left(x^2-1\right)\left(x^2 + 1\right)\left(x^4 + 1\right) =\\= \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right)\left(x^4 + 1\right),$$ $$g\left(x\right) = x^4-1 = \left(x^2-1\right)\left(x^2 + 1\right) = \left(x-1\right)\left(x + 1\right)\left(x^2 + 1\right).$$Очевидно, что наибольшим общим делителем будет являться $\left(x^4-1\right).$

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

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

Пример 3. Построим НОД для двух многочленов с помощью алгоритма Евклида. Пусть даны $f\left(x\right) = x^4+x^3-3x^2-4x-1$ и $g\left(x\right) = x^4+x^3-x-1.$

$x^4$ $+$ $x^3$ $-$ $3x^2$ $-$ $4x$ $-$ $1$  
$x^4$ $+$ $x^3$     $-$ $x$ $-$ $1$  
      $-$ $3x^2$ $-$ $3x$      
$x^4$ $+$ $x^3$ $-$ $x$ $-$ $1$
$1$            
  $x^4$ $+$ $x^3$ $-$ $x$ $-$ $1$  
  $x^4$ $+$ $x^3$          
        $-$ $x$ $-$ $1$  
$-$ $3x^2$ $-$ $3x$      
$-$ $\frac{1}{3}x^2$          
        $-$ $3x^2$ $-$ $3x$  
        $-$ $3x^2$ $-$ $3x$  
              $0$  
$-$ $x$ $-$ $1$      
$3x$            

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

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

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

$x^3$ $+$ $0x^2$ $-$ $x$ $+$ $1$  
$x^3$ $+$ $2x^2$          
    $2x^2$ $-$ $x$ $+$ $1$  
    $2x^2$ $-$ $4x$      
        $3x$ $+$ $1$  
        $3x$ $-$ $6$  
            $7$  
$x$ $-$ $2$        
$x^2$ $+$ $2x$ $+$ $3$    

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

Также стоит упомянуть и линейное представление НОД:$$d\left(x\right) = f\left(x\right) \cdot u\left(x\right) + g\left(x\right) \cdot v\left(x\right),$$ где $f\left(x\right), g\left(x\right), u\left(x\right), v\left(x\right) \in P\left[x\right],$ а $d\left(x\right) = \left(f\left(x\right), g\left(x\right)\right).$

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

  1. Определить наибольший общий делитель многочленов:
    1. $f\left(x\right) = x^2-9$ и $g\left(x\right) =x^3-27;$
    2. $f\left(x\right) = x^5+x^3+x$ и $g\left(x\right) = x^4+x^3+x;$
    Решение (пример a.)

    Для построения НОД воспользуемся алгоритмом Евклида. Так как степень многочлена $g\left(x\right)$ больше степени многочлена $f\left(x\right),$ то мы будем делить $g\left(x\right)$ на $f\left(x\right).$

      $x^3$ $+$ $0x^2$ $+$ $0x$ $-$ $27$  
      $x^3$     $-$ $9x$      
              $9x$ $-$ $27$  
    $x^2$ $-$ $9$        
    $x$            

    После первого деления мы получили остаток $r_1\left(x\right) = 9x-27.$ Для удобства мы можем умножить его на $\displaystyle\frac{1}{9}.$ Получим $r_1\left(x\right) = x-3.$

    Продолжаем наше деление, только в этот раз мы делим многочлен $g\left(x\right)$ на остаток $r_1\left(x\right).$

          $x^2$ $+$ $0x$ $-$ $9$  
          $x^2$ $-$ $3x$      
              $3x$ $-$ $9$  
              $3x$ $-$ $9$  
                  $0$  
    $x$ $-$ $3$        
    $x$ $+$ $3$        

    Теперь в остатке мы получили $0$ — значит деление закончено. Последний ненулевой остаток и будет являться НОД многочленов $f\left(x\right)$ и $g\left(x\right).$ В нашем случае это $x+3.$

    Ответ: НОД$\left(f\left(x\right), g\left(x\right)\right) = x+3.$

    [свернуть]

    Решение (пример b.)

    Также как и в прошлом примере, воспользуемся алгоритмом последовательного деления.

    $x^5$ $+$ $0x^4$ $+$ $x^3$ $+$ $0x^2$ $+$ $x$  
    $x^5$ $+$ $x^4$     $+$ $x^2$      
      $-$ $x^4$ $+$ $x^3$ $-$ $x^2$ $+$ $x$  
      $-$ $x^4$ $-$ $x^3$     $-$ $x$  
            $2x^3$ $-$ $x^2$ $+$ $2x$  
    $x^4$ $+$ $x^3$ $+$ $x$    
    $x$ $-$ $1$        

    В результате первого деления мы получили остаток $r_1\left(x\right) = x-1.$ Продолжаем деление.

      $x^4$ $+$ $x^3$ $+$ $0x^2$ $+$ $x$  
      $x^4$ $-$ $\frac{1}{2}x^3$ $+$ $x^2$      
          $\frac{3}{2}x^3$ $-$ $x^2$ $+$ $x$  
          $\frac{3}{2}x^3$ $-$ $\frac{3}{4}x^2$ $+$ $\frac{3}{2}x$  
            $-$ $\frac{1}{4}x^2$ $-$ $\frac{1}{2}x$  
    $2x^3$ $-$ $x^2$ $+$ $2x$    
    $\frac{1}{2}x$ $+$ $\frac{3}{4}$        

    Для удобства умножим остаток $r_2\left(x\right) = -\frac{1}{4}x^2-\frac{1}{2}x$ на $-4$ и получим $r_2\left(x\right) = x^2+2x.$ Продолжаем деление.

          $2x^3$ $-$ $x^2$ $+$ $2x$  
          $2x^3$ $+$ $4x^2$      
            $-$ $5x^2$ $+$ $2x$  
            $-$ $5x^2$ $-$ $10x$  
                  $12x$  
    $x^2$ $+$ $2x$        
    $2x$ $-$ $5$        

    Третий остаток умножим на $\displaystyle\frac{1}{12}$ и получим $r_3\left(x\right) = x.$ Поделим в последний раз.

              $x^2$ $+$ $2x$  
              $x^2$      
                  $2x$  
                  $2x$  
                  $0$  
    $x$            
    $x$ $+$ $2$        

    Как мы видим, последний ненулевой остаток равен $x$ — это и будет нашим НОД.

    Ответ: НОД$\left(f\left(x\right), g\left(x\right)\right) = x.$

    [свернуть]
  2. Пользуясь алгоритмом Евклида, убедиться в том, что многочлены $f\left(x\right)$ и $g\left(x\right)$ взаимно простые, и подобрать $u\left(x\right)$ и $v\left(x\right)$ так, чтобы $f\left(x\right) \cdot u\left(x\right) + g\left(x\right) \cdot v\left(x\right) = 1:$ $$f\left(x\right) = 3x^3-2x^2+x+2,\\ g\left(x\right) =x^2-x+1.$$
    Решение

    Как и сказано в условии задачи, воспользуемся алгоритмом Евклида, чтобы проверить равен ли НОД наших многочленов $1.$ В отличии от прошлого задания, здесь надо запоминать все частные и остатки.

      $3x^3$ $-$ $2x^2$ $+$ $x$ $+$ $2$  
      $3x^3$ $-$ $3x^2$ $+$ $3x$      
          $x^2$ $-$ $2x$ $+$ $2$  
          $x^2$ $-$ $x$ $+$ $1$  
            $-$ $x$ $+$ $1$  
    $x^2$ $-$ $x$ $+$ $1$    
    $3x$ $+$ $1$   $=$ $q_1\left(x\right)$  

    Получили остаток $r_1\left(x\right) = -x+1.$ Продолжаем деление.

          $x^2$ $-$ $x$ $+$ $1$  
          $x^2$ $-$ $x$      
                  $1$  
    $-$ $x$ $+$ $1$      
    $-$ $x$     $=$ $q_2\left(x\right)$  

    $r_2\left(x\right) = 1,$ следовательно НОД$\left(f\left(x\right), g\left(x\right)\right) = 1,$ значит, наши многочлены взаимно простые и можно продолжать решать. Запишем многочлены в таком виде:$$\begin{cases} f\left(x\right) = g\left(x\right) \cdot q_1\left(x\right) + r_1\left(x\right); \\ g\left(x\right) = r_1\left(x\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$$ Выразим $r_1\left(x\right)$ из первого равенства и подставим во второе:$$\begin{cases} r_1\left(x\right) = f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right); \\ g\left(x\right) = \left(f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right)\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$$ Помня про то, что $r_2\left(x\right) = d\left(x\right),$ продолжаем наши преобразования:$$f\left(x\right) \cdot \left(-q_2\left(x\right)\right) + g\left(x\right) \cdot \left(1 + q_1\left(x\right) \cdot q_2\left(x\right)\right) = d\left(x\right).$$ Подставляем значения:$$f\left(x\right) \cdot \left(x\right) + g\left(x\right) \cdot \left(-3x^2-x+1\right) = d\left(x\right).$$

    Если сравнить данное равенство с формулой линейного представления НОД, мы увидим, что получили $u\left(x\right) = x$ и $v\left(x\right) = -3x^2-x+1.$

    Ответ: $u\left(x\right) = x,$ $v\left(x\right) = -3x^2-x+1.$

    [свернуть]
  3. Пользуясь алгоритмом Евклида, найти многочлены $u\left(x\right)$ и $v\left(x\right)$ такие, чтобы они удовлетворяли равенству $f\left(x\right) \cdot u\left(x\right) + g\left(x\right) \cdot v\left(x\right) = d\left(x\right),$ где $d\left(x\right)$ — НОД многочленов $f\left(x\right)$ и $g\left(x\right):$ $$f\left(x\right) = x^4+2x^3-x^2-4x-2,\\ g\left(x\right) = x^4+x^3-x^2-2x-2.$$

    Решение

    Для начала необходимо построить НОД. Для этого используем алгоритм Евклида.

    $x^4$ $+$ $2x^3$ $-$ $x^2$ $-$ $4x$ $-$ $2$  
    $x^4$ $+$ $x^3$ $-$ $x^2$ $-$ $2x$ $-$ $2$  
        $x^3$     $-$ $2x$      
    $x^4$ $+$ $x^3$ $-$ $x^2$ $-$ $2x$ $-$ $2$
    $1$       $=$ $q_1\left(x\right)$      

    Получили остаток $r_1\left(x\right) = x^3-2x.$ Делим дальше.

    $x^4$ $+$ $x^3$ $-$ $x^2$ $-$ $2x$ $-$ $2$  
    $x^4$     $-$ $2x^2$          
        $x^3$ $+$ $x^2$ $-$ $2x$ $-$ $2$  
        $x^3$     $-$ $2x$      
            $x^2$     $-$ $2$  
    $x^3$ $-$ $2x$          
    $x$ $+$ $1$     $=$ $q_2\left(x\right)$  

    Второй остаток $r_2\left(x\right) = x^2-2.$ Выполняем последнее деление.

              $x^3$ $-$ $2x$  
              $x^3$ $-$ $2x$  
                  $0$  
    $x^2$ $-$ $2$        
    $x$       $=$ $q_3\left(x\right)$  

    $r_3\left(x\right) = 0,$ следовательно НОД$\left(f\left(x\right), g\left(x\right)\right) = x^2-2.$ Дальнейшие наши действия ведутся по тому же принципу, что и в прошлой задаче, поэтому запишем многочлены в таком виде:$$\begin{cases} f\left(x\right) = g\left(x\right) \cdot q_1\left(x\right) + r_1\left(x\right); \\ g\left(x\right) = r_1\left(x\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$$ Выразим $r_1\left(x\right)$ и подставим его во второе равенство:$$\begin{cases} r_1\left(x\right) = f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right); \\ g\left(x\right) = \left(f\left(x\right)-g\left(x\right) \cdot q_1\left(x\right)\right) \cdot q_2\left(x\right) + r_2\left(x\right). \end{cases}$$ Помним, что $r_2\left(x\right) = d\left(x\right),$ поэтому делаем замену:$$f\left(x\right) \cdot \left(-q_2\left(x\right)\right) + g\left(x\right) \cdot \left(1 + q_1\left(x\right) \cdot q_2\left(x\right)\right) = d\left(x\right).$$ Подставляем значения:$$f\left(x\right) \cdot \left(-x-1\right) + g\left(x\right) \cdot \left(x+2\right) = d\left(x\right).$$

    Итак, мы получили $u\left(x\right) = -x-1$ и $v\left(x\right) = x+2.$ На этом можно и закончить, но иногда стоит перепроверить правильность своих вычислений. Для проверки нам необходимо вместо $f\left(x\right)$ и $g\left(x\right)$подставить их значения, а после раскрыть скобки. Если в итоге мы получим многочлен равный построенному НОД, то $u\left(x\right)$ и $v\left(x\right)$ подобраны верно. В нашем случае все сходится, а значит мы можем записывать их в ответ.

    Ответ: $u\left(x\right) = -x-1,$ $v\left(x\right) = x+2.$

    [свернуть]

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

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

НОД двух многочленов: 1 комментарий

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *