Определения (1016731), страница 2

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

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

Пусть Р – поле;

Обозначим: Р - множество носителей с элементами из Р; (а₀ а₁ а₂ … ), а_j Р

Р : если (а₀ … а_n …) , то k : а_j=0, для j k, т.е. начиная с какого-то номера они все нули.

Определим на множестве : + = , c_k=a_k+b_k

× = , c_k= a_jb_k-j

Опр.: Будем говорить, что многочлен a(x) делит b(x), т.е. a(x)½b(x), если существует с(х) : a(x)× c(x)=b(x)

Опр.: Степень многочлена a(x) – deg a(x) – номер наибольшего ненулевого коэффициента в представлении: a(x)= a_jx^j.

Если а(х)=0, то полагаем deg a(x)= -

(примечание: пусть a(x)=a₀ 0 тогда deg a(x)=0).

Опр.: Разделить a(x) на b(x) с остатком – значит, что b(x) можно представить в виде b(x)=q(x)a(x)+r(x), deg r(x)<deg a(x)

Опр.: NOD многочленов a(x), b(x) – многочлен d(x):

1) d(x)|a(x); d(x)|b(x)

2) d'(x)|a(x), d'(x)|b(x) следовательно d'(x)|d(x)

Замечание: для определенности считаем, что старший коэффициент многочлена равен 1.

Опр.: Многочлены a(x) и b(x) называются взаимнопростыми, если их NOD = 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)

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

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.

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

Пусть 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), a₂(x),…,a_t(x) – полная система представителей классов эквивалентностити относительно отношения º(mod f(x)) если:

1. для любого j¹k a_j(x) не сравним с a_k(x)(mod f(x))

2. для люього b(x) P[x] существует k : b(x)=a_k(x) (mod f(x)).

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

Пусть a(x)=

Опр.: - значение многочлена a(x) (x)_ние много из поля.

Опр.: Если для некоторого многочлена a(x) над полем Р и элемента ? из Р выполнено условие a(α)=0,

Опр.: Кратность корня – наибольшее значение r : r= α

Неприводимые многочлены над числовым полем С, полем действительных чисел R и полем рациональных чисел Z

Теорема (Гаусса): Любой многочлен над полем С имеет в этом поле корень.

Следствие: Над полем С неприводимы многочлены только первой степени.

Опр.: Многочлен a(x) над кольцом Z (с целыми коэффициентами) – примитивный, если множество его коэффициентов взаимно просто в совокупности.

Опр.: Два числа взаимно просты, если для любого простого числа одно из них на него не делится.

Опр.: Множество (a₀,…,a_n) – взаимно просто в совокупности, если для p – простого k, 0kn : p|a_k

Пример: (6,10,15)=1, т.е. NOD совокупности равен 1.

Опр.: Многочлены a(x), b(x) над полем Q – ассоциированные, если : a(x)=c^.b(x).

Опр.: Пусть Р – поле следовательно множество Q P – подполе Р, если Q P и Q – поле.

Пример: Q < R < C

Опр.: Поле называется простым, если оно не содержит собственных подполей, т.е. если Q<P значит Q=P (более простых полей, чем Р в нем нет).

Опр.: В конечном поле элемент с таким свойством называется примитивным

Т.е. в конечном поле существует примитивный элемент, где 0, ¹, ², …, ^|P|-1 – все различные элементы поля Р

{В абелевой группе существует : ord =expG}

expG=min{t : G, ^t=e}

Определение: элемент порядок которого равен мощности поля без единицы называется примитивным элементом поля:

Определение: пусть Q>P; унитарный многочлен f(x) наименьшей степени с коэффициентами из Р , такой что для  Q, f()=0 – минимальный многочлен элемента  над полем Р: m_,P(x);

Отображение “след”.

Определение: пусть есть поле Р из q элементов и поле Р^/ из q^m элементов. Отображение называется “следом” если:

Линейные рекуррентные последовательности.

Последовательность над полем Р – произвольное отображение множества N₀ в поле Р:

U: N₀P; U=(H(0), U(1), U(2), …);

P^ - всё множество последовательностей над Р.

Линейная рекуррентная последовательность (ЛРП) над Р – последовательность U для которой  m, c₀, c₁, …, c_m-1P:  i 0 :

Отрезок последовательности: (U(c), …, U(m-1)) – начальный вектор рекуррентна.

Определение: - характеристический многочлен последовательности.

Порядок рекуррентны = deg(F(x));

Пример1: ГПр – ЛРП: b_n+1=qb_n; F(x)=x-q;

Пример2: АПр  а_n+1=a_n+d=a_n+(a_n-a_n-1);  a_n+2=2a_n+1-a_n; F(x)=x²-2x+1=(x-1)²;

Пример3: Фибоначчи: U_n+2=U_n+1+U_n; 1,1,2,3,5,8,11,…; F(x)=x²-x-1;

Утверждение: ЛРП U с характеристическим многочленом F(x), degF(x)=m – однозначно определяется своим начальным вектором длины m.

Обозначение: множество всех ЛРП над Р с характеристическим многочленом F(x): pL(F).

Операции над последовательностями.

1. W=U+V; то есть: W(i)=U(i)+V(i);

2. CP, W=CU; W(i)=CU(i);

Определение: последовательности U₁, …, U_m  pL(F) – базис семейства ЛРП с характеристическим многочленом F(х), если:

1. VpL(F)  c₁, …, c_m: V=c₁U₁+…+c_mU_m;

2. Константы c₁, …, c_m – определены однозначно, то есть представление 1. – однозначно.

Определение: пусть UР^, h(x)= ;

 произведение последовательности U на многочлен h(x) – последовательность W=h(x)U;

Пример: x(U(0), U(1), U(2), …)=(U(1), U(2), …)

Свойства умножения последовательности на многочлен.

1. (A(x)+B(x))U=A(x)U+B(x)U;

2. (A(x)B(x))U=A(x)(B(x)U);

3. A(x)(U+V)=A(x)U+A(x)V;

Определение: характеристический многочлен наименьшей возможной степени – минимальный многочлен ЛРП: m_U(x).

Определение: импульсная последовательность с характерным многочленом f(x): e^fpL(f) – последовательность принадлежащая pL(f) с начальным вектором:

(0, ….., 0, 1)=e_m-1;

Определение: многочлен _U(x) из Т – генератор плоскости U.

Определение: аннулятор последовательности: A_nnU={g(x)P[x]g(x)U=0}.

Соотношения между семействами рекуррент.

1. pL(G)pL(F)  G(x)F(x);

2. L(G)L(F)=L((G,F));

3. L(G)+L(F)=L([G,F]);

4. (F(x),G(X))=  L(FG)=L(F)+L(G);

При этом представление каждой рекурренты из семейства L(FG) в виде суммы рекуррент из семейств L(F), L(G) – однозначно.

Биномиальные последовательности. Биномиальный базис.

Пусть P\0, биномиальная последовательность l-го порядка с корнем  - последовательность, знаки которой определяются по правилу:

Представление ЛРП через функцию “след”.

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

Список файлов учебной работы