Решение задачи 6.2: Китайская теорема об остатках

Задача 6.2 (Китайская теорема об остатках) Дана система сравнений: \[ \begin{cases} x \equiv 5 \pmod{7} \\ x \equiv 3 \pmod{11} \\ x \equiv 10 \pmod{13} \end{cases} \] Решение: 1. Вычислим общее произведение модулей: \[ M = 7 \cdot 11 \cdot 13 = 1001 \] 2. Вычислим частные модули \( M_i = \frac{M}{m_i} \): \[ M_1 = \frac{1001}{7} = 143 \] \[ M_2 = \frac{1001}{11} = 91 \] \[ M_3 = \frac{1001}{13} = 77 \] 3. Найдем обратные элементы \( y_i \) такие, что \( M_i y_i \equiv 1 \pmod{m_i} \): Для \( M_1 \): \[ 143 y_1 \equiv 1 \pmod{7} \] Так как \( 143 = 20 \cdot 7 + 3 \), то \( 3 y_1 \equiv 1 \pmod{7} \). Методом подбора: \( 3 \cdot 5 = 15 \equiv 1 \pmod{7} \). Значит, \( y_1 = 5 \). Для \( M_2 \): \[ 91 y_2 \equiv 1 \pmod{11} \] Так как \( 91 = 8 \cdot 11 + 3 \), то \( 3 y_2 \equiv 1 \pmod{11} \). Методом подбора: \( 3 \cdot 4 = 12 \equiv 1 \pmod{11} \). Значит, \( y_2 = 4 \). Для \( M_3 \): \[ 77 y_3 \equiv 1 \pmod{13} \] Так как \( 77 = 5 \cdot 13 + 12 \), то \( 12 y_3 \equiv 1 \pmod{13} \), что эквивалентно \( -1 y_3 \equiv 1 \pmod{13} \). Значит, \( y_3 = -1 \equiv 12 \pmod{13} \). Возьмем \( y_3 = 12 \). 4. Вычислим решение по формуле \( x = \sum a_i M_i y_i \pmod{M} \): \[ x = (5 \cdot 143 \cdot 5 + 3 \cdot 91 \cdot 4 + 10 \cdot 77 \cdot 12) \pmod{1001} \] \[ x = (3575 + 1092 + 9240) \pmod{1001} \] \[ x = 13907 \pmod{1001} \] 5. Найдем остаток от деления 13907 на 1001: \[ 13907 = 13 \cdot 1001 + 894 \] \[ x = 894 \] Проверка: \( 894 = 127 \cdot 7 + 5 \) (верно) \( 894 = 81 \cdot 11 + 3 \) (верно) \( 894 = 68 \cdot 13 + 10 \) (верно) Ответ: \( x \equiv 894 \pmod{1001} \).