Processing math: 100%

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

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

При определении понятия НОД, для начала необходимо ознакомиться с понятием общего делителя двух многочленов. Заранее для краткости и удобства договоримся, что в дальнейшем под понятиями общего делителя и наибольшего общего делителя мы будем подразумевать их аналоги на множестве 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)=x81, g(x)=x41. Для того, чтобы найти общие делители разложим эти многочлены по формуле разности квадратов: f(x)=x81=(x41)(x4+1)=(x21)(x2+1)(x4+1)==(x1)(x+1)(x2+1)(x4+1), g(x)=x41=(x21)(x2+1)=(x1)(x+1)(x2+1).Как мы видим, общими делителями являются (x1), (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)cP:f(x)=cg(x)) d1(x)=c1d2(x), c1P, c1=const.

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

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

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

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

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

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))=x1.

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

Пример 4. Пусть даны f(x)=x3+x1 и g(x)=x2. Найдем их НОД. Для удобства умножим f(x) на 1, получим f(x)=x3x+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)=x29 и g(x)=x327;
    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)=3x32x2+x+2,g(x)=x2x+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+2x3x24x2,g(x)=x4+x3x22x2.

    Решение

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

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

М1812. Доказать тождество

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

Условие

Натуральные числа а, b и с таковы, что НОД(a21,b21,c21)=1.

Докажите, что НОД(ab+c,bc+a,ca+b)=НОД(a,b,c) (НОД – наибольший общий делитель).

Рассмотрим произвольное простое число р и докажем, что оно входит в НОД(a21,b21,c21) и НОД(a,b,c) в равной степени. Заметим, что если НОД(a,b,c)p, то степень вхождения р в оба НОДа равна наименьшей степени вхождения р в числа a,b,c (если НОД(a,b,c)pk, но c не делится на pk+1, то ab+c делится на pk, но не делится на pk+1). Поэтому достаточно доказать, что любой простой делитель q числа НОД(ab+c,bc+a,ca+b) делит НОД(a,b,c). Пусть, скажем, а не делится на q, тогда, поскольку bc+a не делится на q, получаем, что b не делится на q и с не делится на q. Тогда (ab+c)(bc+a)a(ab+c)c(bc+a)=ac(b21)q. Стало быть, (b21)q. Аналогично, (a21)q и (c21)q – это уже противоречие с тем, что НОД(a21,b21,c21)=1. Значит, НОД(ab+c,bc+a,ca+b)=НОД(a,b,c).

А.Голованов

М1814. О периодической последовательности

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

Условие

Пусть a, m1, m2 натуральные числа, причем a взаимно просто как с m1, так и с m2. Обозначим через rn остаток от деления целой части числа anm1 на m2 (n=0,1,2,).

Докажите, что последовательность {rn} является периодической.

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

Так как НОД(a, m1) = НОД(a, m2)=1, то НОД(a, m1m2)=1. Пусть n0 какое-нибудь натуральное число, для которого an0 при делении на m1m2 дает в остатке 1. (Если НОД(a, m1m2)=1, то такое число обязательно существует. Можно, например, положить n0=φ(m1m2), где φ(m) функция Эйлера см. статью В.Сендерова и А.Спивака «Малая теорема Ферма» в «Кванте» №1 за 2000 год.)

Тогда an0=Qm1m2+1 для некоторого целого числа Q. Теперь при любом nn0 имеем [anm1]=[an0ann0m1]=[(Qm1m2+1)ann0m1]= =[ann0Qm2+ann0m1]=ann0Qm2+[ann0m1] ([x] обозначает целую часть числа x).

Таким образом, остатки чисел [anm1] и [ann0m1] при делении на m2 совпадают, т.е. rn=rnn0. Значит, последовательность {rn} имеет период длины n0 (доказано также и то, что этот период начинается с самого начала последовательности).

Возникает вопрос о длине наименьшего периода последовательности {rn}. Верно ли, что если в качестве n0 взять наименьшее натуральное число такое, что an0 при делении на m1m2 дает в остатке 1, то n0 и будет длиной наименьшего периода? Как показывает пример a=3, m1=13, m2=2 (здесь n0=3, а последовательность {rn} сплошь состоит из нулей), ответ на этот вопрос в общем случае отрицателен. Однако если дополнительно предположить, например, что m2m1, то ответ будет утвердительным (читателю предлагается доказать это в качестве упражнения).

Н.Осипов

М1762. Две тысячи делителей

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

Условие

Существует ли натуральное число n такое, что n имеет ровно 2000 различных простых делителей и 2n+1 делится на n?

Решение

Докажем по индукции, что для любого натурального k существует натуральное nk, имеющее k различных простых делителей, делящееся на 3 и такое, что 2nk+1 делится на nk.

Для k=1 можно взять n=3. Пусть число nk=n, кратное 3, имеет k различных простых делителей, причём 2n+1 делится на n.

Число 23n+1=(2n+1)(22n2n+1) делится на 3n. Это следует из того, что 2n+1 делится на n, а
22n2n+1=(2n2)(2n+1)+3() делится на 3 (поскольку при нечётном n числа 2n+1 и 2n2 делятся на 3).

Далее, число 22n2n+1 не делится на 9, поскольку на 9 делится произведение (2n2)(2n+1). Значит, поскольку 22n2n+1>3 при n>1, то это число имеет при n>1 простой делитель p>3. Так как НОД (2n+1,22n2n+1)=3 (это тоже ясно из равенства ()), то p — не делитель n.

Из сказанного следует, что число 3pn имеет k+1 простой делитель, причём 23pn+1 делится на 3pn. Последнее следует, например из равенства
(23n)p+1=(23n+1)((23n)p1(23n)p2++1)

Для завершения решения достаточно положить nk+1=3pn=3pnk.

А.Егоров, В.Сендеров

М1476

Условие

Докажите, что не существует различных простых чисел p, q таких, что 2p+1 делится на q, 2q+1 делится на p.

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

Ясно, что p и q нечетны, и если одно из них равно 3, то другое тоже должно равняться 3. Поэтому будем в дальнейшем считать, что p>q>3.

Первое решение.

Из условия следует, что 22p1(modm).
С другой стороны, согласно малой теореме Ферма, для простого q имеем: 2q11(modq).
Пусть n — найменьшее натуральное число такое, что 2n=1(modq). Тогда n2 — отличный от единицы делитель числа 2p. Значит, n=p либо n=2p, т.е. n не является делителем числа q1. Противоречие.
Второе решение можно получить, опираясь на следующее утверждение.

Лемма 1

Пусть pq — простые числа, q3,2p+1 делится на q. Тогда q=2kp+1, где k — натуральное число. Эту лемму легко доказать, заметив, что число n в первом решении равно 2p. Из нее следует, что q>p. Противоречие.
Еще одно решение можно получить, опираясь на такое утверждение.

Лемма 2

Если числа a и b взаимно просты, то НОД(2a+1, 2b+1)=1,

либо НОД(2a+1, 2b+1)=3
(причем второй случай имеет место тогда и только тогда, когда a и b нечетны).

Третье решение

Имеем:2p+1 делится на q; 2q11, по малой теореме Ферма, также делится на q. Следовательно, и 2pq+1+1 делится на q — в противоречии с леммой 2.

Замечание.

Лемма 2 является частным случаем следующего несложного утверждения. Пусть НОД(m,n)=1, НОД(a,b)=d, НОД(ma+na, mb+nb)=d1. Тогда d1=md+nd, если числа ad и bd оба нечетны; d1=1 либо d1=2 в противном случае (а именно: d1=1, если m и n разной четности; d1=2, если m и n нечетны).