Глава 8. Системы сравнений

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

§ 8.1. Линейные уравнения

Начнем со случая одного линейного уравнения:

в котором натуральное число. В § 5.7 мы видели, что это уравнение легко решается, если По теореме обратимости, взаимная простота чисел влечет обратимость а в Пусть а — соответствующий обратный элемент. Умножая на него сравнение (1.1), мы получаем:

Так как отсюда следует сравнение

что дает решение уравнения. В частности, если простое уравнение (1.1) всегда имеет решение.

Предположим теперь, что а не обратим в Напомним, что это равносильно условию Наличие решения у (1.1) означает, что найдутся элементы для которых

а это возможно только если делит Итак, если уравнение (1.1) имеет решение, то делится на Разумеется, в случае обратимости класса а в необходимое условие выполнено, поскольку тогда

Проверим, что обратное тоже верно. Пусть делит Тогда для некоторых натуральных и Сокращение равенства (1.2) на дает:

что равносильно сравнению Отметим, что сравнёние берется по модулю делителю исходного модуля Более того, так что новое сравнение должно иметь решение. Итак, мы доказали, что если делит то множество решений уравнения (1.1) непусто.

Суммируя вышесказанное, заключаем: уравнение (1.1) имеет решение тогда и только тогда, когда делит b (см. упражнение 7 главы 2). Кроме того, приведенный метод решения линейных сравнений легко применим, поскольку использует только расширенный алгоритм Эвклида. Однако, когда решения будут получены, у нас могут возникнуть несколько поводов для удивления.

Решим сравнение . Поскольку то 6 не имеет обратного в Если данное сравнение имеет решение, то найдутся такие целые х и у, для которых Разделим это равенство на 2: что равносильно сравнению . Но 3 сам себе обратен в Умножая последнее сравнение на 3, мы приходим к

решению:

Это не совсем то, что нужно. Действительно, мы начинали со сравнения по модулю 8, и решение тоже хотели бы найти по модулю 8, а не по модулю 4, как в (1.3). Беда легко поправима. Как следует из (1.3), решение х сравнения записывается в виде для некоторого к Если к четно, то одно из решений. С другой стороны, если к нечетно, то Так что другое решение. Более того, поскольку к может быть либо четным, либо нечетным, существуют только эти возможности. Следовательно, уравнение имеет ровно два разных решения в а именно 2 и 6. Это пример линейного сравнения с двумя решениями. Как мы видели в § 6.4, такое произошло потому, что модуль сравнения был составным.