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

---

Китайская теорема об остатках — несколько связанных утверждений о решении линейной системы сравнений.

Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (кит. упр. 孙子算经, пиньинь sunzi suanjing), предположительно датируемом III веком н. э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах», датируемой 1247 годом, где было приведено точное решение^[1].

Если натуральные числа ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ попарно взаимно просты, то для любых целых ${\displaystyle r_{1},r_{2},\dots ,r_{n}}$ таких, что ${\displaystyle 0\leqslant r_{i}<a_{i}}$ при всех ${\displaystyle i\in \{1,2,\dots ,n\},}$ найдётся число ${\displaystyle N}$, которое при делении на ${\displaystyle a_{i}}$ даёт остаток ${\displaystyle r_{i}}$ при всех ${\displaystyle i\in \{1,2,\dots ,n\}}$. Более того, если найдутся два таких числа ${\displaystyle N_{1}}$ и ${\displaystyle N_{2}}$ (соответствующих утверждению выше), то ${\displaystyle N_{1}\equiv N_{2}{\pmod {a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}}$.

Воспользуемся методом математической индукции. При ${\displaystyle n=1}$ утверждение теоремы очевидно. Пусть теорема справедлива при ${\displaystyle n=k-1}$, тогда существует число ${\displaystyle m}$, дающее остаток ${\displaystyle r_{i}}$ при делении на ${\displaystyle a_{i}}$ при ${\displaystyle i\in \{1,2,\dots ,k-1\}}$. Обозначим

---