Китайська теорема про залишки

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Китайська теорема про залишки — один з основних результатів елементарної теорії чисел. Використовуючи позначення модульної арифметики її можна сформулювати наступним чином. Нехай довільні цілі числа, а попарно взаємно прості числа. Тоді наступна система:

має розв'язок і всі її розв'язки рівні за модулем

Історія[ред.ред. код]

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

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

Позначимо і . Звідки випливає взаємна простота і . Тож за допомогою розширеного алгоритму Евкліда можна знайти такі , що

Позначимо . Тоді в той час, як якщо . Визначивши за допомогою суми

одержуємо необхідний розв'язок. Очевидно всі числа рівні йому за модулем теж є розв'язками. Якщо взяти тепер два довільні розв'язки , то, згідно з умовами теореми, їхня різниця повинна ділитися на кожне з чисел а значить, враховуючи попарну взаємну простоту чисел , і на їхній добуток. Тобто:

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

Алгебраїчна версія[ред.ред. код]

Нехай  — комутативні кільця з одиницею, сюр'єктивні гомоморфізми, такі що для всіх . Тоді гомоморфізм , заданий формулою

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

.

Якщо взяти , і визначити гомоморфізми наступним чином

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

Див. також[ред.ред. код]

Література[ред.ред. код]

Джерела[ред.ред. код]