ЛЕКЦИИ~4 (Лекции Кузьмина)
Описание файла
Файл "ЛЕКЦИИ~4" внутри архива находится в следующих папках: Лекции Кузьмина, WORD6. Документ из архива "Лекции Кузьмина", который расположен в категории "". Всё это находится в предмете "линейная алгебра и аналитическая геометрия" из 1 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "алгебра и геометрия (линейная алгебра)" в общих файлах.
Онлайн просмотр документа "ЛЕКЦИИ~4"
Текст из документа "ЛЕКЦИИ~4"
Пусть Р- простое и Р½T(V)*T(U) Þ пусть Р½T(V) и ;
W(i+L+ )=U(i+L)+V(i+L+ )=U(i+L)+V(i+L); Þ V(i+L+ )=V(i+L) Þ V(i+L+ )=V(i+L) Þ V(i+L+ )= =V(i+L+ )=V(i+L) Þ по утв.2: противоречие; Þ T(W)=T(V)*T(U).
Ч.Т.Д.
-
пусть L(U)<L(V) Þ L(U)£L(V)-1;
L(W)<L(V)=max(L(V), L(U));
W(i+L(V)-1+T(W))=U(i+L(V)-1+ )+V(i+L(V)-1+T(W))=U(i+L(V)-1)+V(i+L(V)-1+T(W)), a L(W)£L(V)-1 Þ W(i+L(V)-1)=U(i+L(V)-1)+V(i+L(V)-1);Þ
V(i+L(V)-1)=V(i+L(V)-1+T(W))=V(i+L(V)-1+T(V)+T(V) )V(i+L(V)-1+T(V)); Þ мо определению4: для L.
Утверждение4: " U- периодическая однозначно представляется в виде суммы вырожденных и чисто периодических последовательностей.
Доказательство: так как U- периодическая Þ UÎpL(xl(xt-1)), a (xl, xt-1)=1 Þ L(xl(xt-1))= =L(xl)+L(xt-1) Þ U=U1+U2, где U1- вырожденная, U2- чисто периодическая.
Ч.Т.Д.
Периодические многочлены.
Определение: многочлен F(x)ÎP[x]- периодический, если $ tÎN, l>0: F(x)½xl(xt-1); (1);
Определение: наименьший min{ tÎN, для которого $ l: F(x)½xl(xt-1)}=T(F(x));
Þ если Т- период многочлена, то min{l>0: F(x)½xl(xT(F)-1)}=L(F(x));
Утверждение: если выполнено (1), то: T(F)½t; L(F)£l.
Доказательство: так как F(x)½xL(F)(xT(F)-1) Þ xL(F)½(F(x)= xL(F)G(x)), так как в противном случае L(F) можно было бы уменьшить, но L(F)- min. Þ G(x)½(xT(F)-1);
Чтобы: xL(F)G(x)½xl(xt-1) Þ L(F)£l (так как (xt-1) не делится на xL(F)) Þ
G(x)½(xT(F)-1)
G(x)½xl-L(F)(xt-1) Þ G(x)½(xt-1,xT(F)-1)=(x(t,T(F))-1), a (t,T(F))£T(F)- если меньше, то это противоречит с выбором T(F).
Определение: многочлен периодический если L(F)=0.
Утверждение: F(x)- периодический Û eF- чисто периодическая.
Доказательство: “Þ” F(x)½(xT(F)-1) Þ F(x)*H(x)=xT(F)-1, a F(x)*eF=0 Þ F(x)*H(x)*eF=0
Þ (xT(F)-1)eF=0 Þ eF- чисто периодическая.
“Ü” если eF- чисто периодическая, то (xt-1)eF=0 ~ eF(i+t)=eF(i), a то есть F(x)½(xt-1), F(x)- периодический.
Теорема: пусть F(x)- унитарный многочлен над полем, тоесть ÎР[х] Þ
-
$ L(F), T(F)
-
L(F)+T(F)£½R½m-1, где m=degF(x);
-
L(F)=0 Û F(0)¹0;
Доказательство: 1) 1, x(modF(x)), x2(modF(x)), ……- члены этой последовательности- многочлены вида: с0+с1х+…+cmxm-1;- остатки от деления на F(x), а таких остатков ½R½m<¥, а последовательность – бесконечная Þ она будет повторяться:
пусть xj(modF(x))=xk(modF(x));
F(x)½xj-xk=xjk(xj-k-1);
Þ L(F)£j*k, T(F)½(j-k), то есть $ L,F.
-
В нашей последовательности вычетов будут повторы. На куске L(F)+T(F)- все вычеты разные, то есть L(F)+T(F)£½R½m-1.
-
“Þ” L(F)=0 Þ F(x)½(xT(F)-1) ~ F(x)H(x)= xT(F)-1; F(0)H(0)=-1 Þ F(0)¹0;
“Ü” пусть F(0)¹0 Þ (F(x),x)=1, a F(x)½xL(F)(xT(F)-1) Þ F(x)½(xT(F)-1) Þ L(F)=0, как наименьшее.
Определение: O(F)=HOK порядков корней многочлена в его поле разложения.
!!! всюду дальше: F(0)¹0, то есть x не½F(x);
O(F)=HOK{ordaj, F(aj)=0}.
Теорема: пусть F(x) – неприводимый многочлен над полем P=GF(q); degF(x)=m; Þ T(F)=O(F); T(F)½qm-1;
Доказательство: a) пусть корни F(x): a1…am в GF(qm);
F(x)½(xT(F)-1) Þ F(x)H(x)= xT(F)-1 Þ F(aj)H(aj)= ~ordaj½T(F), то есть m- чисел, каждое делит T(F) Þ O(F)½T(F).
b) любой корень многочлена F(x) удовлетворяет уравнению:
xO(F)-1=0 Þ (x-aj)½(xO(F)-1) " a, a все aj попарно различные Þ P(x-aj)½ (xO(F)-1) Þ F(x)½(xO(F)-1) Þ T(F)½O(F).
a)+b) Þ T(F)=O(F);
Корни F(x): a1…am – образуют мультипликативную группу поля, а порядок каждого делит порядок группы: O(F)½qm-1.
Определение: если O(F)½qm-1; degF(x)=m; F(x)- над P=GF(q), то F(x)- многочлен максимального периода.
Теорема: GF(q), q=pn- характеристика поля;
Пусть где G1(x), …, Gt(x)- попарно различные неприводимые многочлены.
DegG(x)=mj Þ T(F(x))=O(F)*pc, где
Доказательство: F(x)½(xT(F)-1) Þ Gj(x)½(xT(F)-1) Þ O(Gj)½T(F), " j= Þ
HOK{ O(Gj), j= }½T(F); так как все различны и неприводимый xT(F)-1 Þ Gj(x) ½(xО(F)-1);
G1(x)*…*Gt(x) ½(xО(F)-1) Þ (G1…Gt)H(x)= (xО(F)-1); (G1…Gt) H (x)=(xО(F)-1) = xО(F)* -1;
, a F(x)½(G1…Gt) , так как , a (G1…Gt) ½ xО(F)* -1 Þ T(F)½O(F)*pc;
пусть a<c Þ a£c-1 Þ T(F) )½O(F)*pc-1, но этого не может быть: пусть
a (xO(F)-1)/=O(F)xO(F)-1 пусть в роле -F(x)- раскладывается на линейные множители и корни F(x) в этом поле образуют мультипликативную группу этого поля и ord Þ максимальная кратность корня = pc-1, а по условию - противоречие Þ T(F)= O(F)*pc-1.
Пример: (x+1)5(x2+x+1)3(x3+x+1)(x3+x2+1)2; GF(2)
все многочлены неприводимые:
-
корни
-
(x+1) Þ 1, ord1=1
-
x3+x+1-пусть корень a, GF(23) a3+a+1=0; a¹1, orda=7
-
x3+x2+1 Þ orda=7 (аналогично).
Для degF(x)=m Þ T(F)=qm-1;
Теорема: T(F)=qm-1 Û F(x)- неприводимый; orda= qm-1 ;
T(F)=O(F)*pc=qm-1; так как (p, qm-1)=1 Þ c=0 Þ F(x)= то есть rj=1;
- противоречие, Þ F(x)=G(x) Þ неприводимый; T(F)=orda=qm-1;
“Ü” просто проверка, что такие многочлены имеют такой Т.
Выборки из линейных рекуррент.
Определение: пусть UÎR¥- последовательность V- (l, d)- выборка, если V(i)=U(l+di).
Доказательство: V(i) =U(l+d(i+ ))=U(l+di+T(U) )=U(l+ di)=V(i);
Теорема: пусть F(x)- неприводимый над Р: degF(x)=m; UÎpL(F); V-(l-d)-выборка из U;
Þ VÎpL(F(x)), degG(x)½m;