Номер 11, страница 418 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

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

Рекомендуемая литература:

1) Бухштаб А. А. Теория чисел : учебное пособие. — 4-е изд., стер. — СПб. [и др.] : Лань, 2015. (Классическая учебная литература по математике).

2) Коутинхо С. Введение в теорию чисел. Алгоритм RSA. — М. : Постмаркет, 2001.

3) Нестеренко Ю. В. Теория чисел. — М. : Издательский центр «Академия», 2008.

Китайская теорема об остатках (КТО) — это результат теории чисел, который дает условия, при которых система линейных сравнений имеет единственное решение. Она имеет важное применение в криптографии, теории кодирования и других областях математики и информатики.

Формулировка теоремы

Пусть даны попарно взаимно простые натуральные числа $n_1, n_2, \dots, n_k$, то есть $\text{НОД}(n_i, n_j) = 1$ для всех $i \ne j$. Тогда для любых целых чисел $a_1, a_2, \dots, a_k$ система сравнений:

$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$

имеет решение, и это решение единственно по модулю $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.

Ответ: Теорема утверждает, что если модули $n_i$ попарно взаимно просты, то система линейных сравнений всегда имеет решение, которое уникально с точностью до прибавления кратных числа $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.

Доказательство и конструктивный метод решения

Доказательство теоремы является конструктивным, то есть оно не только доказывает существование решения, но и предоставляет метод его нахождения.

1. Обозначим $N = n_1 \cdot n_2 \cdot \dots \cdot n_k$.

2. Для каждого $i = 1, 2, \dots, k$ введем число $N_i = \frac{N}{n_i} = n_1 \cdot \dots \cdot n_{i-1} \cdot n_{i+1} \cdot \dots \cdot n_k$.

3. Поскольку все $n_j$ попарно взаимно просты, то для любого $i$ числа $N_i$ и $n_i$ также взаимно просты, то есть $\text{НОД}(N_i, n_i) = 1$.

4. Из того, что $\text{НОД}(N_i, n_i) = 1$, следует, что для каждого $N_i$ существует обратный элемент по модулю $n_i$. Найдем такое целое число $y_i$, что $N_i y_i \equiv 1 \pmod{n_i}$. Это число $y_i$ можно найти с помощью расширенного алгоритма Евклида.

5. Теперь мы можем построить решение системы. Искомое число $x$ находится по формуле:
$x = a_1 N_1 y_1 + a_2 N_2 y_2 + \dots + a_k N_k y_k = \sum_{i=1}^k a_i N_i y_i$.

Проверим, что это действительно решение. Рассмотрим $x$ по модулю $n_j$ для произвольного $j \in \{1, \dots, k\}$:
$x \pmod{n_j} = \left(\sum_{i=1}^k a_i N_i y_i\right) \pmod{n_j}$.
Заметим, что для любого $i \ne j$, число $N_i$ содержит в своем произведении множитель $n_j$, поэтому $N_i \equiv 0 \pmod{n_j}$. Таким образом, все слагаемые в сумме, кроме одного, обращаются в ноль по модулю $n_j$:
$x \equiv a_j N_j y_j \pmod{n_j}$.
Но мы выбрали $y_j$ так, что $N_j y_j \equiv 1 \pmod{n_j}$. Следовательно:
$x \equiv a_j \cdot 1 \pmod{n_j}$, что и требовалось доказать.

Для доказательства единственности предположим, что есть два решения, $x$ и $x'$. Тогда $x \equiv a_i \pmod{n_i}$ и $x' \equiv a_i \pmod{n_i}$ для всех $i$. Это означает, что их разность $x - x'$ делится на каждое $n_i$. Поскольку все $n_i$ попарно взаимно просты, их произведение $N$ также делит $x - x'$. Таким образом, $x - x' \equiv 0 \pmod N$, или $x \equiv x' \pmod N$.

Ответ: Решение системы находится по формуле $x = \sum_{i=1}^k a_i N_i y_i \pmod N$, где $N = \prod n_i$, $N_i = N/n_i$, и $y_i$ является мультипликативным обратным для $N_i$ по модулю $n_i$.

Пример

Решим систему сравнений:
$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$

1. Модули $n_1=3, n_2=5, n_3=7$ попарно взаимно просты.
$N = 3 \cdot 5 \cdot 7 = 105$.

2. Находим $N_i$:
$N_1 = N/n_1 = 105/3 = 35$.
$N_2 = N/n_2 = 105/5 = 21$.
$N_3 = N/n_3 = 105/7 = 15$.

3. Находим обратные элементы $y_i$:
$N_1 y_1 \equiv 1 \pmod{n_1} \implies 35 y_1 \equiv 1 \pmod{3} \implies 2 y_1 \equiv 1 \pmod{3}$. Умножая на 2, получаем $4y_1 \equiv 2 \pmod{3} \implies y_1 \equiv 2 \pmod{3}$. Итак, $y_1=2$.
$N_2 y_2 \equiv 1 \pmod{n_2} \implies 21 y_2 \equiv 1 \pmod{5} \implies 1 y_2 \equiv 1 \pmod{5}$. Итак, $y_2=1$.
$N_3 y_3 \equiv 1 \pmod{n_3} \implies 15 y_3 \equiv 1 \pmod{7} \implies 1 y_3 \equiv 1 \pmod{7}$. Итак, $y_3=1$.

4. Вычисляем решение $x$:
$x_0 = a_1 N_1 y_1 + a_2 N_2 y_2 + a_3 N_3 y_3$
$x_0 = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233$.

5. Находим наименьшее неотрицательное решение:
$x = 233 \pmod{105} = 23$.

Проверка:
$23 = 7 \cdot 3 + 2 \implies 23 \equiv 2 \pmod{3}$.
$23 = 4 \cdot 5 + 3 \implies 23 \equiv 3 \pmod{5}$.
$23 = 3 \cdot 7 + 2 \implies 23 \equiv 2 \pmod{7}$.

Ответ: $x \equiv 23 \pmod{105}$.