Математические основы системы остаточных классов (стр. 3 из 19)
Там же доказывается, что время выполнения алгоритма Евклида оценивается равенством
, где L(a) и L(b) – число цифр в а и b соответственно. В правом столбце этого алгоритма каждый остаток выражен через 
. Надо вычислить 
и 
. Очевидно, что 
и 
. Сравнивая обе части на i-м шаге, получим 
откуда получается следующая индуктивная процедура вычисления
и : 
Пример. Применим расширенный алгоритм Евклида к числам а = 342, b = 612. Весь алгоритм представим в виде следующей таблицы.
Расширенный алгоритм Евклида
| Номер итерации | q | A0 | a1 | x0 | x1 | Y0 | y1 |
| 0 | - | 342 | 612 | 1 | 0 | 0 | 1 |
| 1 | 0 | 612 | 342 | 0 | 1 | 1 | 0 |
| 2 | 1 | 342 | 270 | 1 | -1 | 0 | 1 |
| 3 | 1 | 270 | 72 | -1 | 2 | 1 | -1 |
| 4 | 3 | 72 | 54 | 2 | -7 | -1 | 4 |
| 5 | 1 | 54 | 18 | -7 | 9 | 4 | -5 |
| 6 | 3 | 18 | 0 | 9 | -34 | -5 | 19 |
Заметим, что равенство
выполняется на каждом шаге итерации. Алгоритм выдаёт d = 18, x = 9, y = -5 и тогда 18=342∙9 + 612∙(-5).§ 3. Китайская теорема об остатках и её роль в представлении чисел в СОК
Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках. Эта теорема формулируется следующим образом.
Теорема. Пусть
- попарно взаимно-простые числа, больше 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.Исходя из конструктивного доказательства китайской теоремы об остатках, можно записать алгоритм решения системы линейных сравнений рассматриваемого вида следующим образом (греко-китайский алгоритм).