Китайская теорема об остатках и её роль в представлении чисел в СОК
Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках. Эта теорема формулируется следующим образом.
Теорема. Пусть 
- попарно взаимно-простые числа, больше 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; просмотров: 184; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!