Кита́йська теоре́ма про оста́чі — один з основних результатів елементарної теорії чисел. Використовуючи позначення модульної арифметики її можна сформулювати таким чином. Нехай довільні цілі числа, а попарно взаємно прості числа. Тоді така система:
має розв'язок і всі її розв'язки рівні за модулем .
Історія
Близько 100 р. до н. е. китайський математик Сун Цу (Sun-Tsŭ) розв'язав таку задачу: знайти число, яке дає при діленні на 3, 5 та 7 остачі 2, 3 та 2 відповідно (загальний розв'язок має вигляд 23+105k для цілих k). Тому твердження про еквівалентність системи порівнянь за взаємно простими модулями, і порівняння за модулем добутку називають «китайською теоремою про остачі».
Конструктивне доведення
Позначимо і . Звідки випливає взаємна простота і . Тож за допомогою розширеного алгоритму Евкліда можна знайти такі , що
Позначимо . Тоді в той час, як якщо . Визначивши за допомогою суми
одержуємо необхідний розв'язок. Очевидно всі числа рівні йому за модулем теж є розв'язками. Якщо взяти тепер два довільні розв'язки , то, згідно з умовами теореми, їхня різниця повинна ділитися на кожне з чисел а значить, враховуючи попарну взаємну простоту чисел , і на їхній добуток. Тобто:
- що завершує доведення теореми.
Алгебраїчна версія
Нехай — комутативні кільця з одиницею, сюр'єктивні гомоморфізми, такі що для всіх . Тоді гомоморфізм , заданий формулою
є сюр'єктивним. Окрім того, визначає ізоморфізм
- .
Якщо взяти , і визначити гомоморфізми наступним чином
то ми одержуємо арифметичну версію теореми.
Див. також
Література
- Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — Москва : Мир, 1987. — 416 с.(рос.)
- Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. — МЦНМО: БИНОМ. — С. 960. — .
Джерела
Українською
- (укр.) Елементи теорії груп та теорії кілець. — І.-Ф. : Голіней, 2023. — 153 с.
- Реалізація алгоритму на мові C# [ 11 Червня 2010 у Wayback Machine.]
- Втілення алгоритму на мові C++ [ 27 Серпня 2016 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет