ALG#05 (1085235), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

(a(x),b(x)) = (a(x)-b(x)q₁(x),b(x)) = [r₁(x)=a(x)-b(x)q₁(x)] = (r₁(x),b(x))= (r₁(x),b(x)-r₁(x)q₂(x)) = [r₂(x)=b(x)-r₁(x)q₂(x)]=(r₁(x),r₂(x)) =…= (r_s(x),r_s+1(x))= (r_n-2(x),r_n-1(x)) = r_n-1(x),

где r_n-1(x) – последний ненулевой остаток;

т.к. r_n(x)=0, а r_n-2(x)=r_n-1(x)q_n(x)+r_n(x), то r_n-1(x)|r_n-2(x) ч.т.д.

Теорема: Пусть a(x), b(x) – ненулевые многочлены над полем. Тогда существуют u(x), v(x) : u(x)a(x)+b(x)v(x)=d(x)=(a(x),b(x)).

Доказательство: пусть u₀(x)=0, u₁(x)=1, u_k(x)=u_k-2(x)-q_k(x)u_k-1(x),

v₀(x)=1, v₁(x)=-q₁(x), v_k(x)=v_k-2(x)-q_k(x)v_k-1(x).

Докажем, что: r_k(x)=u_k(x)a(x)+v_k(x)b(x);

проводим доказательство по индукции:

1. базис индукции: k=1

r₁(x)=1^.a(x)-q₁(x)b(x) – соответствует алгоритму Евклида

1. шаг индукции: пусть выполняется для любого k<t.

Пусть k=t - проверим:

по алгоритму Евклида:

r_t-2(x)=r_t-1(x)q_t(x)+r_t(x) следовательно r_t(x)=r_t-2(x)-q_t(x)r_t-1(x);

т.к. t-2<t и t-1<t, то для них формула верна:

r_t(x) = u_t-2(x)a(x) + v_t-2(x)b(x) - q_t(x)[u_t-1(x)a(x) + v_t-1(x)b(x)] = a(x)(u_t-2(x)-q_t(x)u_t-1(x)) +

+ b(x)(v_t-2(x) - q_t(x)v_t-1(x)), где [u_t-2(x) - q_t(x)u_t-1(x) = u_t(x)], [v_t-2(x) - q_t(x)v_t-1(x) = v_t(x)]

верно при k=t

выполняется для любого k (по индукции)

а т.к. (a(x),b(x))=r_n-1(x)=u_n-1(x)a(x)+v_n-1b(x) – то построили в явном виде, где r_n-1(x) – последний ненулевой остаток.

Опр.: Многочлены a(x) и b(x) называются взаимнопростыми, если их NOD = 1.

Утв.: Многочлены 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)

1. для любого 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 то свойство справедливо

1. пусть (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₀

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

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

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

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

1. 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)

1. симметричность: 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) – отношением эквивалентности:

1. множество многочленов кольца 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)).

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

Характеристики

Список файлов лекций