Китайская теорема об остатках для двух элементов

1. Китайская теорема об остатках для двух элементов

Пусть m, n - два взаимно простых целых числа.
Тогда для любой пары (a, b) целых чисел
существует целое число с такое, что
x a(mod m),
x b(mod n)
тогда и только тогда, когда x c(mod m·n)
если с1 другое решение этой системы, то
с c1(mod m·n).

2. Пример:

Рассмотрим два простых числа n=31, m=17.
Соответствующие им коэффициенты Безу
u= -6, v=11, т.е.
-6·31 + 11·17 = 1
Произведение n на m равно 527. Для данных y и z
система
x y (mod 31)
x z (mod 17)
имеет решение 11·17·y+31·(-6)·z.

3. Вычислительные формулы.

Вычисление
х = n·(u·( b - a) mod m) + a,
дает единственное целое число из
интервала [0, n·m), удовлетворяющее
сравнениям
x a(mod n),
x b(mod m).

4. Пример:

Исходные данные: n = 31, m = 17, u =-6,
y = 24, z = 9. Сначала подсчитаем
u(z - y) mod m = -6· (9 – 24) mod 17 = -12,
умножаем это на n и прибавляем y.
Получаем х = 31·(-12) + 24 = 179, что и
является решением.

5. Китайская теорема об остатках для r элементов

Пусть n1 ,n2, …, nr - попарно взаимно простые числа.
Пусть а1 ,а2, …, аr произвольно целые числа. Тогда
система
x a1 (mod n1 );
x a (mod n );
2
2
.......... .......... ..;
x a r (mod n r );
имеет по крайней мере одно решение. Кроме того,
если х' – другое решение этой системы, то
х х'(mod n1·n2· …·nr ).

6. Вычислительные формулы.

Пусть n1 ,n2, …, nr - попарно взаимно простые числа. Тогда решения
системы сравнений х хi(mod ni). находятся из последовательности
вычислений:
y 1 x 1 mod n1,
y N (C ( x y ) mod n ) y ,
2
2
2
2
1
2
1
y 3 N3 (C 3 ( x 3 y 2 ) mod n 3 ) y 2 ,
.......... .......... ........
y r Nr (C r ( x r y r 1 ) mod n r ) y r 1,
в которой Ni
n
j i
j
коэффициент Ci удовлетворяет
условиям CiNi 1(mod ni) и получены при помощи алгоритма Евклида
для Ni и ni. При этих условиях число yr будет единственным
решением системы сравнений на интервале [0, n1·n2· …·nr )