рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Теорема 2.3.4.

Теорема 2.3.4. - Домашнее Задание, раздел Домостроительство, ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ (1) RD(Х)[A(Х)+B(X)]= RD...

(1) Rd(х)[a(х)+b(x)]= Rd(х)[a(х)]+ Rd(х)[b(х)]

, (2 ) Rd(х)[a(х)b(x)]= Rd(х)[ Rd(х)[a(х)] Rd(х)[b(х)].]

Доказательствосводится к упражнению: использовать алгоритм деления для выражений в обеих частях равенства и приравнять остатки.

 

Подобно тому как часто бывает полезным представление положительных целых чисел в виде произведения простых сомножителей, часто бывает полезным представление приведенных много­
членов в виде произведения простых многочленов.

 

 

Теорема 2.3.5 (теорема об однозначном разложении).Ненулевой многочлен p(х) над некоторым полем однозначно (с точностью до порядка следования множителей) разлагается в произведение элемента поля и простых многочленов над этим полем

Доказательство.Ясно, что входящим в произведение элементом поля должен быть коэффициент рп-1, где п-1 —степень многочлена р (х). Можно пренебречь этим элементом и доказывать теорему для приведенных многочленов.

Предположим, что теорема не верна. Пусть р (х) — приведенный многочлен наименьшей степени, для которого не верна теорема. Тогда имеются два разложения:

р (х) = а1 (х) а2 (х) ... ак(х) = b1(х) b2 (х) ... bl(х),,

где ai(х) и bi(х) — простые многочлены.

Все многочлены ai(х) должны отличаться от всех многочле­нов bi (х), так как в противном случае можно было бы сократить общие члены и получить многочлен меньшей степени, который можно разложить двумя разными способами.

Без потери общности предположим, что степень многочлена b1(х) не больше степени многочлена а1(х). Тогда

 

a1(х) = b1(х) Н(х) + s (х), где deg s(х)< deg b(х)< deg a(х). Далее,

 

s(x) а2 (х) ... ак(х) = b1(х) { b2 (х) ... bl(х) — Н (х) а2 (х) ... ак(х)}

.
Разложим многочлен s(х) и многочлен, стоящий в квадратных скобках, на простые множители, разделив, если надо, на соответствующий элемент поля так, чтобы все множители были приведенными. Поскольку b1 (х) не содержится в левой части, мы получили два различных разложения приведенного многочлена, степень которого меньше степени р (х). Это противоречие доказывает теорему.

 

В силу теоремы об однозначном разложении теперь ясно, что для любых двух многочленов

 

r(х) и b(х) НОД[r(х), b(х)] и НОК[r(х), b(х)] являются единственными, так как наибольший общий делитель равен произведению всех общих для r(х) и b(х) простых делителей, причем каждый делитель входит в наименьшей из степеней, в которых он входит в r(х) и в b(x), а наименьшее общее кратное равно произведению всех простых делителей, входящих либо в r (х), либо в b(х), причем *"каждый делитель входит в наибольшей из степеней, в которых он входит в r(х) или в b(х). Далее, любой многочлен, делящий как r(х), так и b(х), делит НОД{r(х), b (х)}, а любой многочлен, делящийся и на r(х), и на b(х), делится на НОК[r (х), b(х)].

Из алгоритма деления многочленов вытекает важное следствие, известнее под названием алгоритма Евклида для многочленов.

Теорема 2.3.6 ( алгоритм Евклида для многочленов).Наибольший общий делитель двух многочленов r(х) и s(х) над полем GF(q) можно вычислить с помощью итеративного приме­нения алгоритма деления. Если 0≤ deg r(x) ≤ deg s(x), то последовательность вычислений такова:

s(x) =Q1(x) r(x) +r1(x)

r(x) =Q2(x) r2 (x) +r3(x)

r1(x) =Q3(x) r2(x) +r4(x)

.

rп-1(x) =Qn+1(x) rп(x),

и процесс обрывается, как только получается равный нулю остаток..

Тогда rп(х) = а НОД [r(х), s(х)], где а некоторый скаляр.

Доказательство.Отправляясь от первого уравнения, видим, что НОД[r(х),s(х)] делит и делимое, и делитель, и, следовательно, остаток. Проводя это рассуждение далее по всем уравнениям, видим, что НОД[r(x), s(х)] делит rn (х). Отправляясь от последнего уравнения, видим, что rп(х) делит делитель и остаток, так что он делит и делимое. Проводя это рассуждение по всем уравнениям вплоть до первого, видим, что rn(х) делит НОД [r(х), s(х)].Так как rп(х) делит НОД[r(х),s(х)] и делится на него, то получаем утверждение теоремы.

 

Следствие 2.3.7.НОД[r(х), s(х) ] = а(х) r(х) + b(х) s(х), где а(х) и b(х) многочлены над GF(q).

Доказательство.Последнее уравнение с ненулевым остатком в утверждении предыдущей теоремы дает выражение многочлена rп (х) через rп-1 (х) и _rn-2(х). Перебирая уравнения снизу вверх, исключаем сначала rп-1(х), затем rп-2(х), и т. д. и в конце концов получим выражение rп (х) только через r(х) и s(х).

 

+ 0 1 * 0 1
0 1 1 0 0 0 0 1

Для произвольного элемента β поля GF(q) можно вычислить значение многочлена над GF(q) в этой точке, подставив элемент β вместо неопределенной переменной. Например, пусть над GF(3)

р (х)=2x5+x4 +x2 +2.-...Тогда получаем

р (0) = 2-О5 + О4 + О2 + 2 = 2,

