Китайская теорема об остатках

Китайская теорема об остатках (КТО) является очень древней находкой математики, которой около 2000 лет.

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

Так как , то . С другой стороны, . Поэтому или . Поскольку НОД =НОД , можем решить последнее уравнение относительно . Имеем , следовательно, . Поэтому . Тогда .

Приведем общую схему решения системы двух уравнений, так как такая система имеет важное значение. Предположим, что числа и взаимно просты и дана система уравнений Сначала определим . Это сделать можно в силу предположения о взаимной простоте чисел и . Затем вычисляем . Решение по модулю задается формулой . Чтобы убедиться в верности метода, сделаем проверку , .

В общем случае КТО посвящена системе из более чем двух уравнений. Пусть и - числа, причем все взаимно просты. Нужно найти такой элемент , , что для всех . КТО гарантирует существование и единственность решения и дает ответ: , где , .

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

Решение. Числа 7, 11, 13 взаимно простые, поэтому . Согласно выше изложенному методу , , , , , . Пользуясь формулой, получаем решение: .