Разделы 
Дополнительно
Задача по математике - 931
2015-02-14 
(Китайская теорема об остатках)Докажите, что система сравнений: #\begin{cases} x \equiv a_{1} (mod b_{1}), x \equiv a_{2} (mod b_{2}), \cdots x \equiv a_{n} (mod b_{n}), \end{cases}#
имеет решение, если числа #b_{i} (i = 1, 2, \cdots, n)# попарно взаимно просты.
Решение:
Индукция по #n.#
При #n = 2# утверждение теоремы доказано в предыдущей задаче. Допустим, что #n > 2,# для #n -1# утверждение верно и
#x \equiv r (\mod b_{1} \cdot b_{2} \cdot \cdots \cdot b_{n-1})#
Если #b_{n}# взаимно просто с каждым из чисел #b_{1}, b_{2}, \cdots, b_{n-1},# то #b_{n}# взаимно просто с произведением #b_{1} \cdot b_{2} \cdot \cdots \cdot b_{n-1},#
Поэтому система сравнений # \begin{cases} x \equiv r (\mod b_{1} \cdot b_{2} \cdot \cdots \cdot b_{n-1}),\\ x \equiv a_{n} (\mod b_{n}) \end{cases}# разрешима в целых числах. Теорема доказана.
(Китайская теорема об остатках)Докажите, что система сравнений: #\begin{cases} x \equiv a_{1} (mod b_{1}), x \equiv a_{2} (mod b_{2}), \cdots x \equiv a_{n} (mod b_{n}), \end{cases}#
имеет решение, если числа #b_{i} (i = 1, 2, \cdots, n)# попарно взаимно просты.
Решение:
Индукция по #n.#
При #n = 2# утверждение теоремы доказано в предыдущей задаче. Допустим, что #n > 2,# для #n -1# утверждение верно и
#x \equiv r (\mod b_{1} \cdot b_{2} \cdot \cdots \cdot b_{n-1})#
Если #b_{n}# взаимно просто с каждым из чисел #b_{1}, b_{2}, \cdots, b_{n-1},# то #b_{n}# взаимно просто с произведением #b_{1} \cdot b_{2} \cdot \cdots \cdot b_{n-1},#
Поэтому система сравнений # \begin{cases} x \equiv r (\mod b_{1} \cdot b_{2} \cdot \cdots \cdot b_{n-1}),\\ x \equiv a_{n} (\mod b_{n}) \end{cases}# разрешима в целых числах. Теорема доказана.
