Системы сравнений. Китайская теорема об остатках

 

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

Рассмотрим систему сравнений:

                         ,                      (11.1)

где числа  – попарно взаимно просты.

Требуется найти число x, удовлетворяющее системе сравнений (11.1).

Для решения поставленной задачи докажем теорему:

    Теорема 11.1. Пусть числа  – попарно взаимно просты: , при , и пусть числа  причем  при . Тогда существует целое число x, удовлетворяющее системе сравнений (11.1).

    Сформулированная теорема носит название китайской теоремы об остатках, поскольку была доказана в Китае в 1-м (а по другим сведениям в 4-м веке) н. э.. Известны несколько доказательств этой теоремы. Мы рассмотрим конструктивное доказательство, т. е. доказательство существования решения путем построения решения.

Для доказательства теоремы докажем вспомогательное утверждение.

    Лемма. Пусть числа  – попарно взаимно просты. Тогда для каждого  найдется число , удовлетворяющее двум условиям:

 при    и .

Доказательство. Положим   и , . Искомое число  должно удовлетворять свойству: . Это значит, что должно выполняться равенство , где – некоторое целое число. Искомое число  также должно удовлетворять свойству: , . Это значит, что должно выполняться равенство , где  – некоторое целое число. 

    Таким образом, для существования искомого числа  должны существовать такие целые числа  и , что одновременно выполняются равенства:   и . А это, очевидно, значит, что должно существовать решение неопределенного уравнения . Поскольку , то, как было установлено в § 6, данное уравнение имеет решение.

    Доказательство теоремы. Возьмем в качестве x какое-либо число, удовлетворяющее условию , где , а – числа, способ нахождения которых дан в доказательстве леммы. Докажем, что определенное таким образом число x, является решением системы (11.1). Это означает, что требуется доказать справедливость утверждений:

 

                               .               (11.2)

Из определения x следует, что, , где z – некоторое целое число. Докажем, что . Имеем

 

. Каждое из трех слагаемых этой суммы делится на . Действительно, поскольку , имеем . Так как  для , то и . И, наконец, очевидно, что . Следовательно, . Аналогично можно доказать, что , для . Таким образом, получим, что x – решение системы.

Выпишем теперь последовательность действий, которые требуется совершить, чтобы найти решение системы сравнений.

    Алгоритм решения системы сравнений вида (11.1)

1. Вычислить .

2. Найти числа , .

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

4. Вычислить  для .

5. Составить сумму ; – частное решение системы (11.1).

6. Найти общее решение системы (11.1) по формуле: .

Примеры. 1) Решить систему сравнений

.

1. .

2. , .

3. Решим сравнения  и . В нашей задаче это сравнения  и . Получим частные решения этих сравнений: , .

4. Вычислим  и .

5. Составим сумму: .

6. Найдем общее решение системы: , где .

2) Решить систему сравнений

.

Прежде всего, приведем данную систему сравнений к виду (11.1). Для этого решим каждое из сравнений системы относительно неизвестной величины x, одним из способов, разобранных выше. Получим систему сравнений, равносильную исходной:

.

Будем решать полученную систему сравнений по указанному алгоритму.

1. .

2. , , .

3. Решим сравнения ,  В нашей задаче это сравнения ,  и . Получим частные решения этих сравнений: , , .

4. Вычислим  ,  и .

5. Составим сумму: .

6. Найдем общее решение системы: , где . Упростим решение, для этого заменим число 24367 на остаток от деления этого числа на 1872, получим , где .