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

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

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

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ - Домашнее Задание, раздел Домостроительство, Лекции и домашнии задания по курсу токбдискретная математика введение в дискретную алгебру Когда Можно Однозначно Определить Целое Число, Если Заданы Только Его Выче...

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

Теорема .2.23.14. Для заданного множества из k целых положи­тельных попарно взаимно простых чисел m1, m2, ..., mк и множе­ства неотрицательных целых чисел с1 с2, ..., ск при сi < mi система сравнений

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

 

имеет

не более одного решения с в интервале 0≤ c > Пki-1 mi

Доказательство. Предположим, что сиc' являются двумя лежащими в рассматриваемом интервале решениями. Тогда с =Qi mi +ci и c'=Qi'mi+ci и, следовательно, с — с' кратно mi для каждого i, а так как mi по­парно взаимно просты, то с — с кратно Пki-1 mi .. Но число с — с' лежит между — (Пki-1 mi — 1) и Пki-1 mi— 1. Единственным по­ложительным числом, удовлетворяющим этим условиям, является с — с' =0. Следовательно, с = с' .

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

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

Для заданного множества попарно взаимно простых положи­тельных целых чисел m1, m2, ..., mк, положим М = Пki-1 mi и Мi = М/ mi. Тогда НОД (Мi,ь т,) = 1, и, следовательно, суще­ствуют такие целые Ni, и ni, что Ni Mi +nimi=1.

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

Теорема 2.23.25. Пусть М = Пki-1 mi произведение попарно взаимно простых положительных целых чисел, пусть Мi = М/ mi,, и пусть Ni, удовлетворяют равенству Ni Mi +nimi=1.Тогда единственным решением системы сравнений

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

k

c = ∑ Ni Mi ci (mod M),

i=1

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

k

c = ∑ Ni Mi ci (mod mi)= Ni Mi ci (mod mi),

i=1

ибо mi делит Мr при r≠i. Наконец, так как Ni Mi +nimi=1.то Ni Mi =1(mod mi) и ci = с (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п

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