+ 0 1 2 3 * 0 1 2 3
0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 0 0 0 0 0 1 2 3 0 2 3 1 0 3 1 2
+ 0 1 2 3 * 0 1 2 3
0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 0 0 0 0 0 1 2 3 0 2 3 1 0 3 1 2

р(I)=2·15+14+12 + 2 = 0,

р (2) =2·25 + 24 + 22 + 2 = 2.

+ 0 1 * 0 1
0 1 1 0 0 0 0 1

 

Рис2.1 Пример полей GF(2) и GF(4)

 

 

Рис2.1 Пример полей GF(2) и GF(4)

В случае поля вещественных чисел известной процедурой является вычисление значений многочлена в расширении этого поля; широко применяется вычисление значений многочлена с веществен­ными коэффициентами в поле комплексных чисел. Аналогично мо жно вычислять значения многочлена над GF(q) в расширении поля GF(q).Такое вычисление проводится подстановкой элементов из расширения поля вместо неопределенной переменной х и выполнения операций в расширении поля. Например, пусть над GF(2)

р (х) = х3 + х + 1.

Тогда (см. рис. 2.1) для элементов поля СР (4)имеем

р (0) = О3 + 0 + 1 = 1,

р (1) = I3 + 1 + 1 = 1,

р (2) = 23 + 2 + 1 = 2,

р (3) = З3 + 3 + 1 = 3.

Если p(β) = 0, то элемент β называется корнем многочлена p(х) или корнем уравнения p(х) = 0. Многочлен не обязательно имеет корни в своем собственном поле. Многочлен

p(x)= х3 + х + 1 не имеет корней в GF(2), а также в GF(4).

Теорема 2.3.8.Элемент β является корнем многочлена р (х) тогда только тогда, когда (х- β) делит р (х). Более того, корнями многочлена р (х) степени п являются не более п элементов поля.

Доказательство.Согласно алгоритму деления, р (х) = (Х - β) Q (х) + s(х),

где степень s(х) меньше единицы. Таким образом, s(х) является элементом поля s0. Следовательно, 0 = р (β) = (β — β) Q (β) + s0. и соответственно s(х) = s0 = 0

Обратно, если х -β делит р (х), то

р (х) = (x - β) Q(х),

так что р (β)= (β -β) Q(β) = 0, и, таким образом, β — корень многочлена р (х).Разложим теперь многочлен р (х) в произведение элемента поля и простых множителей. Степень многочлена р (х) равна сумме степеней простых множителей, и для каждого корня имеется один такой множитель. Следовательно, существует не более п корней.

 

– Конец работы –

Эта тема принадлежит разделу:

ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ

ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА... ДЛЯ СТУДЕНТОВ ДНЕВНОГО ОТДЕЛЕНИЯ СПЕЦИАЛЬНОСТИ КИРИШКИЙ ФИЛИАЛ... ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Теорема 2.3.4.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Доказательство.
(1). аО = а (0 + 0) = аО + аО. Вычитая из обеих частей равенства аО, получаем 0 = аО. Вторая часть утверждения (1) доказывается аналогично, (2). О = аО = а (b — b) = аb

Теорема 1.2.4.
(1) Множество единиц кольца образует группу относительно умножения в кольце (2) Если с = аb и с — единица, то а имеет правый обратный, а b — левый о

ВЕКТОРНЫЕ ПРОСТРАНСТВА
Известный пример векторного пространства дает трехмерное евклидово пространство, фигурирующее во многих физических задачах. Его обобщением является n-мерное векторное пространство над полем веществ

ЛИНЕЙНАЯ АЛГЕБРА
  Широко используемые разделы прикладной математики — линейная алгебра, в частности теория матриц, — обычно изучаются только для поля вещественных чисел и поля комплексных чисел, одна

Теорема 12.56.3.
10) Если все элементы некоторой строки квадратной матрицы равны нулю, то определитель этой матрицы равен нулю., 2П) Определитель матрицы равен определителю транспони­рованной мат

КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ
| Множество всех целых чисел (положительных, отрицательных и нуля) образуют кольцо относительно обычных операций сложе­ния и умножения. Это кольцо принято обозначать через Z. В данном пара

Теорема 2.1.2.
1. Rd(a+b)=Rd{ Rd (a) + Rd (b) } 2 . Rd(a*b)=Rd{ Rd (a) *Rd (b

КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
Имеется очень важная конструкция, позволяющая по заданному кольцу построить новое кольцо, называемое кольцом отношений. В случае произвольного кольца для построения кольца отноше­ний строятс

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Китайская теорема об остатк

КОЛЬЦА МНОГОЧЛЕНОВ
Многочленом над полем GF(q) называется математическое выра­жение f(x)= fn-1 xn-1+fn-2 xn

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
Теорема 2.3.8. Для заданного множества попарно взаимно простых многочленов т1 (х), m2(х), ..., тk (х) и множества многочленов с1 (х),

КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦАХ МНОГОЧЛЕНОВ
Конечные поля можно построить из колец многочленов таким же образом, каким были построены поля из кольца целых чисел. Пусть имеется кольцо многочленов F [х] над полем F. Так же, как б

Степень Простые многочлены
2 x2 +x +1 3 x3 +x +1 4 x4 +x +1 5 x5 +x2 +1 6 x6 +x +1 7 x7 +x3

ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ
В предыдущем параграфе было построено поле GF(4). На рис. 2.2 видно, , за исключением нуля, все элементы поля могут быть представлены в виде степени элемента х. Опред

СТРУКТУРА КОНЕЧНОГО ПОЛЯ
Ранее в данной главе мы изучали, как строить поле. Предполагая, что можно найти простой многочлен степени п над полем άGF (q), мы научились строить конечное поле с qп

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги