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

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

Теорема 10.2.1. Для заданного множества целых положительных попарно взаимно простых чисел и множества неотрицательных целых чисел при система сравнений

имеет не более одного решения с в интервале

Доказательство. Предположим, что с и с являются двумя лежащими в рассматриваемом интервале решениями. Тогда

и, следовательно, кратно для каждого а так как попарно взаимно просты, то кратно Но число лежит между Единственным положительным числом, удовлетворяющим этим условиям, является Следовательно,

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

Для заданного множества попарно взаимно простых положительных целых чисел тк положим и Тогда следовательно, существуют такие целые что

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

Теорема 10.2.2. Пусть произведение попарно взаимно простых положительных целых чисел, пусть и пусть удовлетворяют равенству Тогда единственным решением системы сравнений

будет

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

ибо делит при Наконец, так как то что и завершает доказательство.

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

Теорема 10.2.3. Для заданного множества попарно взаимно простых многочленов и множества многочленов таких, что система сравнений

имеет не более одного решения с удовлетворяющего условию

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

и

так что разность с кратна многочлену для каждого Тогда многочлен с кратен и многочлену причем

Следовательно, с и доказательство закончено. Так же как и в кольце целых чисел, в кольце многочленов над произвольным полем выполняется равенство

для некоторых и Для заданного множества попарно взаимно простых положим и допустим, что удовлетворяют равенствам ; согласно следствию 4.3.7, такие многочлены всегда существуют.

Теорема 10.2.4. Пусть произведение попарно взаимно простых многочленов, и пусть

и удовлетворяют равенствам Тогда единственным решением системы сравнений

является

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

ибо делит если Наконец, так как

то что и завершает доказательство.

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

Теорема 10.2.5. Если длины циклических кодов и взаимно просты, то при соответствующем расположении компонент в кодовом слове код-произведение также является циклическим.

Доказательство. Если то, согласно китайской теореме об остатках, имеется единственное целое число лежащее в интервале и удовлетворяющее сравнениям

Перепишем кодовое слово с в следующем порядке:

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

Так как этот многочлен является кодовым словом, то и является кодовым словом.

Взаимосвязь между с и с можно лучше пояснить с помощью следующей двумерной таблицы.

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