Система сравнений первой степени. Китайская теорема об остатках.

Рассмотрим систему сравнений

*

От системы сравнений вида a_ix ≡ b_i (mod m_i) можно перейти к данной способом, указанным в п.1.

Китайская теорема об остатках (I век до н.э. Сунь-Цзе)

Пусть m₁,…, m_k – попарно простые числа система сравнений (*) имеет единственное решение x₀ ≡ **,

где M= , M_i= , .

Доказательство:

Т.к. m_s\M_j

система (*) равносильна системе

***

т.е. системам (*) и (***) удовлетворяют одни и те же значения x. Системе (***) (в силу свойств 12 и 13 сравнений) удовлетворяют те и только те значения, которые заданы теоремой (т.е. x₀).

□

Следствие.

Если в системе ** независимо друг от друга пробегают полные системы вычетов по модулям соответственно, то пробегает полную систему вычетов по модулю M.

Доказательство: в силу свойства 13 сравнений, x₀ пробегает ровно M не сравнимых по модулю M значений.

□

Пример

Решить систему сравнений:

mi
Mi

Вычислим параметры, необходимые для нахождения решения. Составим таблицу

Согласно китайской теореме об остатках, решением будет являться

x₀≡1∙20∙2+2∙15∙3+4∙12∙3(mod 60)≡40+90+144(mod 60)≡34(mod 60).

Ответ: x≡34(mod 60).

Проверка:

Решение верно.