|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[242] Объясните свой ответ. 33.4-4* Пусть /(ж) = /о + f\x + • • • + ftxt (mod р) - многочлен степени t с коэффициентами /г- £ Zp (где р - простое число). Назовём а £ Ъ,р нулём (zero) многочлена /, если f(a) = 0 (mod р). Докажите, что если а - нуль многочлена /, то найдётся многочлен д(х) степени t - 1, для которого /(ж) = (ж - а)д(х) (mod р). Выведите отсюда, что многочлен степени t имеет не более t нулей (в Ъ,р). 33.5. Китайская теорема об остатках Около 100 г. до Р.Х. китайский математик Сун Цу (Sun-Tsu) решил такую задачу: найти число, дающее при делении на 3, 5 и 7 остатки 2, 3 и 2 соответственно (общий вид решения - 23 + 105/г при целых к). Поэтому утверждение об эквивалентности системы сравнений по взаимно простым модулям и сравнения по модулю произведений называют «китайской теоремой об остатках». Пусть некоторое число п представлено в виде произведения попарно взаимно простых чисел riin2 ... пк. Китайская теорема об остатках утверждает, что кольцо вычетов Ъп устроено как произведение колец вычетов Zrai X Z„2 X • • • X ЪПк (с покомпонентным сложением и умножением). Это соответствие полезно и с алгоритмической точки зрения, так как бывает проще выполнить операции во всех множествах Zraj, чем непосредственно в Ъп. Теорема 33.27 (Китайская теорема об остатках) Пусть п = п\П2 пь, где щ, ,пь попарно взаимно просты. Рассмотрим соответствие а <н> (аь а2,... , ак),(33.25) где а £ Ъп, а{ £ ЪПг и аг- = а mod п, при г = 1,2,...,к. Формула (33.25) определяет взаимно однозначное соответствие между Ъп и декартовым произведением Zrai X Z„2 X • • • X ЪПк. При этом операциям сложения, вычитания и умножения в Ъп соответствуют покомпонентные операции над /г-элементными кортежами: если а (а1,а2,... ,ак) и Ь (h, b2, , bk), то (a-\-b) mod n -H- ((ai+bi) mod щ, (a2-\-b2) mod n2, (a-b) mod n -H- ((ai - bi) mod щ, (a2 - b2) mod n2, •• • , (an+bn) mod nk (33.26) •• • , (an-bn) mod nk (33.27) (ab) mod га -и- ((ai&i) mod щ, (а2Ь2) mod п2, , (anbn) mod пк). (33.28) Доказательство Заметим прежде всего, что формула (33.25) действительно задаёт корректно определённое отображение Ъп в указанное произведение: если два числа сравнимы по модулю га, то их разность кратна га, и потому эти числа дают одинаковые остатки при делении на любое из гц (так как гц га). Обратное отображение также легко описать. Положим ггц = п/щ, где г = 1, 2,... , к, то есть ггц = п\п2 ...... nk. Оче- видно, ггц = 0 (mod rij) при гф j. Положим d = ггц(т~1 mod щ)(33.29) при г = 1,2,... , к. Тогда сг- = 1 (mod га)г- и сг- = 0 (mod n)j при j ф г, и числу сг- соответствует набор с одной единицей на г-м месте: с,- (0,0,... ,0,1,0,... ,0). Тем самым, положив а = (a\Ci + а2С2 + .. .afccfc) (mod га).(33.30) мы получим число, соответствующее набору (а\, а2, , ак). Тем самым для каждого набора можно найти соответствующий элемент Ъп. Осталось убедиться, что такой элемент только один. Можно сослаться на то, что и слева, и справа у нас имеются множества из га = raira2 .. .nk элементов, и потому всякая сюръекция является биекцией. А можно заметить, что если а и а дают одинаковые остатки при делении на все щ, то а - а делится на все щ и в силу взаимной простоты на их произведение, то есть на га (это легко следует из однозначности разложения на множители). Следствие 33.28 Если щ, п2,... ,пк попарно взаимно просты и га = raira2 • • -га, то система сравнений х = aj (mod гц) относительно х (где г = 1,2,... , Аг) имеет единственное решение по модулю га. Следствие 33.29 Если щ, п2,... ,пк попарно взаимно просты, га = raira2 • • • пк, а х на - целые числа, то свойство х = a (mod га) равносильно выполнению сравнений х = a (mod гц) Рис. 33.3 33.3 Китайская теорема об остатка: п\ = 5, п2 = 13. В столбцах перечислены различные остатки при делении на 13, в строках - при делении на 5. Каждое число от 0 до 65 - 1 помещено в соответствующую строку и столбец, и теорема гарантирует, что в каждой клетке таблицы будет по одному числу. при всех г = 1, 2,... , к. В качестве примера рассмотрим систему сравнений а = 2 (mod 5), а = 3 (mod 13). Здесь а\ = 2, аз = 3, п\ = т2 = 5, п2 = т\ = 13, и следовательно, п = 65. Поскольку 13-1 = 2 (mod 5) и 5-1 = 8 (mod 13), мы находим ci = 13(2 mod 5) 26, с2 = 5(8 mod 13) 40, и а = 2-26 + 3-40 (mod 65) =52+ 120 (mod 65) =42 (mod 65). См. также рис. 33.3. Таким образом, вычисления по модулю произведения взаимно простых чисел можно выполнять отдельно по модулю каждого из этих чисел. Упражнения 33.5-1 Найдите все ж, при которых ж = 4 (mod 5) и ж = 5 (mod 11). 33.5-2 Найдите все целые числа ж, дающие при делении на 2, 3, 4, 5, 6 остатки 1, 2, 3, 4, 5 (соответственно). 33.5-3 Докажите, что (в контексте теоремы 33.27) при gcd(a,ra) = 1 имеет место соответствие (a-1 mod п) -и- ({а1 mod rai), (a2l mod n2),... , (a1 mod пк)). 33.5-4 Пусть /(ж) - многочлен с целыми коэффициентами. Докажите, что (в условиях теоремы 33.27) число его корней по модулю п (вычетов, для которых /(ж) = 0 (mod п)) равно произведению чисел его корней по модулям щ, п2,... ,пк. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||