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

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

При определении понятия НОД, для начала необходимо ознакомиться с понятием общего делителя двух многочленов. Заранее для краткости и удобства договоримся, что в дальнейшем под понятиями общего делителя и наибольшего общего делителя мы будем подразумевать их аналоги на множестве $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. Личный конспект, составленный на основе лекций Белозерова Г.С.

М1839. О тригонометрических неравенствах

Задача из журнала «Квант» (2002 год, 5 выпуск)

Условие

Пусть $0 < x < \frac{\pi}{4}$. Докажите, что $$\left(\cos x\right)^{\cos^2 x} > \left(\sin x\right)^{\sin^2 x},$$ а также $$\left(\cos x\right)^{\cos^4 x} < \left(\sin x\right)^{\sin^4 x}.$$

Доказательство

На первый взгляд кажется, что одно из неравенств противоречит другому, но это не так.

Рассмотрим $$f(y) = \cos^y x − \sin^y x ,$$ где $ 0 < x < \frac{\pi}{4}$, $y \geqslant 0$. Имеем: $f(0) = 0$, $f(y) > 0$ при $y > 0$, $f(y) \to 0$ при $y \to \infty$. Далее, $$f'(y) = \cos^y x \ln \cos x − \sin^y x \ln \sin x =\\= \cos^y x\left(\ln \cos x − \mathrm {tg}^y\,x \ln \sin x\right),$$ поэтому $f'(y)$ имеет единственный корень при $y > 0$, так как функция $g(y) = \mathrm {tg}^y\,x$ монотонна. Из равенства $$f(2) = f(2)\left(\cos^2 x + \sin^2 x\right) = f(4)$$ следует, что $f'(2) > 0$, $f'(4) < 0$.

Перепишем первое неравенство: $$\cos^2 x \ln \cos x > \sin^2 x \ln \sin x ,$$ что эквивалентно первому неравенству задачи. Аналогично, $f'(4) < 0$, или $$\cos^4 x \ln \cos x < \sin^4 x \ln \sin x ,$$ что эквивалентно второму неравенству задачи.

В. Сендеров

М778. Общая точка

Задача из журнала «Квант» (1982 год, 12 выпуск)

Условие

Дан неравнобедренный треугольник $A_{1}A_{2}A_{3}$. Пусть $a_{i}$ – его сторона, лежащая против вершины $A_{i}$ $(i = 1, 2, 3)$, $M_{i}$ – середина стороны $a_{i}$, $T_{i}$ – точка касания стороны с окружностью, вписанной в данный треугольник, $S_{i}$ – точка, симметричная $T_{i}$ относительно биссектрисы угла $A_{i}$ треугольника.

Докажите, что прямые $M_{1}S_{1}$, $M_{2}S_{2}$ и $M_{3}S_{3}$ имеют общую точку.

Доказательство

Стороны треугольника $M_{1}M_{2}M_{3}$ соответственно параллельны сторонам треугольника $A_{1}A_{2}A_{3}$. Мы докажем, что и стороны треугольника $S_{1}S_{2}S_{3}$ параллельны сторонам $A_{1}A_{2}A_{3}$. Отсюда вытекает, что $\triangle$$S_{1}S_{2}S_{3}$ гомотетичен $\triangle$$M_{1}M_{2}M_{3}$ или переводится в него параллельным переносом. Второй случай отпадает, ибо окружность, описанная около треугольника $M_{1}M_{2}M_{3}$, больше описанной окружности треугольника $S_{1}S_{2}S_{3}$. Следовательно, прямые, соединяющие соответственные вершины треугольников $S_{1}S_{2}S_{3}$ и $M_{1}M_{2}M_{3}$, должны пересечься в одной точке — центре гомотетии.

Покажем, например, что прямые $S_{1}S_{2}$ и $A_{1}A_{2}$ параллельны (см. рисунок). При симметрии относительно биссектрисы угла $A_{1}$ точка $S_{1}$ перейдет в $T_{1}$, а $T_{3}$ — в $T_{2}$,Рисунок задачи М778 поэтому дуги $S_{1}T_{3}$ и $T_{1}T_{2}$ вписанной окружности треугольника $A_{1}A_{2}A_{3}$ равны. Аналогично, при симметрии относительно биссектрисы угла $A_{2}$ дуга $T_{1}T_{2}$ перейдет в дугу $T_{3}S_{2}$. Следовательно, дуги $S_{1}T_{3}$ и $T_{3}S_{2}$ равны, и поэтому точки $S_{1}$ и $S_{2}$ находятся на одинаковом расстоянии от прямой $A_{1}A_{2}$, то есть $S_{1}S_{2}$$\parallel$$A_{1}A_{2}$. Аналогично доказывается, что и две другие стороны треугольника $S_{1}S_{2}S_{3}$ параллельны соответствующим сторонам треугольника $A_{1}A_{2}A_{3}$.

А. П. Савин