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

Раздел Домостроительство
/
Вид работы: Домашние Задания
/
КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

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

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

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ - Домашнее Задание, раздел Домостроительство, ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ Когда Можно Однозначно Определить Целое Число, Если Заданы Только Его Выче...

Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Китайская теорема об остатках будет доказана в два этапа. Сначала мы докажем единственность решения, а затем его существование.

Теорема .2.23.14. Для заданного множества из k целых положительных попарно взаимно простых чисел m₁, m₂, ..., m_к и множества неотрицательных целых чисел с₁ с₂, ..., с_к при с_i < m_i система сравнений

c_i = с (mod т_i_;), i=1,2, ,k ,

имеет

не более одного решения с в интервале 0≤ c > П^k_i_-₁ m_i

Доказательство. Предположим, что сиc' являются двумя лежащими в рассматриваемом интервале решениями. Тогда с =Q_i m_i +c_i и c'=Q_i'm_i+c_i и, следовательно, с — с' кратно m_i для каждого i, а так как m_i попарно взаимно просты, то с — с кратно П^k_i_-₁m_i_.. Но число с — с' лежит между — (П^k_i_-₁m_i — 1) и П^k_i_-1m_i— 1. Единственным положительным числом, удовлетворяющим этим условиям, является с — с' =0. Следовательно, с = с' .

Для того чтобы практически найти решение выписанной в теореме 2.3.1 системы сравнений, воспользуемся следствием 2.1.4 из алгоритма Евклида, согласно которому в кольце целых чисел

НОД (г, s) =аг + bs для некоторых целых а и b.

Для заданного множества попарно взаимно простых положительных целых чисел m₁, m₂, ..., m_к, положим М = П^k_i_-₁m_i и М_i = М/ m_i. Тогда НОД (М_i,_ь т,) = 1, и, следовательно, существуют такие целые N_i, и n_i, что N_i M_i +n_im_i=1.

Теперь можно доказать следующую теорему.

Теорема 2.23.25. Пусть М = П^k_i_-₁m_i — произведение попарно взаимно простых положительных целых чисел, пусть М_i = М/ m_i,, и пусть N_i, удовлетворяют равенству N_i M_i +n_im_i=1.Тогда единственным решением системы сравнений

c_i = с (mod т_i;), i=1,2, ,k , будет]

c = ∑ N_iM_ic_i (mod M),

ⁱ⁼¹

Доказательство. Поскольку мы уже знаем, что решение рассматриваемой системы сравнений единственно, надо только доказать, что выписанное выше с действительно является решением. Но

c = ∑ N_iM_ic_i (mod m_i)= N_iM_ic_i (mod m_i),

ⁱ⁼¹

ибо m_i делит М_r при r≠i. Наконец, так как N_i M_i +n_im_i=1.то N_i M_i =1(mod m_i) и c_i = с (mod т_i_;), i=1,2, ,k , что и завершает доказательство.

Развернуть

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

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

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

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

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

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

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

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

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

Доказательство.
(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.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п