Китайская теорема об остатках и её роль в представлении чисел в СОК
Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках. Эта теорема формулируется следующим образом.
Теорема. Пусть - попарно взаимно-простые числа, больше 1, и пусть . Тогда существует единственное неотрицательное решение по модулю Р следующей системы сравнений:
…, (3.1)
Другими словами, отображение, которое каждому целому числу х, , ставит в соответствие кортеж , где , , является биекцией кольца на декартово произведение
колец .
Существует много различных доказательств этой теоремы. Приведём конструктивное доказательство китайской теоремы об остатках.
Доказательство. Найдём число х, , удовлетворяющее одновременно всем сравнениям, указанным в теореме. Систему сравнений будем решать присоединением на каждом шаге нового сравнения. Первое сравнение справедливо для всякого целого числа х вида где q1 – произвольное целое число. Для нахождения q1 подставим значение х во второе сравнение системы, после чего получим откуда где - обратный мультипликативный элемент к по модулю . Такой элемент существует, так как Найденное таким образом q1 можно записать в виде
для некоторого целого числа . Подставив значение в выражение
Теперь первые два сравнения могут быть заменены на одно
(3.2)
Применим теперь описанную процедуру к сравнению (3.2) и к одному из оставшихся сравнений системы (3.1). Повторяя этот процесс k – 1 раз, мы в конечном итоге найдём число х, удовлетворяющее всем сравнениям системы (3.1).
|
|
Докажем единственность решения системы (3.1). Воспользуемся методом от противного. Предположим, что существует другое решение системы (3.1). Тогда
для всех . Вычитая почленно из первого сравнения второе, получим истинное сравнение откуда следует, что . Но тогда , следовательно, , так как . Этим завершается доказательство китайской теоремы об остатках.
Пример. Решим систему сравнений
Решение. Так как модули 13, 15, 19 попарно взаимно простые числа, то данная система имеет единственное решение по модулю . Сравнение соответствует диофантовому уравнению , где . Заменяя х во втором сравнении системы на , получаем , т. е. . К числу 13 обратным мультипликативным элементом по модулю 15 является число 7. Умножая последнее сравнение на 7 и, переходя в нём к вычетам по модулю 15, получим . Таким образом, . Следовательно, , при этом все числа вида являются решениями первых двух сравнений данной системы. Подставим в третье сравнение вместо х полученное выше значение или . Так как (5, 19) = 1, то или . Итак,
|
|
, то есть х = 274.
Исходя из конструктивного доказательства китайской теоремы об остатках, можно записать алгоритм решения системы линейных сравнений рассматриваемого вида следующим образом (греко-китайский алгоритм).
Вход: Пары , такие, что , , где каждое > 1 и ( , ) = 1 для и - короткие целые числа.
Выход: х – единственное наименьшее неотрицательное решение системы по модулю .
1. Инициализация. Р:=1; х:=МОД( , ) – подпрограмма нахождения остатка деления на .
2. Цикл для i от 1 до n – 1: MOДINV(p, );
q:=МОД(
3. х:= х + pq, где MOДINV – подпрограмма вычисления мультипликативного обратного элемента.
4. q:=МОД(
5. Вернуть х.
Несложный анализ времени работы данного алгоритма показывает, что
где - количество цифр числа Р, т. е. длина числа Р, при этом функция L ведёт себя как логарифм.
Дата добавления: 2019-07-15; просмотров: 174; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!