Разделы 
Дополнительно
Задача по математике - 930
2014-03-08 
Докажите, что система сравнений #\begin{cases} x \equiv a_{1} (\mod b_{1}),& \\ x \equiv a_{2} (\mod b_{2}) \end{cases}# имеет решения, если #\text{НОД}(b_{1},b_{2}) = 1# Верно ли обратное утверждение?
Решение:
Пусть в системе сравнений # \begin{cases} x \equiv a_{1} (\mod b_{1}),\\ x \equiv a_{2} (\mod b_{2}); \end{cases}# числа #b_{1}# и #b_{2}# взаимно просты; докажем, что система имеет решения. Действительно, # \begin{cases} x \equiv a_{1} (\mod b_{1}),\\ x \equiv a_{2} (\mod b_{2}); \end{cases} \iff \begin{cases} x = b_{1} \cdot n + a_{1},\\ x = b_{2} \cdot k + a_{2}. \end{cases}# Отсюда #b_{1} \cdot n + a_{1} = b_{2} \cdot k + a_{2},# или #b_{1} \cdot n - b_{2} \cdot k = a_{2} - a_{1}.# Так как #\text{НОД}(b_{1}, b_{2}) = 1.# диофантово уравнение #b_{1} \cdot n - b_{2} \cdot k = a_{2} - a_{1}# разрешимо в целых числах. Таким образом, существуют целые числа #n_{0}# И #k_{0},# что # \begin{cases} n = n_{0}c+ b_{2}t,\\ k = k_{0} + b_{1}t, \end{cases}# где #t \in \mathbf{Z}.# Тогда # \begin{cases} x = b_{1}n_{0}+ b_{1}b_{2}t + a_{1},\\ x =b_{2}k_{0} + b_{1}b_{2}t + a_{2}, \end{cases} \iff \begin{cases} x = b_{1}n_{0} + a_{1} (\mod b_{1}b_{2}),\\ x =b_{2}k_{0} + a_{2} (\mod b_{1}b_{2}). \end{cases}# Так как числа #n_{0}# и #k_{0}# решения уравнения #b_{1} \cdot n - b_{2} \cdot k = a_{2} - a_{1},# то #b_{1} \cdot n_{0} + a_{1} = b_{2} \cdot k_{0} + a_{2}.# Итак, система сравнений разрешима. Обратное утверждение неверно. Действительно, рассмотрим систему сравнений: # \begin{cases} x \equiv -1 (\mod 20),\\ x \equiv 5 (\mod 6). \end{cases}# Данная система, как легко видеть, имеет решение: #x \equiv 59 (\mod 60).# Однако числа 20 и 6 не взаимно просты.
Докажите, что система сравнений #\begin{cases} x \equiv a_{1} (\mod b_{1}),& \\ x \equiv a_{2} (\mod b_{2}) \end{cases}# имеет решения, если #\text{НОД}(b_{1},b_{2}) = 1# Верно ли обратное утверждение?
Решение:
Пусть в системе сравнений # \begin{cases} x \equiv a_{1} (\mod b_{1}),\\ x \equiv a_{2} (\mod b_{2}); \end{cases}# числа #b_{1}# и #b_{2}# взаимно просты; докажем, что система имеет решения. Действительно, # \begin{cases} x \equiv a_{1} (\mod b_{1}),\\ x \equiv a_{2} (\mod b_{2}); \end{cases} \iff \begin{cases} x = b_{1} \cdot n + a_{1},\\ x = b_{2} \cdot k + a_{2}. \end{cases}# Отсюда #b_{1} \cdot n + a_{1} = b_{2} \cdot k + a_{2},# или #b_{1} \cdot n - b_{2} \cdot k = a_{2} - a_{1}.# Так как #\text{НОД}(b_{1}, b_{2}) = 1.# диофантово уравнение #b_{1} \cdot n - b_{2} \cdot k = a_{2} - a_{1}# разрешимо в целых числах. Таким образом, существуют целые числа #n_{0}# И #k_{0},# что # \begin{cases} n = n_{0}c+ b_{2}t,\\ k = k_{0} + b_{1}t, \end{cases}# где #t \in \mathbf{Z}.# Тогда # \begin{cases} x = b_{1}n_{0}+ b_{1}b_{2}t + a_{1},\\ x =b_{2}k_{0} + b_{1}b_{2}t + a_{2}, \end{cases} \iff \begin{cases} x = b_{1}n_{0} + a_{1} (\mod b_{1}b_{2}),\\ x =b_{2}k_{0} + a_{2} (\mod b_{1}b_{2}). \end{cases}# Так как числа #n_{0}# и #k_{0}# решения уравнения #b_{1} \cdot n - b_{2} \cdot k = a_{2} - a_{1},# то #b_{1} \cdot n_{0} + a_{1} = b_{2} \cdot k_{0} + a_{2}.# Итак, система сравнений разрешима. Обратное утверждение неверно. Действительно, рассмотрим систему сравнений: # \begin{cases} x \equiv -1 (\mod 20),\\ x \equiv 5 (\mod 6). \end{cases}# Данная система, как легко видеть, имеет решение: #x \equiv 59 (\mod 60).# Однако числа 20 и 6 не взаимно просты.
