Китайские теоремы об остатках. Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел?

Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Китайская теорема об остатках будет доказана в два этапа. Сначала мы докажем един­ственность решения, а затем его существование.

Теорема.2.23.14. Для заданного множества из k целых положи­тельных попарно взаимно простых чисел m₁, m₂,..., m_к и множе­ства неотрицательных целых чисел с₁ с₂,..., с_к при с _i < m_i система сравнений

c_i = с (mod т _{i ;}), i=1,2,,k,

имеет

не более одного решения с в интервале 0≤ c > П^k_i-1 m_i

Доказательство. Предположим, что сиc' являются двумя лежащими в рассматриваемом интервале решениями. Тогда с =Q _i m _i +c _i и c'=Q _i 'm _i +c _i и, следовательно, с — с' кратно m _i для каждого i, а так как m _i по­парно взаимно просты, то с — с кратно П^k_i-1 m_i.. Но число с — с' лежит между — ( П^k_i-1 m_i — 1) и П^k_i-1 m_i — 1. Единственным по­ложительным числом, удовлетворяющим этим условиям, является с — с' =0. Следовательно, с = с'.

Для того чтобы практически найти решение выписанной в тео­реме 2.3.1 системы сравнений, воспользуемся следствием 2.1.4 из алгоритма Евклида, согласно которому в кольце целых чисел

НОД (г, s) = а г + b s для некоторых целых а и b.

Для заданного множества попарно взаимно простых положи­тельных целых чисел m₁, m₂,..., m_к, положим М = П^k_i-1 m_i и М_i = М/ m_i. Тогда НОД (М _i ,_ь т,) = 1, и, следовательно, суще­ствуют такие целые N _i, и n _i, что N _i M_i +n _i m _i =1.

Теперь можно доказать следующую теорему.

Теорема 2.23.25. Пусть М = П^k_i-1 m_i — произведение попарно взаимно простых положительных целых чисел, пусть М_i = М/ m_i,, и пусть N _i, удовлетворяют равенству N _i M_i +n _i m _i =1. Тогда единственным решением системы сравнений

c_i = с (mod т _i; ), i=1,2,,k, будет]

_k

c = ∑ N _i M_i c_i (mod M),

ⁱ⁼¹

Доказательство. Поскольку мы уже знаем, что решение рас­сматриваемой системы сравнений единственно, надо только дока­зать, что выписанное выше с действительно является решением. Но

_k

c = ∑ N _i M_i c_i (mod m_i )= N _i M_i c_i (mod m_i ),

ⁱ⁼¹

ибо m_i делит М _r при r≠i. Наконец, так как N _i M_i +n _i m _i =1. то N _i M_i =1(mod m_i ) и c_i = с (mod т _{i ;}), i=1,2,,k, что и завершает доказа­тельство.