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

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

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

Пример:
Исходные данные: 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, что и является решением.

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