Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Несколько связанных утверждений известны под именем китайской теоремы об остатках. Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (Шаблон:Lang-zh-ип), предположительно датируемом третим веком н.э..

Арифметическая формулировка Править

Если числа 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 + sd и M + td при 0 \leq s\leq a_k- 1 и 0 \leq t \leq a_k - 1. Тогда их разность (M + sd) - (M + td) = (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}

является сюрьективным. Более того, \Phi опеределяет изоморфизм

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, \phi_i являются естественными проекциями на A/I_i и требуется, чтобы I_i + I_j = A для любых i, j \in I.cs:Čínská věta o zbytcíchhe:משפט השאריות הסיני hu:Kínai maradéktétel id:Teorema sisa Tiongkoknl:Chinese reststelling pl:Chińskie twierdzenie o resztachsv:Kinesiska restsatsen ur:چینی تقسیم باقی مسلئہ اثباتی vi:Định lý số dư Trung Quốczh-classical:韓信點兵

Викия-сеть

Случайная вики