www.wikidata.uk-ua.nina.az

Китайська теорема про остачі Кита йська теоре ма про оста чі один з основних результатів елементарної теорії чисел Викор

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

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

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

Історія Редагувати

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

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

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

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

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

Алгебраїчна версія Редагувати

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

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

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

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

Див. також Редагувати

Література Редагувати

Джерела Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Kita jska teore ma pro osta chi odin z osnovnih rezultativ elementarnoyi teoriyi chisel Vikoristovuyuchi poznachennya modulnoyi arifmetiki yiyi mozhna sformulyuvati takim chinom Nehaj y 1 y 2 y k displaystyle y 1 y 2 dots y k dovilni cili chisla a n 1 n 2 n k displaystyle n 1 n 2 dots n k poparno vzayemno prosti chisla Todi taka sistema x y 1 mod n 1 displaystyle x equiv y 1 bmod n 1 x y 2 mod n 2 displaystyle x equiv y 2 bmod n 2 displaystyle vdots x y k mod n k displaystyle x equiv y k bmod n k maye rozv yazok i vsi yiyi rozv yazki rivni za modulem M n 1 n 2 n k displaystyle M n 1 n 2 dots n k Zmist 1 Istoriya 2 Konstruktivne dovedennya 3 Algebrayichna versiya 4 Div takozh 5 Literatura 6 DzherelaIstoriya RedaguvatiBlizko 100 r do n e kitajskij matematik Sun Cu Sun Tsŭ rozv yazav taku zadachu znajti chislo yake daye pri dilenni na 3 5 ta 7 ostachi 2 3 ta 2 vidpovidno zagalnij rozv yazok maye viglyad 23 105k dlya cilih k Tomu tverdzhennya pro ekvivalentnist sistemi porivnyan za vzayemno prostimi modulyami i porivnyannya za modulem dobutku nazivayut kitajskoyu teoremoyu pro ostachi Konstruktivne dovedennya RedaguvatiPoznachimo M n 1 n 2 n k displaystyle M n 1 n 2 dots n k nbsp i M i M n i displaystyle M i frac M n i nbsp Zvidki viplivaye vzayemna prostota n i displaystyle n i nbsp i M i displaystyle M i nbsp Tozh za dopomogoyu rozshirenogo algoritmu Evklida mozhna znajti taki f i g i Z displaystyle f i g i in mathbb Z nbsp sho f i n i g i M i 1 displaystyle f i n i g i M i 1 nbsp Poznachimo e i g i M i displaystyle e i g i M i nbsp Todi e i 1 mod n i displaystyle e i equiv 1 bmod n i nbsp v toj chas yak e i 0 mod n j displaystyle e i equiv 0 bmod n j nbsp yaksho j i displaystyle j neq i nbsp Viznachivshi x displaystyle x nbsp za dopomogoyu sumi x i 1 k y i e i displaystyle x sum i 1 k y i e i nbsp oderzhuyemo neobhidnij rozv yazok Ochevidno vsi chisla rivni jomu za modulem M displaystyle M nbsp tezh ye rozv yazkami Yaksho vzyati teper dva dovilni rozv yazki x 1 x 2 displaystyle x 1 x 2 nbsp to zgidno z umovami teoremi yihnya riznicya povinna dilitisya na kozhne z chisel n i displaystyle n i nbsp a znachit vrahovuyuchi poparnu vzayemnu prostotu chisel n 1 n 2 n k displaystyle n 1 n 2 dots n k nbsp i na yihnij dobutok Tobto x 1 x 2 0 mod M displaystyle x 1 x 2 equiv 0 bmod M nbsp sho zavershuye dovedennya teoremi Algebrayichna versiya RedaguvatiNehaj A B i i I displaystyle A B i i in I nbsp komutativni kilcya z odiniceyu ϕ i A B i displaystyle phi i A to B i nbsp syur yektivni gomomorfizmi taki sho Ker ϕ i Ker ϕ j A displaystyle operatorname Ker phi i operatorname Ker phi j A nbsp dlya vsih i j I displaystyle i j in I nbsp Todi gomomorfizm F A i I B i displaystyle Phi A to prod i in I B i nbsp zadanij formuloyu F a ϕ i a i I displaystyle Phi a phi i a i in I nbsp ye syur yektivnim Okrim togo F displaystyle Phi nbsp viznachaye izomorfizm A i I Ker ϕ i i I B i displaystyle A cap i in I operatorname Ker phi i simeq prod i in I B i nbsp Yaksho vzyati A Z a 1 a n Z displaystyle A mathbb Z a 1 cdot ldots cdot a n mathbb Z nbsp B i Z a i Z displaystyle B i mathbb Z a i mathbb Z nbsp i viznachiti gomomorfizmi nastupnim chinom ϕ i x x mod a i displaystyle phi i x x mod a i nbsp to mi oderzhuyemo arifmetichnu versiyu teoremi Div takozh Redaguvati nbsp Portal Matematika Diofantovi rivnyannya Algoritm EvklidaLiteratura RedaguvatiAjerlend K Rouzen M Klassicheskoe vvedenie v sovremennuyu teoriyu chisel Moskva Mir 1987 416 s ros T Kormen Ch Lejzerson R Rivest Algoritmy postroenie i analiz MCNMO BINOM S 960 ISBN 5 900916 37 5 Dzherela RedaguvatiRealizaciya algoritmu na movi C Arhivovano 11 Chervnya 2010 u Wayback Machine Vtilennya algoritmu na movi C Arhivovano 27 Serpnya 2016 u Wayback Machine Otrimano z https uk wikipedia org w index php title Kitajska teorema pro ostachi amp oldid 39225979