CONTIN (Лекции Кузьмина), страница 2

Утв.: Многочлены a(x),b(x) – взаимнопросты u(x), v(x):u(x)a(x)+v(x)b(x)=1

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

" " (a(x),b(x))=1 следовательно u(x), v(x)

" " пусть (a(x),b(x))=d(x), deg d(x)>1

т.к. d(x)|a(x), d(x)|b(x) значит d(x)|[u(x)a(x)+v(x)b(x)] следовательно d(x)|1 следовательно deg d(x) 0,

deg d(x) 0 значит d(x)=const=1. ч.т.д.

Опр.: a(x) – собственный делитель b(x), если d(x)|b(x) и 0<deg a(x)<deg b(x), т.е. a(x) const.

Опр.: Многочлен a(x) – неприводимый, – если он не имеет собственных делителей, иначе – приводимый.

Замечание: неприводимый многочлен делится либо на константу, либо на самого себя.

Свойства взааимнопростых многочленов

1. (a(x),b(x))=d(x) =1

Доказательство: существуют многочлены u(x), v(x) : u(x)a(x)+b(x)v(x)=d(x)

u(x) + v(x) = 1

первое свойство доказано

1. (a(x),b(x))=1; a(x)|c(x), b(x)|c(x) следовательно a(x)b(x)|c(x)

Доказательство: u(x)a(x)+v(x)b(x)=1;

c(x)=a(x)q(x)

u(x)a(x)q(x)+v(x)b(x)q(x)=q(x)

следовательно b(x)|q(x)

значит q(x)=b(x)q₁(x) следовательно c(x)=a(x)b(x)q₁(x). ч.т.д.

1. (a(x),b(x))=1, a(x)|c(x)^.b(x) следовательно a(x)|c(x)

Доказательство: u(x)a(x)+v(x)b(x)=1; | c(x)

u(x)a(x)c(x)+v(x)b(x)c(x)=c(x)

следовательно a(x)|c(x). ч.т.д.

1. (a(x),b(x))=1, (a(x),c(x))=1 следовательно (a(x),b(x)^.c(x))=1

Доказательство: [u(x)a(x)+v(x)b(x)=1] [m(x)a(x)+l(x)c(x)=1]

a(x)(u(x)a(x)m(x) + u(x)c(x)l(x) + m(x)b(x)v(x)) + b(x)c(x)v(x)l(x) = 1,

где u'= u(x)a(x)m(x)+u(x)c(x)l(x)+m(x)b(x)v(x), v'=v(x)l(x). ч.т.д.

Опр.: NOK многочленов a(x), b(x) - [a(x),b(x)] называется многочлен D(x) со свойствами:

1. a(x)|D(x); b(x)|D(x)

2. для любого D'(x) : a(x)|D'(x), b(x)|D'(x) следует D(x)|D'(x)

Утв.: Для любых многочленов a(x), b(x)

[a(x),b(x)]=

Доказательство: пусть (a(x),b(x))=d(x);

Значит a(x)=a₁(x)d(x); b(x)=b₁(x)d(x).

Перемножим их: a₁(x)b₁(x)d(x)=B(x)

a(x)|B(x); b(x)|B(x), т.е. 1) – выполнено.

2) - ? Пусть существует F(x) : a(x)|F(x), b(x)|F(x) значит F(x)=a₁(x)d(x)f(x)=b₁(x)d(x)g(x),

где a₁(x)=d(x)=a(x), b₁(x)d(x)=b(x) следовательно a₁(x)f(x)=b₁(x)g(x), а (a₁,b₁)=1

(по свойству 1. взаимопростых многочленов) значит a₁(x)|g(x) следовательно g(x)=a₁(x)g'(x) откуда получаем, что

F(x)=b₁(x)d(x)a₁(x)g'(x), где b₁(x)d(x)a₁(x)=B(x) следовательно доказали утверждение. (по определению NOK)

Свойства неприводимых многочленов

Везде старший коэффициент равен 1.

1. Теорема: пусть f(x) – неприводимый многочлен. Тогда для любого многочлена g(x) выполнено либо f(x)|g(x), либо (f(x),g(x))=1

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

1. Если (f(x),g(x))=1 то свойство справедливо

2. пусть (f(x),g(x))=d(x), deg d(x)>0 значит f(x)|g(x) – докажем это:

d(x)|f(x) и deg d(x)>0, т.е. d(x) 0 следовательно

d(x)=f(x), т.к. f(x) – неприводимый многочлен, а т.к. d(x)|g(x) значит f(x)|g(x)

2. пусть f(x) – неприводимый многочлен. Если неприводимый многочлен делит произведение двух других многочленов, т.е. f(x)|a(x)^.b(x), то либо f(x)|a(x), либо f(x)|b(x).

Доказательство: пусть f(x)†a(x) значит f(x)|b(x) – докажем это:

из свойства 1. неприводимых многочленов следует:

(f(x),a(x))=1 + f(x)|a(x)^.b(x)

откуда получаем, что f(x)|b(x) – по 3. свойству взаимопростых многочленов.

ч.т.д.

Опр.: Представление произвольного многочлена a(x) в виде:

a(x)=a_{n j}(x)^kj,

где f₁(x),…,f_r(x) – попарно различные неприводимые многочлены со старшим коэффициентом равным 1, k_j>0 – есть каноническое разложение многочлена a(x); deg a(x)=n.

Теорема: Для любого ненулевого многочлена a(x) его каноническое разложение определено однозначно.

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

1. Докажем индукцией по n–степени многочлена, что n=deg a(x):

1. n=0 значит a(x)=const=(-1)^ε.a₀

2. n=1 значит a(x)=a₁(x+a₀/a₁) – неприводимый как многочлен первой степени

3. пусть существует каноническое разложение для любых многочленов степени n<t

Покажем справедливость предположения индукции для n=t. deg a(x)=t

1. a(x) – неприводимый многочлен, тогда это и есть его представление, т.е. он сам – каноническое разложение

2. a(x) – приводимый многочлен значит

a(x)=a₁(x)a₂(x), deg a₁(x)<t, deg a₂(x)<t

следовательно для a₁, a₂ справедливо предположение индукции, т.е. существует каноническое разложение

a(x)=( _j(x)^kj)( _s(x)^ts)

раскроем скобки и объединим степени у одинаковых, значит a(x) – также имеет каноническое разложение.

2. Докажем его единственность: для определенности будем считать, что неприводимый многочлен – унитарный, т.е. старший коэффициент равен 1, т.к. свойство неприводимости выполняется для всех многочленов вида cf(x);

пусть существуют два канонических разложения:

a(x)=a_{n j}(x)^kj=a_{n s}(x)^ts.

Покажем, что эти произведения совпадают, т.е.

_j(x)^kj= _s(x)^ts.

f₁(x)–неприводим и f₁(x)| _s(x)^ts;

по свойству 2.: существует s₁: f₁(x)|g_s1(x)^ts1=g_s1(x)...g_s1(x)

из свойства 2. Следует, что f₁(x)|g_s1(x), а т.к. g_s1 – неприводим значит f₁(x)=g_s1(x).

Аналогично для любого f_j(x) существует s_j : f_j(x)=g_sj(x), следовательно r l.

И аналогично наоборот: получаем, что l r

следовательно r=l и наборы многочленов совпадают: {f₁(x),…,f_r(x)}={g₁(x),…,g_l(x)} и существует взаимно однозначное соответствие j s_j .

Переупорядочим многочлены в правой части, чтобы был тот же порядок: _j(x)^kj= _j(x)^tsj; k_j=ts_j - ?

Пусть k₁<t_s1 . Разделим обе части на f₁^k1 :

_j(x)^kj = f₁(x)^ts1-k1 _j(x)^tsj

f₁(x)| _j(x)^kj значит f₁ делит какой-то f_j, т.е. совпадает с ним. Возникает противоречие с выбором системы многочленов {f₁,…,f_r}, следовательно предположение, что k₁<t_s1, неверно. Аналогично доказывается неверность k₁>t_s1, значит k₁=t_s1

Теперь сократим все на f₁^k1 :

_j(x)^kj = _j(x)^tsj

– с которым поступаем аналогично, и т.д. Т.е. для любого k_j=t_sj

Значит с точностью до перестановки сомножителей каноническое разложение определено однозначно.

Свойство сравнимости в кольце многочленов над полем

Пусть P(x) – кольцо многочленов над полем Р

Опр.: a(x) = b(x) (mod f(x)) – сравнимы по модулю многочлена f(x), если остатки от деления совпадают:

a(x)=f(x)q₁(x)+r₁(x) и b(x)=f(x)q₂(x)+r₂(x) r₁=r₂

Утв.: Многочлены a(x) b(x) (mod f(x)) f(x)|a(x)-b(x)

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

" " – очевидно из определения

" " – a(x)=f(x)q₁(x)+r₁(x) и b(x)=f(x)q₂(x)+r₂(x)

a(x)-b(x) = f(x)(q₁(x)-q₂(x)) + r₁(x)-r₂(x)

значит f(x)|r₁(x)-r₂(x), deg f(x) 0, deg[r₁(x)-r₂(x)]<deg f(x)

следовательно r₁(x)-r₂(x)=0 ч.т.д.

Теорема: пусть f(x) – унитарный многочлен (далее везде). Для любого унитарного ненулевого многочлена f(x) – отношение сравнимости по (mod f(x)) – конгруэнция кольца.

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

1. Покажем, что mod f(x) – отношение эквивалентности:

a(x) b(x)(mod f(x)) ~ f(x)|a(x)-b(x)

1. рефлексивность: f(x)|a(x)-a(x)

2. симметричность: f(x)|a(x)-b(x)

следовательно f(x)|b(x)-a(x), т.к. a(x)-b(x)=f(x)q(x)

значит b(x)-a(x)=f(x)(-q(x))

1. транзитивность: f(x)|a(x)-b(x), f(x)|b(x)-c(x) значит

a(x)-b(x)=f(x)q₁(x) + b(x)-c(x)=f(x)q₂(x)

a(x)-b(x)+b(x)-c(x)=a(x)-c(x)=f(x)(q₁(x)+q₂(x)). ч.т.д.

1. Покажем, что операции кольца многочленов согласованы с отношением mod f(x) – отношением эквивалентности:

2. множество многочленов кольца P[x]:

{a(x): a(x) b(x)(mod f(x))}=[b(x)]_f – класс эквивалентности для многочлена b(x);

1. берем два класса [a(x)], [b(x)] и по два многочлена a₁(x), a₂(x) и b₁(x), b₂(x), где a₁(x) a₂(x)(mod f(x)) и b₁(x) b₂(x)(mod f(x)).

Надо доказать, что

a₁(x)+ b₁(x) a₂(x)+ b₂(x)(mod f(x)) и a₁(x)^. b₁(x) a₂(x)^. b₂(x)(mod f(x)),

т.е. согласованность операций:

а) [a₁(x)-a₂(x)=f(x)^.q₁(x)] + [b₁(x)-b₂(x)=f(x)^.q₂(x)] значит

(a₁(x)+b₁(x))-(a₂(x)+b₂(x))= =f(x)(q₁(x)+q₂(x))

a₁(x)+b₁(x) a₂(x)+b₂(x) (mod f(x)) ч.т.д.

б) [a₁(x)=a₂(x)+f(x)q₁(x)] [b₁(x)=b₂(x)+f(x)q₂(x)]

a₁(x)b₁(x)=a₂(x)b₂(x)+f(x)Q(x)

a₁(x)b₁(x)-a₂(x)b₂(x)=f(x)^.Q(x)

a₁(x)b₁(x) a₂(x)b₂(x) (mod f(x)) ч.т.д.

Следовательно это конгруэнция на кольце ч.т.д.

Следствие: Обозначим через – множество классов эквивалентности кольца многочленов P[x] относительно отношения эквивалентностити:

(mod f(x)). Определим на этих классах сложение и умножение: [a(x)]+[b(x)]=[a(x)+b(x)] и [a(x)]^.[b(x)]=[a(x)^.b(x)]

следовательно множество с введенными операциями – кольцо.

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

1. Введенные операции определены корректно, т.е. результат не зависит от выбора элемента из класса:

a₁(x), a₂(x) [a(x)] значит [a(x)]=[a₁(x)]=[a₂(x)],

аналогично для b₁(x), b₂(x) [b(x)]. По теореме о конгруэнции [a₁(x)+b₁(x)]=[a₂(x)+b₂(x)], а [a₁(x)+b₁(x)]=[a₁(x)]+[b₁(x)] следовательно [a₁(x)]+[b₁(x)]=[a₂(x)]+[b₂(x)].