§ 8.4. Китайским алгоритм остатков: общий случай

Мы в деталях проанализировали решение системы линейных сравнений для взаимно простых модулей потому, что именно этот случай встретится нам в следующих главах. Однако

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

Из первого сравнения мы получаем: для некоторого целого у. Подставляя найденное выражение для х во второе сравнение системы, имеем: . Так как делит 16, последнее сравнение должно иметь решение. Действительно, его целочисленный эквивалент имеет вид: Разделим это равенство на 4: т. е. . Но , так что . Следовательно, для некоторого целого к. Наконец, подставляя вместо у в равенство находим Итак, данная система имеет единственное решение по модулю 24. Однако Так какое же отношение число 24 имеет к модулям 8 и 12? Ответ на этот вопрос найдете в упражнении 5.

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

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

Заполняя таким образом таблицу для не взаимно простых модулей, мы вернемся в клетку с координатами (0,0), не перебрав всех чисел. Это объясняет, почему некоторые клетки таблицы останутся пустыми. Для таблица выглядит следующим образом:

(см. скан)