Китайская теорема об остатках

x≡a1 mod m1,x≡a2 mod m2,…x≡ak mod mk, (10)
где mi0, ai – заданные целые числа. Решение такой системы в одном важном частном случае может быть получено достаточно легко. Следующее утверждение было известно в Китае около двух тысячелетий тому назад и сейчас носит название «китайская теорема об остатках».
Теорема 8. Если числа mi, i=1, k, попарно взаимно просты, то системы сравнений (10) разрешима. Если для целых чисел M, Mi, bi выполнены соотношения
M=m1⋅…⋅mk, Mi=Mmi, Mibi≡ai mod mi, 1≤i≤k,
x0=i=1kMibi, (11)
то множество целых чисел, удовлетворяющих системе сравнений (10), составляет класс вычетов x≡x0 mod M.
Доказательство. Так как Mj нацело делятся на mi при j≠i, то при любом i выполняются сравнения
x0≡Mibi≡ai mod mi.
Это означает, что множество целых чисел, удовлетворяющих системе (10) и системе
x≡x0 mod mi, i=1, k,
совпадают.
Последние сравнения выполняются в том и только том случае, если x-x0 нацело делится на mi, i=1, k

. Учитывая попарную взаимную простоту модулей mi, можно сделать вывод, что последнее свойство выполняется для тех и только тех чисел x, для которых x-x0 нацело делится на M, то есть x≡x0 mod M. Теорема доказана.
Следствие 1. Если числа a1, a2, …, ak независимо друг от друга пробегают полные системы вычетов по модулям m1, m2, …, mk соответственно, то числа x0 ,определенные для каждого набора a1, a2, …, ak с помощью равенств (11), пробегают полную систему вычетов по модулю M=m1⋅…⋅mk.
Доказательство