Китайська теорема про остачі

Кита́йська теоре́ма про оста́чі — один з основних результатів елементарної теорії чисел. Використовуючи позначення модульної арифметики її можна сформулювати таким чином. Нехай $y_{1}, y_{2}, \dots, y_{k}$ довільні цілі числа, а $n_{1}, n_{2}, \dots, n_{k}$ попарно взаємно прості числа. Тоді така система:

x \equiv y_{1} (mod n_{1}),

x \equiv y_{2} (mod n_{2}),

⋮

x \equiv y_{k} (mod n_{k})

має розв'язок і всі її розв'язки рівні за модулем $M = n_{1} n_{2} \dots n_{k}$ .

Історія

Близько 100 р. до н. е. китайський математик Сун Цу (Sun-Tsŭ) розв'язав таку задачу: знайти число, яке дає при діленні на 3, 5 та 7 остачі 2, 3 та 2 відповідно (загальний розв'язок має вигляд 23+105k для цілих k). Тому твердження про еквівалентність системи порівнянь за взаємно простими модулями, і порівняння за модулем добутку називають «китайською теоремою про остачі».

Конструктивне доведення

Позначимо $M = n_{1} n_{2} \dots n_{k}$ і $M_{i} = \frac{M}{n_{i}}$ . Звідки випливає взаємна простота $n_{i}$ і $M_{i}$ . Тож за допомогою розширеного алгоритму Евкліда можна знайти такі $f_{i}, g_{i} \in ℤ$ , що

f_{i} n_{i} + g_{i} M_{i} = 1 .

Позначимо $e_{i} = g_{i} M_{i}$ . Тоді $e_{i} \equiv 1 (mod n_{i})$ в той час, як $e_{i} \equiv 0 (mod n_{j})$ якщо $j \neq i$ . Визначивши $x$ за допомогою суми

x = \sum_{i = 1}^{k} y_{i} e_{i}

одержуємо необхідний розв'язок. Очевидно всі числа рівні йому за модулем $M$ теж є розв'язками. Якщо взяти тепер два довільні розв'язки $x^{1}, x^{2}$ , то, згідно з умовами теореми, їхня різниця повинна ділитися на кожне з чисел $n_{i},$ а значить, враховуючи попарну взаємну простоту чисел $n_{1}, n_{2}, \dots, n_{k}$ , і на їхній добуток. Тобто:

x^{1} - x^{2} \equiv 0 (mod M),

що завершує доведення теореми.

Алгебраїчна версія

Нехай $A, (B_{i})_{i \in I}$ — комутативні кільця з одиницею, $ϕ_{i} : A \to B_{i}$ сюр'єктивні гомоморфізми, такі що $Ker ϕ_{i} + Ker ϕ_{j} = A$ для всіх $i, j \in I$ . Тоді гомоморфізм $Φ : A \to \prod_{i \in I} B_{i}$ , заданий формулою

Φ (a) = (ϕ_{i} (a))_{i \in I}

є сюр'єктивним. Окрім того, $Φ$ визначає ізоморфізм

A / (\cap_{i \in I} Ker ϕ_{i}) ≃ \prod_{i \in I} B_{i}

.

Якщо взяти $A = ℤ / (a_{1} \cdot \dots \cdot a_{n}) ℤ$ , $B_{i} = ℤ / a_{i} ℤ$ і визначити гомоморфізми наступним чином

ϕ_{i} (x) = x mod a_{i},

то ми одержуємо арифметичну версію теореми.

Див. також

Шаблон:Портал

Література

Джерела

Українською

Китайська теорема про остачі

Зміст

Історія

Конструктивне доведення

Алгебраїчна версія

Див. також

Література

Джерела

Українською

Навігаційне меню

Китайська теорема про остачі

Історія

Конструктивне доведення

Алгебраїчна версія

Див. також

Література

Джерела

Українською

Навігаційне меню

Пошук