Если ты знаешь как себя так и врага, ты можешь победить в многочисленных битвах без опасности поражения.
-Сунь Цзы, но не тот, о котором речь пойдет
Такая проблема, что у китайцев несколько известных чуваков звали Сунь Цзы. И так уж сложилось, что один из них был математиком, которому приписывается авторство китайской теоремы об остатках.
Постановка тривиальной задачи: найти хоть одно число, которое даёт остаток 1 при делении на 5. Практически без труда можно дать отве: подойдет 6, ну или 1, ну или 11. Решение такой задачи тривиально. Рассмотрим более сложный вариант: найти хоть одно число, которое дает остаток 1 при делении на 5 и остаток 2 при делении на 7.
Ну такую задачу можно решить нехитрым перебором, просто взяв все ответы первой задачи и найдя среди них нужные. Минимальное подходящее число - 16.
Еще одна задача: найти все числа, которые дают остаток 3 при делении на 24 и остаток 2 при делении на 27. Такую задачу можно решать перебором, правда ничего не выйдет: такого числа нет. Так как же тут быть? Ну, можно придумать такой костыль: 24 делится на 3, так что если число дает остаток 3 при делении на 24, то оно делится на 3. В то же время, 27 также делится на 3, а дающее остаток 2 при делении на него не может на 3 делиться. Значит, такого числа нет.
А что, если бы условий было не 2, а 5? Перебором такую задачу не решишь, а вопрос неразрешимости вообще доказывается непойми как - в третьем примере нам просто повезло, что число должно давать остаток 3 при делении на 24, а если было бы 4? Тогда наше рассуждение бы провалилось.
Вот наиболее общая постановка задачи: найти число x, хотя бы одно, которое удовлетворяло бы системе линейных сравнений:
x = b1 (mod m1)
x = b2 (mod m2)
. . .
x = bk (mod mk)
Решением данной задачи в наиболее общем случае является Китайская Теорема об Остатках, которая является критерием разрешимости данной системы сравнений: Если числа m1, ..., mk попарно взаимно просты, то система разрешима. Доказательство теоремы является также и конструктивным методом решения таких систем:
/* только для любопытных
Перемножим все m1, m2, ..., mk и получим M, затем разделим M на m1, m2, ..., mk и получим M1, M2, ..., Mk.
Тогда M1, M2, ..., Mk будут взаимно просты с m1, ... mk соответственно. Мы умеем решать линейные уравнения вида:
Mi * yi = bi (mod mi), например, при помощи алгортима Евклида.
Тогда x = M1*y1 + M2*y2 + ... + Mk*yk, можно убедиться подстановкой в систему.
*/
Данная теорема является очень удобным и очень широкоиспользуемым методом в теории чисел, на ней основаны некоторые алгоритмы из криптографии потому что ее доказательство позволяет в явном виде искать числа необходимого вида. Есть и более общая формулировка теоремы, связанная с кольцами произвольной породы и отображениями между ними, ну и отдельная теорема для Евклидовых колец (это такие кольца, в которых есть аналог алгоритма Евклида).
Часть 3. Мультипликативные функции
Часть 2. Алгоритм Евклида
Часть 1. Введение
Дополнительно. Кольца
Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite
![Теория чисел - 4. Китайская теорема об остатках](https://retell.in//upload/articles/430-teoriya-chisel---4-kitayskaya-teorema-ob-ostatkah_1.jpg)