Реферат Курсовая Конспект
КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ - Домашнее Задание, раздел Домостроительство, ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ Когда Можно Однозначно Определить Целое Число, Если Заданы Только Его Выче...
|
Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Китайская теорема об остатках будет доказана в два этапа. Сначала мы докажем единственность решения, а затем его существование.
Теорема .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 , что и завершает доказательство.
– Конец работы –
Эта тема принадлежит разделу:
ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА... ДЛЯ СТУДЕНТОВ ДНЕВНОГО ОТДЕЛЕНИЯ СПЕЦИАЛЬНОСТИ КИРИШКИЙ ФИЛИАЛ... ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов