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

Материал из Википедии — свободной энциклопедии

Текущая версия (не проверялась)

Несколько связанных утверждений известны под именем китайской теоремы об остатках. Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (кит. 孙子算经, пиньинь sūnzǐ suànjīng), предположительно датируемом третим веком н.э..

Если натуральные числа $a_1, a_2, \dots , a_n$ попарно взаимно просты, то для любых целых $r_1, r_2, \dots, r_n$ таких, что $0 \leq r_i < a_i$ при всех $i = 1, 2, \dots, n$ , найдётся число $N$ , которое при делении на $a i$ даёт остаток $r i$ при всех $i = 1, 2, \dots, n$ .

Доказательство

Применим индукцию по $n$ . При $n = 1$ утверждение теоремы очевидно. Пусть теорема справедлива при $n = k - 1$ , т. е. существует число $M$ , дающее остаток $r i$ при делении на $a i$ при $i = 1, 2, \dots, k - 1$ . Обозначим

$d = a_1 a_2\cdots a_{k-1}$

и рассмотрим числа $M, M + d, M + 2d,\dots , M + (a_{k} - 1)d$ . Покажем, что хотя бы одно из этих чисел даёт остаток $r k$ при делении на $a k$ . Допустим это не так. Поскольку количество чисел равно $a k$ , а возможных остатков при делении этих чисел на $a k$ может быть не более чем $a k - 1$ (ведь ни одно число не даёт остаток $r k$ ), то среди них найдутся два числа, имеющих равные остатки (принцип Дирихле). Пусть это числа $M + s d$ и $M + t d$ при $0 \leq s\leq a_k- 1$ и $0 \leq t \leq a_k - 1$ . Тогда их разность $(M + s d) - (M + t d) = (s - t) d$ делится на $a k$ , что невозможно, т. к. $0 < | s - t | < a k$ и $d = a_1 a_2 \cdots a_{k-1}$ взаимно просто с $a k$ , ибо числа $a_1, a_2,\dots, a_k$ попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число $N$ , которое при делении на $a k$ даёт остаток $r k$ . В то же время при делении на $a_1, a_2, \dots, a_{k-1}$ число $N$ даёт остатки $r_1, r_2, \dots, r_{k-1}$ соответственно. Теорема доказана.

[править] Вариации и обобщения

[править] Формулировка для колец

Пусть $A, (B_i)_{i \in I}$ — коммутативные кольца с единицей, $\phi_i: A \to B_i$ сюръективные гомоморфизмы, обладающие свойством $Ker\,\phi_i + Ker\,\phi_j=A$ для всех $i,j \in I$ . Тогда гомоморфизм $\Phi: A \to \prod_{i \in I} B_i$ , заданный формулой

$\Phi(a) = (\phi_i(a))_{i \in I}$

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

$A / (\cap_{i \in I} Ker\,\phi_i )\simeq \prod_{i \in I} B_i$ .

Если положить $A=\mathbb{Z}/(a_1\cdot \ldots \cdot a_n)\mathbb{Z}$ , $B_i = \mathbb{Z}/a_i\mathbb{Z}$ и определить гомоморфизмы следующим образом

$\phi_i(x) = x \mod a_i$

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

Также часто встречается следующая эквивалентная формулировка для колец, где $B i$ имеют форму $A / I i$ , $φ i$ являются естественными проекциями на $A / I i$ и требуется, чтобы $I i + I j = A$ для любых $i, j \in I$ .

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

Материал из Википедии — свободной энциклопедии

[править] Вариации и обобщения

[править] Формулировка для колец

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

На других языках