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

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

${\displaystyle d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}}$.

Выберем произвольное число ${\displaystyle a_{k}}$, взаимно простое со всеми ${\displaystyle a_{1}\dots a_{k-1}}$ и рассмотрим числа ${\displaystyle M=\{m,m+d,m+2d,\dots ,m+(a_{k}-1)\cdot d\}=\{m+t\cdot d\}_{0\leqslant t<a_{k}}}$. Покажем, что все ${\displaystyle t\in \{0,\dots ,a_{k}-1\}}$ являются остатками при делении каких-либо элементов из ${\displaystyle M}$ на ${\displaystyle a_{k}}$.

Допустим это не так, то есть существует некоторое ${\displaystyle r_{k}<a_{k}}$, которое не принадлежит множеству всех остатков при делении элементов ${\displaystyle M}$ на ${\displaystyle a_{k}}$. Поскольку количество этих элементов равно ${\displaystyle |M|=a_{k}}$, а возможных остатков при делении элементов из ${\displaystyle M}$ на ${\displaystyle a_{k}}$ может быть не более чем ${\displaystyle a_{k}-1}$ (ведь ни одно число не даёт остаток ${\displaystyle r_{k}}$), то среди них найдутся два числа, имеющих равные остатки (принцип ящиков Дирихле). Пусть это числа ${\displaystyle m+t_{1}d}$ и ${\displaystyle m+t_{2}d}$ при ${\displaystyle t_{1}\neq t_{2}}$. Тогда их разность ${\displaystyle (m+t_{1}d)-(m+t_{2}d)=(t_{1}-t_{2})d}$ делится на ${\displaystyle a_{k}}$, что невозможно, так как ${\displaystyle t_{1}<a_{k}}$, ${\displaystyle t_{2}<a_{k}}$, ${\displaystyle 0<|t_{1}-t_{2}|<a_{k}}$ и ${\displaystyle d=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{k-1}}$ взаимно просто с ${\displaystyle a_{k}}$, так как числа ${\displaystyle a_{1},a_{2},\dots ,a_{k}}$ попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число ${\displaystyle N=m+t\cdot d}$, которое при делении на ${\displaystyle a_{k}}$ даёт остаток ${\displaystyle r_{k}}$. В то же время при делении на ${\displaystyle a_{1},a_{2},\dots ,a_{k-1}}$ число ${\displaystyle N}$ даёт остатки ${\displaystyle r_{1},r_{2},\dots ,r_{k-1}}$ соответственно, так как ${\displaystyle m+t\cdot d\equiv m{\pmod {a_{i}}}}$.

Докажем теперь, что ${\displaystyle N_{1}\equiv N_{2}{\pmod {a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}}$. В самом деле ${\displaystyle N_{1}\equiv N_{2}\equiv r_{i}{\pmod {a_{i}}}}$, то есть ${\displaystyle N_{1}-N_{2}\equiv 0{\pmod {a_{i}}}}$. Таким образом, число ${\displaystyle N_{1}-N_{2}}$ делится без остатка на все ${\displaystyle a_{i}}$, а также их произведение. ■

Описанное ниже доказательство теоремы помогает решить практически важную задачу — поиск решения системы линейных уравнений по модулю[2]. Рассмотрим систему уравнений:

Если наборы ${\displaystyle (r_{1},r_{2},\dots ,r_{n})}$ и ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$ удовлетворяют условию теоремы, то решение системы (1) существует и единственно с точностью до операции взятия по модулю ${\displaystyle M}$, где ${\displaystyle M={\displaystyle \prod _{i=1}^{n}a_{i}}}$, причем справедлива формула[2][3][4]:

Покажем, что определённый таким образом ${\displaystyle x}$ является решением — проверим, что для него выполняется i-е равенство в системе[3]: ${\displaystyle x\equiv \sum _{j=1}^{n}r_{j}M_{j}M_{j}^{-1}\equiv r_{i}M_{i}M_{i}^{-1}\equiv r_{i}{\pmod {a_{i}}}}$ Второе равенство справедливо так как ${\displaystyle M_{j}\equiv {\displaystyle \prod _{k\neq j}^{n}a_{k}}\equiv 0{\pmod {a_{i}}}}$ при всех ${\displaystyle i\neq j}$, третье так как ${\displaystyle M_{i}^{-1}}$ является обратным для ${\displaystyle M_{i}}$ по модулю ${\displaystyle a_{i}}$. Повторяя рассуждения для всех ${\displaystyle i}$, убедимся, что ${\displaystyle x}$, определённый формулой (2), является решением для (1).

В силу выбранного числа ${\displaystyle M}$ все числа ${\displaystyle x'\equiv x{\pmod {M}}}$ будут удовлетворять системе.

Покажем теперь, что среди чисел ${\displaystyle 0,1,\dots ,M-1}$ (множество ${\displaystyle A}$) не найдется другого решения, кроме найденного нами ранее. Проведём доказательство этого факта от противного. Предположим, что получилось найти хотя бы два решения ${\displaystyle x_{1},x_{2}\in A}$ для некоторого набора остатков ${\displaystyle r}$. Так как множество ${\displaystyle B}$ всех допустимых наборов ${\displaystyle (r_{1},r_{2},\dots ,r_{n})}$ является равномощным множеству ${\displaystyle A}$, то для ${\displaystyle {\overline {A}}_{x}:=A\setminus \{x_{1},x_{2}\}}$ и ${\displaystyle {\overline {B}}_{r}:=B\setminus \{r\}}$ выполнено ${\displaystyle |{\overline {A}}_{x}|<|{\overline {B}}_{r}|}$. Однако по доказанному ранее, для любого набора из ${\displaystyle {\overline {B}}_{r}}$ существует решение из ${\displaystyle {\overline {A}}_{x}}$, следовательно, по принципу Дирихле, найдутся как минимум 2 набора остатков, которым соответствует одно и то же ${\displaystyle x\in A}$. Для такого ${\displaystyle x}$ найдется ${\displaystyle a_{i}}$ такое, что ${\displaystyle x\equiv r_{1},x\equiv r_{2}{\pmod {a_{i}}}}$ и ${\displaystyle r_{1}\neq r_{2}}$. Противоречие[5]. ■

Из доказанного выше следует, что существует взаимно однозначное соответствие между вектором остатков из ${\displaystyle B}$ и числом из множества ${\displaystyle A}$ для любого набора ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$, т.е. отображение ${\displaystyle B}$ в ${\displaystyle A}$, заданное (2), является биективным[5]. Заметим, что кроме соответствия

${\displaystyle (x{\pmod {M}})\leftrightarrow (r_{1}{\pmod {a_{1}}},r_{2}{\pmod {a_{2}}},\dots ,r_{n}{\pmod {a_{n}}}),}$

верны также[6][7]

${\displaystyle (x_{1}\pm x_{2}{\pmod {M}})\leftrightarrow (r_{11}\pm r_{21}{\pmod {a_{1}}},r_{12}\pm r_{22}{\pmod {a_{2}}},\dots ,r_{1n}\pm r_{2n}{\pmod {a_{n}}})}$,

${\displaystyle (x_{1}x_{2}{\pmod {M}})\leftrightarrow (r_{11}r_{21}{\pmod {a_{1}}},r_{12}r_{22}{\pmod {a_{2}}},\dots ,r_{1n}r_{2n}{\pmod {a_{n}}})}$.

Вычислительная сложность перехода от вектора остатков к числу оценивается как ${\displaystyle O(k^{2})}$, где k — длина восстанавливаемого числа в битах[3].

Как пример рассмотрим систему:

Для решения системы выпишем отдельно решения первого, второго и третьего уравнений (достаточно выписать решения не превосходящие 2 × 3 × 7 = 42):

${\displaystyle x_{1}\in \{1,3,5,7,9,11,\dots ,39,\mathbf {41} ,43,\dots \},}$

${\displaystyle x_{2}\in \{2,5,8,11,14,\dots ,38,\mathbf {41} ,44,\dots \},}$

${\displaystyle x_{3}\in \{6,13,20,27,34,\mathbf {41} ,48,\dots \}.}$

Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю 42. В нашем случае ${\displaystyle x\in \{41,83,125,\dots \}}$ или ${\displaystyle x\equiv 41{\pmod {42}}.}$

Для того, чтобы продемонстрировать другой путь, переформулируем задачу. Найдем тройку чисел (u, v, w) таких, что:

Подставив x из первого уравнения во второе, получим ${\displaystyle 1+2u\equiv 2{\pmod {3}}}$, тогда ${\displaystyle 2u\equiv 1{\pmod {3}}}$, или ${\displaystyle 4u\equiv 2{\pmod {3}}}$, или ${\displaystyle u\equiv 2{\pmod {3}}}$, или ${\displaystyle u=2+3s}$;

подставив затем x из первого уравнения в третье с учетом выражения для ${\displaystyle u}$ получим ${\displaystyle 1+2(2+3s)\equiv 6{\pmod {7}}}$ или ${\displaystyle 6s\equiv 1{\pmod {7}}}$, тогда ${\displaystyle 36s\equiv 6{\pmod {7}}}$ и следовательно ${\displaystyle s\equiv 6{\pmod {7}}}$;

тогда ${\displaystyle x=1+2(2+3\cdot 6)=41}$.

Алгоритм сводится к поиску решений по формуле, данной в теореме[8].

Шаг 1. Вычисляем ${\displaystyle M={\displaystyle \prod _{i=1}^{n}a_{i}}}$.

Шаг 2. Для всех ${\displaystyle i\in \{1,2,\dots ,n\}}$ находим ${\displaystyle M_{i}={\frac {M}{a_{i}}}}$.

Шаг 3. Находим ${\displaystyle M_{i}^{-1}={\frac {1}{M_{i}}}{\bmod {a_{i}}}}$ (например, используя расширенный алгоритм Евклида).

Шаг 4. Вычисляем искомое значение по формуле ${\displaystyle x=\sum _{i=1}^{n}r_{i}M_{i}M_{i}^{-1}\mod M}$.

Рассмотрим набор модулей ${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$, удовлетворяющих условию теоремы. Другой теоремой из теории чисел утверждается, что любое число ${\displaystyle 0\leqslant x<M=a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}$ однозначно представимо в виде[9]

${\displaystyle x=x_{1}+x_{2}\cdot a_{1}+x_{3}\cdot a_{1}\cdot a_{2}+\dots +x_{n}\cdot a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n-1}}$.

Вычислив по порядку все коэффициенты ${\displaystyle x_{i}}$ для ${\displaystyle i\in \{1,2,\dots ,n\}}$ мы сможем подставить их в формулу и найти искомое решение[10]:

Обозначим через ${\displaystyle r_{ij}=a_{i}^{-1}{\bmod {a_{j}}}}$ и рассмотрим выражение для ${\displaystyle x}$ по модулю ${\displaystyle a_{i}}$, где ${\displaystyle i\in \{2,\dots ,n\}}$, получим:

${\displaystyle x_{1}=r_{1}}$;

${\displaystyle r_{2}=(x_{1}+x_{2}a_{1}){\bmod {a_{2}}}}$;

${\displaystyle x_{2}=(r_{2}-x_{1})r_{12}{\bmod {a_{2}}}}$;

${\displaystyle r_{3}=(x_{1}+x_{2}a_{1}+x_{3}a_{1}a_{2}){\bmod {a_{3}}}}$;

${\displaystyle x_{3}=((r_{3}-x_{1})r_{13}-x_{2})r_{23}{\bmod {a_{3}}}}$

и так далее.

Сложность вычисления коэффициентов ${\displaystyle x_{i}}$ для данного алгоритма ${\displaystyle O(n^{2})}$. Такая же сложность и восстановления искомого числа по найденным коэффициентам.

Пусть ${\displaystyle A,B_{1},\dots ,B_{n}}$ — коммутативные кольца с единицей, ${\displaystyle \varphi _{i}\colon A\to B_{i}}$ — сюръективные гомоморфизмы, обладающие свойством ${\displaystyle \ker \varphi _{i}+\ker \varphi _{j}=A}$ для всех ${\displaystyle i,j\in \{1,\dots ,n\},i\neq j}$. Тогда гомоморфизм

${\displaystyle \Phi \colon A\to \prod _{i=1}^{n}B_{i}}$,

заданный формулой

${\displaystyle \Phi (a)=(\varphi _{1}(a),\dots ,\varphi _{n}(a))}$,

является сюръективным. Более того, ${\displaystyle \Phi }$ определяет изоморфизм

${\displaystyle A/\left(\bigcap _{i=1}^{n}\ker \varphi _{i}\right)\cong \prod _{i=1}^{n}B_{i}}$.

Если положить ${\displaystyle A=\mathbb {Z} /(a_{1}\cdot \ldots \cdot a_{n}\mathbb {Z} ),B_{i}=\mathbb {Z} /a_{i}\mathbb {Z} \ (i=1,2,\dots ,n;\ a_{i}\in \mathbb {Z} )}$ и определить гомоморфизмы следующим образом

${\displaystyle \varphi _{i}(x)=x\,{\bmod {\,a_{i}}}}$,

то мы получим арифметическую версию теоремы.

Также часто встречается эквивалентная формулировка для колец, где ${\displaystyle B_{i}}$ имеют форму ${\displaystyle A/I_{i}}$ для некоторого набора идеалов ${\displaystyle I_{1},\dots ,I_{n}}$, гомоморфизмы ${\displaystyle \varphi _{i}}$ являются естественными проекциями на ${\displaystyle A/I_{i}}$ и требуется, чтобы ${\displaystyle I_{i}+I_{j}=A}$ для любых ${\displaystyle i,j\in \{1,\dots ,n\},i\neq j}$. Другими словами, если идеалы ${\displaystyle I_{1},\dots ,I_{n}}$ попарно взаимно просты (то есть сумма двух различных идеалов равна самому кольцу), то их произведение совпадает с их пересечением, и факторкольцо по этому произведению изоморфно произведению факторов:

${\displaystyle A/(I_{1}I_{2}\ldots I_{n})\cong A/I_{1}\times A/I_{2}\times \ldots \times A/I_{n}}$.

Кроме того существует обобщение на некоммутативные кольца без единиц с дополнительным условием, автоматически выполняющимся на кольцах с единицами.[11]

Также известно обобщение на решётки и коммутативные идемпотентные полукольца.[12]

Пусть ${\displaystyle R}$ — евклидово кольцо и ${\displaystyle m,n}$ — взаимно простые числа. Тогда докажем, что существует корректно заданный изоморфизм:

${\displaystyle R/_{(mn)}\cong R/_{(m)}\times R/_{(n)}}$

Прямое отображение ${\displaystyle [x]_{mn}\longrightarrow ([x]_{m},\ [x]_{n})}$ очевидно.

Для доказательства существования обратного отображения рассмотрим классы эквивалентности ${\displaystyle [1]}$ и ${\displaystyle [0]}$:

${\displaystyle ([1]_{m},\ [0]_{n})\longrightarrow [u]_{mn}}$,

${\displaystyle ([0]_{m},\ [1]_{n})\longrightarrow [v]_{mn}}$.

Найдём ${\displaystyle [u]_{mn}}$, решив следующую систему уравнений:

${\displaystyle {\begin{cases}u\equiv 1\ {\pmod {m}}\\u\equiv 0\ {\pmod {n}}\end{cases}}}$

${\displaystyle \exists y\in \mathbb {Z}$ :\ u=ny,\ ny\equiv 1{\pmod {m}}}

Аналогично найдём ${\displaystyle [v]_{mn}}$:

${\displaystyle \exists x\in \mathbb {Z}$ :\ v=mx,\ mx\equiv 1{\pmod {n}}}

Покажем, что в общем виде выполняется:

${\displaystyle ([a]_{m},\ [b]_{n})\longrightarrow [au+bv]_{mn},}$

${\displaystyle au+bv\equiv a{\pmod {m}}}$, так как ${\displaystyle v\equiv 0{\pmod {m}}}$ и ${\displaystyle u\equiv 1{\pmod {m}},}$

${\displaystyle au+bv\equiv b{\pmod {n}}}$, так как ${\displaystyle u\equiv 0{\pmod {n}}}$ и ${\displaystyle v\equiv 1{\pmod {n}}.}$

Проверим корректность отображения, то есть что при взятии разных элементов из классов ${\displaystyle [a]_{m},\ [b]_{n}}$ результат не меняется:

${\displaystyle {\begin{cases}a\equiv a'{\pmod {m}},\\b\equiv b'{\pmod {n}}.\end{cases}}}$

Значит ${\displaystyle au+bv\equiv a'u+b'v{\pmod {mn}},}$ отображение корректно.

Можно проверить, что построенное отображение действительно обратное .