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

Раздел Домостроительство
/
Вид работы: Домашние Задания
/
Теорема 2.1.2.

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

Выберите учебное заведение

Теорема 2.1.2.

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

1. R_d(a+b)=R_d{ R_d (a) + R_d (b) }

2 . R_d(a*b)=R_d{ R_d (a) *R_d (b) }

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

Используя алгоритм деления, можно найти наибольший общий Делитель двух целых чисел. Например, НОД (814, 187) находится следующим образом:

814 = 4x187 +66,

187 = 2x66+55,

66 = 1x55 + 11,

55 = 5x11 +0.

Так как НОД (814, 187) делит и 814, и 187, то он должен делить и остаток 66. Так как он делит и 187, и 66, то он делит и 55. Так как он делит и 66, и 55, то он делит и 11. С другой стороны, 11 делит 55, а поэтому и 66, и 187, и, наконец, также 814. Следовательно, НОД (814, 187) равен 11.

Теперь можно выразить 11 в виде линейной комбинации чисел 814 и 187, начиная снизу выписанной выше последовательности и поступая следующим образом:

11 = 66 — 1 x 55 = 66 – 1x (187- 2x 66) =

= 3 x 66 — 1 x 187 = 3 x 814 — 13 x 187.

Следовательно, мы выразили НОД (814, 187) в виде линейной комбинации чисел 814 и 187 с коэффициентами из кольца целых чисел, а именно

НОД (814, 187) = 3 x 814 — 13 x 187. '.

Эти рассуждения могут быть проведены в общем виде для произвольных целых чисел r и s и позволяют доказать приведенные ниже теорему и следствие.

Теорема 2.1.3 (алгоритм Евклида).Наибольший общий делитель двух различных ненулевых целых чисел r и s может быть вычислен итеративным применением алгоритма деления. Предположим, что r < s и оба эти числа положительны; тогда алгоритм состоит в следующем:

s = Q₁.r + r₁_,

r = Q₂.r₁+ r₂,

r= Q₃.r₂ + r₃,

r_n_-1=Q_n₊₁r_n.

и процесс заканчивается, когда полученный остаток равен нулю. Последний ненулевой остаток г_п равен наибольшему общему делителю.

Наконец, мы приходим к важному и интуитивно не очевидному результату теории чисел.

Следствие 2.1.4.Для любых целых чисел г и s & существуют целые числа а и Ьb, такие, что

НОД (r, s} = аr + bs.

Доказательство.Последний остаток в теореме 2.1.3 равен НОД(r,s). Воспользуемся множеством выписанных в этой теореме уравнений, чтобы исключить все остальные остатки. Это даст выражение для г в виде линейной комбинации r и s с целочисленными коэффициентами.

Развернуть

Открыть в широком формате

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 2.3.4.
(1) Rd(х)[a(х)+b(x)]= Rd(х)[a(х)]+ Rd(х)[b(х)] , (2 ) Rd(х)

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
Теорема 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п