КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

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

Теорема .2.23.14. Для заданного множества из k целых положи­тельных попарно взаимно простых чисел m1, m2, ..., mк и множе­ства неотрицательных целых чисел с1 с2, ..., ск при сi < mi система сравнений

ci = с (mod тi;), i=1,2, ,k ,

 

имеет

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

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

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

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

Для заданного множества попарно взаимно простых положи­тельных целых чисел m1, m2, ..., mк, положим М = Пki-1 mi и Мi = М/ mi. Тогда НОД (Мi,ь т,) = 1, и, следовательно, суще­ствуют такие целые Ni, и ni, что Ni Mi +nimi=1.

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

Теорема 2.23.25. Пусть М = Пki-1 mi произведение попарно взаимно простых положительных целых чисел, пусть Мi = М/ mi,, и пусть Ni, удовлетворяют равенству Ni Mi +nimi=1.Тогда единственным решением системы сравнений

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

k

c = ∑ Ni Mi ci (mod M),

i=1

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

k

c = ∑ Ni Mi ci (mod mi)= Ni Mi ci (mod mi),

i=1

ибо mi делит Мr при r≠i. Наконец, так как Ni Mi +nimi=1.то Ni Mi =1(mod mi) и ci = с (mod тi;), i=1,2, ,k , что и завершает доказа­тельство.