Čínská věta o zbytku - Chinese remainder theorem - Wikipedia

Originální formulace Sun-tzu: X ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) s řešením X = 23 + 105k, kde k ∈ ℤ

v teorie čísel, Čínská věta o zbytku uvádí, že pokud někdo zná zbytky Euklidovské dělení z celé číslo n několika celými čísly, pak lze jednoznačně určit zbytek dělení n součinem těchto celých čísel za podmínky, že dělitele jsou dvojice coprime.

Nejdříve známé tvrzení věty je čínský matematik Sun-tzu v Sun-tzu Suan-ťing ve 3. století našeho letopočtu.

Čínská věta o zbytku je široce používána pro výpočet s velkými celými čísly, protože umožňuje nahradit výpočet, u kterého lze určit mezní hodnotu výsledku několika podobnými výpočty na malých celých číslech.

Čínská věta o zbytku (vyjádřená jako shody ) platí pro všechny hlavní ideální doména. Bylo zobecněno na všechny komutativní prsten, s formulací zahrnující ideály.

Dějiny

Nejdříve známé tvrzení věty, jako problém s konkrétními čísly, se objevuje v knize 3. století Sun-tzu Suan-ťing čínský matematik Sun-tzu:^[1]

Existují určité věci, jejichž počet není znám. Pokud je spočítáme po třech, zbývají nám dva; po pěti nám zbývají tři; a sedmičky, dva zbyly. Kolik je tam věcí?^[2]

Práce Sun-tzu neobsahuje ani důkaz, ani úplný algoritmus.^[3] Co představuje algoritmus pro řešení tohoto problému, popsal Aryabhata (6. století).^[4] Byly známy také speciální případy čínské věty o zbytku Brahmagupta (7. století), a objevit se v Fibonacci je Liber Abaci (1202).^[5] Výsledek byl později zobecněn kompletním řešením s názvem Ta-yan-shu (大 衍 術) v Ch'in Chiu-shao je 1247 Matematické pojednání v devíti sekcích (數 書 九章, Shu-shu Chiu-chang)^[6] který na počátku 19. století přeložil britský misionář do angličtiny Alexander Wylie.^[7]

Čínská věta o zbytku se objeví v Gauss kniha z roku 1801 Disquisitiones Arithmeticae.^[8]

Pojem shody byl poprvé představen a používán Gauss v jeho Disquisitiones Arithmeticae z roku 1801.^[9] Gauss ilustruje čínskou zbývající větu o problému týkajícím se kalendářů, konkrétně „najít roky, které mají určitý počet období, pokud jde o sluneční a lunární cyklus a římskou indikaci“.^[10] Gauss zavádí postup řešení problému, který již byl použit Euler ale ve skutečnosti to byla starodávná metoda, která se objevila několikrát.^[11]

Prohlášení

Nechat n₁, ..., n_k být celá čísla větší než 1, která se často nazývají moduly nebo dělitele. Označme tím N produkt n_i.

Čínská věta o zbytku tvrdí, že pokud n_i jsou dvojice coprime, a pokud A₁, ..., A_k jsou celá čísla taková, že 0 ≤ A_i < n_i pro každého i, pak je jedno a pouze jedno celé číslo X, takže 0 ≤ X < N a zbytek Euklidovské dělení z X podle n_i je A_i pro každého i.

To může být přepracováno následovně z hlediska shody: Pokud n_i jsou párové coprime, a pokud A₁, ..., A_k jsou libovolná celá čísla, pak existují celá čísla X takhle

${ displaystyle { begin {aligned} x & equiv a_ {1} { pmod {n_ {1}}} & , , , vdots x & equiv a_ {k} { pmod { n_ {k}}}, end {zarovnáno}}}$

a řekněme jakákoli dvě řešení X₁ a X₂, jsou shodné modulo N, to znamená, X₁ ≡ X₂ (mod N).^[12]

v abstraktní algebra, věta je často přepracována jako: pokud n_i jsou párové coprime, mapa

${ displaystyle x { bmod {N}} ; mapsto ; (x { bmod {n}} _ {1}, , ldots, , x { bmod {n}} _ {k} )}$

definuje a kruhový izomorfismus^[13]

${ displaystyle mathbb {Z} / N mathbb {Z} cong mathbb {Z} / n_ {1} mathbb {Z} times cdots times mathbb {Z} / n_ {k} mathbb {Z}}$

mezi prsten z celá čísla modulo N a přímý produkt prstenů celých čísel modulo n_i. To znamená, že pro provádění posloupnosti aritmetických operací v ${ displaystyle mathbb {Z} / N mathbb {Z},}$ jeden může udělat stejný výpočet nezávisle na každém ${ displaystyle mathbb {Z} / n_ {i} mathbb {Z}}$ a poté získáte výsledek uplatněním izomorfismu (zprava doleva). To může být mnohem rychlejší než přímý výpočet, pokud N a počet operací je velký. To je široce používáno pod názvem multimodulární výpočet, pro lineární algebra přes celá čísla nebo racionální čísla.

Věta může být také přepracována do jazyka kombinatorika jako skutečnost, že nekonečný aritmetické průběhy celých čísel tvoří a Helly rodina.^[14]

Důkaz

Existenci a jedinečnost řešení lze prokázat samostatně. První důkaz existence, uvedený níže, však tuto jedinečnost využívá.

Jedinečnost

Předpokládejme to X a y jsou obě řešení všech shod. Tak jako X a y dát stejný zbytek, když se vydělí n_i, jejich rozdíl X − y je násobkem každého z nich n_i. Jako n_i jsou párové coprime, jejich produkt N rozdělí také X − y, a tudíž X a y jsou shodné modulo N. Li X a y mají být nezáporné a menší než N (jako v prvním tvrzení věty), pak jejich rozdíl může být násobkem N jen když X = y.

Existence (první důkaz)

Mapa

${ displaystyle x { bmod {N}} mapsto (x { bmod {n}} _ {1}, ldots, x { bmod {n}} _ {k})}$

mapuje třídy kongruence modulo N na sekvence tříd kongruence modulo n_i. Důkaz jedinečnosti ukazuje, že tato mapa je injekční. Jako doména a codomain této mapy mají stejný počet prvků, mapa je také surjektivní, což dokazuje existenci řešení.

Tento důkaz je velmi jednoduchý, ale neposkytuje žádný přímý způsob výpočtu řešení. Navíc jej nelze zobecnit na jiné situace, kde následující důkaz může.

Existence (konstruktivní důkaz)

Existence může být prokázána výslovnou konstrukcí X.^[15] Tuto konstrukci lze rozdělit do dvou kroků, nejprve řešením problému v případě dvou modulů a druhým rozšířením tohoto řešení na obecný případ o indukce na počtu modulů.

Případ dvou modulů

Chceme vyřešit systém:

${ displaystyle { begin {aligned} x & equiv a_ {1} { pmod {n_ {1}}} x & equiv a_ {2} { pmod {n_ {2}}}, end {zarovnáno }}}$

kde ${ displaystyle n_ {1}}$ a ${ displaystyle n_ {2}}$ jsou coprime.

Bézoutova identita tvrdí existenci dvou celých čísel ${ displaystyle m_ {1}}$ a ${ displaystyle m_ {2}}$ takhle

${ displaystyle m_ {1} n_ {1} + m_ {2} n_ {2} = 1.}$

Celá čísla ${ displaystyle m_ {1}}$ a ${ displaystyle m_ {2}}$ může být vypočítán rozšířený euklidovský algoritmus.

Řešení je dáno

${ displaystyle x = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1}.}$

Vskutku,

${ displaystyle { begin {aligned} x & = a_ {1} m_ {2} n_ {2} + a_ {2} m_ {1} n_ {1} & = a_ {1} (1-m_ {1 } n_ {1}) + a_ {2} m_ {1} n_ {1} & = a_ {1} + (a_ {2} -a_ {1}) m_ {1} n_ {1}, end {zarovnaný}}}$

z toho vyplývá ${ displaystyle x equiv a_ {1} { pmod {n_ {1}}}.}$ Druhá shoda se dokazuje obdobně, výměnou indexů 1 a 2.

Obecný případ

Zvažte posloupnost rovnic kongruence:

${ displaystyle { begin {aligned} x & equiv a_ {1} { pmod {n_ {1}}} & vdots x & equiv a_ {k} { pmod {n_ {k}}} , end {zarovnáno}}}$

Kde ${ displaystyle n_ {i}}$ jsou párové coprime. První dvě rovnice mají řešení ${ displaystyle a_ {1,2}}$ poskytované metodou předchozí části. Množina řešení těchto dvou prvních rovnic je množinou všech řešení rovnice

${ displaystyle x equiv a_ {1,2} { pmod {n_ {1} n_ {2}}}.}$

Jako druhý ${ displaystyle n_ {i}}$ jsou coprime s ${ displaystyle n_ {1} n_ {2},}$ to snižuje řešení počátečního problému k rovnice k podobnému problému s ${ displaystyle k-1}$ rovnice. Po iteraci procesu se nakonec dostane řešení počátečního problému.

Existence (přímá konstrukce)

Pro konstrukci řešení není nutné provádět indukci počtu modulů. Taková přímá konstrukce však zahrnuje více výpočtů s velkým počtem, což z ní činí méně efektivní a méně používané. Nicméně, Lagrangeova interpolace je speciální případ této konstrukce, aplikovaný na polynomy místo celých čísel.

Nechat ${ displaystyle N_ {i} = N / n_ {i}}$ být produktem všech modulů kromě jednoho. Jako ${ displaystyle n_ {i}}$ jsou párové coprime, ${ displaystyle N_ {i}}$ a ${ displaystyle n_ {i}}$ jsou coprime. Tím pádem Bézoutova identita platí a existují celá čísla ${ displaystyle M_ {i}}$ a ${ displaystyle m_ {i}}$ takhle

${ displaystyle M_ {i} N_ {i} + m_ {i} n_ {i} = 1.}$

Řešení systému kongruencí je

${ displaystyle x = sum _ {i = 1} ^ {k} a_ {i} M_ {i} N_ {i}.}$

Ve skutečnosti jako ${ displaystyle N_ {j}}$ je násobkem ${ displaystyle n_ {i}}$ pro ${ displaystyle i neq j,}$my máme

${ displaystyle x equiv a_ {i} M_ {i} N_ {i} equiv a_ {i} (1-m_ {i} n_ {i}) equiv a_ {i} { pmod {n_ {i} }},}$

pro každého ${ displaystyle i.}$

Výpočet

Zvažte systém kongruencí:

${ displaystyle { begin {aligned} x & equiv a_ {1} { pmod {n_ {1}}} & vdots x & equiv a_ {k} { pmod {n_ {k}}} , end {zarovnáno}}}$

Kde ${ displaystyle n_ {i}}$ jsou párové coprime a nechte ${ displaystyle N = n_ {1} n_ {2} cdots n_ {k}.}$ V této části je popsáno několik metod výpočtu jedinečného řešení pro ${ displaystyle x}$, takový, že ${ displaystyle 0 leq x$ a tyto metody jsou použity na příkladu:

${ displaystyle { begin {aligned} x & equiv 0 { pmod {3}} x & equiv 3 { pmod {4}} x & equiv 4 { pmod {5}}. end { zarovnaný}}}$

Systematické vyhledávání

Je snadné zkontrolovat, zda je hodnota X je řešení: stačí spočítat zbytek Euklidovské dělení z X každý n_i. K nalezení řešení tedy stačí postupně zkontrolovat celá čísla z 0 na N až do nalezení řešení.

Ačkoli je tato metoda velmi jednoduchá, je velmi neefektivní. Pro jednoduchý příklad zde uvažovaný, 40 celá čísla (včetně 0) musí být zkontrolováno pro nalezení řešení, což je 39. Tohle je exponenciální čas algoritmus, protože velikost vstupu je až do konstantního faktoru počet číslic Na průměrný počet operací je řádově N.

Proto se tato metoda používá jen zřídka, ani pro ručně psané výpočty, ani pro počítače.

Hledejte proséváním

Hledání řešení může být dramaticky rychlejší proséváním. U této metody předpokládáme, že bez ztráty obecnosti ${ displaystyle 0 leq a_ {i}$ (pokud by tomu tak nebylo, stačilo by je každý vyměnit ${ displaystyle a_ {i}}$ ve zbytku jeho dělení ${ displaystyle n_ {i}}$). To znamená, že řešení patří do aritmetický postup

${ displaystyle a_ {1}, a_ {1} + n_ {1}, a_ {1} + 2n_ {1}, ldots}$

Testováním hodnot těchto čísel modulo ${ displaystyle n_ {2},}$ jeden nakonec najde řešení ${ displaystyle x_ {2}}$ dvou prvních kongruencí. Pak řešení patří do aritmetického postupu

${ displaystyle x_ {2}, x_ {2} + n_ {1} n_ {2}, x_ {2} + 2n_ {1} n_ {2}, ldots}$

Testování hodnot těchto čísel modulo ${ displaystyle n_ {3},}$a pokračování, dokud nebude testován každý modul, nakonec poskytne řešení.

Tato metoda je rychlejší, pokud byly moduly seřazeny podle klesající hodnoty, tedy pokud ${ displaystyle n_ {1}> n_ {2}> cdots> n_ {k}.}$ V příkladu je uveden následující výpočet. Zvažujeme nejprve čísla, která jsou shodná se 4 modulo 5 (největší modul), což jsou 4, 9 = 4 + 5, 14 = 9 + 5, ... U každého z nich spočítáme zbytek o 4 (druhý největší modul), dokud nezískáme kongruentní číslo se 3 moduly 4. Pak můžeme pokračovat přidáním 20 = 5×4 v každém kroku a výpočet pouze zbývajících 3. To dává

4 mod 4 → 0. Pokračovat

4 + 5 = 9 mod 4 → 1. Pokračovat

9 + 5 = 14 mod 4 → 2. Pokračovat

14 + 5 = 19 mod 4 → 3. OK, pokračujte zvážením zbytků modulo 3 a pokaždé přidáním 5 × 4 = 20

19 mod 3 → 1. Pokračovat

19 + 20 = 39 mod 3 → 0. OK, toto je výsledek.

Tato metoda funguje dobře pro ručně psaný výpočet s produktem modulů, který není příliš velký. U velmi velkých produktů modulů je však mnohem pomalejší než jiné metody. Ačkoli je tato metoda výrazně rychlejší než systematické vyhledávání, má také exponenciální čas složitost, a proto se nepoužívá na počítačích.

Použití konstrukce existence

The důkaz konstruktivní existence ukazuje, že v případ dvou modulů, řešení lze získat výpočtem Bézoutovy koeficienty modulů, následovaných několika multiplikacemi, doplněními a redukcemi modulo ${ displaystyle n_ {1} n_ {2}}$ (pro získání výsledku v intervalu ${ displaystyle (0, n_ {1} n_ {2} -1)}$). Protože Bézoutovy koeficienty lze vypočítat s rozšířený euklidovský algoritmus, celý výpočet má nanejvýš kvadratický časová složitost z ${ displaystyle O ((s_ {1} + s_ {2}) ^ {2}),}$ kde ${ displaystyle s_ {i}}$ označuje počet číslic ${ displaystyle n_ {i}.}$

U více než dvou modulů umožňuje metoda dvou modulů nahrazení jakýchkoli dvou kongruencí jednou kongruencí modulo produktu modulů. Iterace tohoto procesu nakonec poskytuje řešení složitost, která je kvadratická v počtu číslic produktu všech modulů. Tato kvadratická časová složitost nezávisí na pořadí, ve kterém jsou moduly přeskupeny. Jeden může přeskupit dva první moduly, potom přeskupit výsledný modul s dalším a tak dále. Tuto strategii je nejsnadnější implementovat, vyžaduje však také více výpočtů zahrnujících velké počty.

Další strategie spočívá v rozdělení modulů do párů, jejichž produkt má srovnatelné velikosti (pokud možno), paralelní použití metody dvou modulů na každou dvojici a iterace s počtem modulů přibližně dělených dvěma. Tato metoda umožňuje snadnou paralelizaci algoritmu. Také, pokud rychlé algoritmy (to jsou algoritmy pracující v kvazilineární čas ) se používají pro základní operace, tato metoda poskytuje algoritmus pro celý výpočet, který pracuje v kvazilineárním čase.

Na aktuálním příkladu (který má pouze tři moduly) jsou obě strategie identické a fungují následovně.

Bézoutova identita pro 3 a 4 je

${ Displaystyle 1 krát 4 + (- 1) krát 3 = 1.}$

Uvedení do vzorce uvedeného pro prokázání existence dává

${ displaystyle 0 krát 1 krát 4 + 3 krát (-1) krát 3 = -9}$

pro řešení dvou prvních kongruencí, další řešení se získá přidáním k -9 libovolnému násobku 3×4 = 12. Jeden může pokračovat v kterémkoli z těchto řešení, ale řešení 3 = −9 +12 je menší (v absolutní hodnotě) a vede tedy pravděpodobně ke snadnějšímu výpočtu

Identita Bézout pro 5 a 3 × 4 = 12 je

${ displaystyle 5 krát 5 + (- 2) krát 12 = 1.}$

Opětovným použitím stejného vzorce získáme řešení problému:

${ Displaystyle 25 krát 3-24 krát 4 = -21.}$

Ostatní řešení se získají přidáním libovolného násobku 3×4×5 = 60a nejmenší pozitivní řešení je −21 + 60 = 39.

Jako lineární diofantický systém

Systém kongruencí vyřešený čínskou větou o zbytku lze přepsat jako a systém simultánních lineárních diofantických rovnic:

${ displaystyle { begin {sladěno} x & = a_ {1} + x_ {1} n_ {1} & vdots x & = a_ {k} + x_ {k} n_ {k}, end { zarovnaný}}}$

kde jsou neznámá celá čísla ${ displaystyle x}$ a ${ displaystyle x_ {i}.}$ Proto lze pro nalezení řešení čínské věty o zbytku použít každou obecnou metodu řešení těchto systémů, jako je redukce matice systému na Smith normální forma nebo Poustevník normální forma. Jako obvykle při použití obecného algoritmu pro konkrétnější problém je však tento přístup méně efektivní než metoda předchozí části, založená na přímém použití Bézoutova identita.

Přes hlavní ideální domény

v § Věta, čínská věta o zbytku byla uvedena třemi různými způsoby: pokud jde o zbytky, shody a prstencový izomorfismus. Prohlášení ve smyslu zbytku se obecně nevztahuje na hlavní ideální domény, protože zbytky nejsou v těchto kruzích definovány. Dvě další verze však dávají smysl nad hlavní ideální doménou R: stačí nahradit „celé číslo“ výrazem „prvek domény“ a ${ displaystyle mathbb {Z}}$ podle R. Tyto dvě verze věty jsou v tomto kontextu pravdivé, protože důkazy (kromě prvního důkazu o existenci) jsou založeny na Euklidovo lemma a Bézoutova identita, které platí pro každou hlavní doménu.

Obecně je však věta pouze teorémem existence a neposkytuje žádný způsob výpočtu řešení, pokud nemá algoritmus pro výpočet koeficientů Bézoutovy identity.

Přes jednorozměrné polynomiální kruhy a euklidovské domény

Prohlášení o zbytcích uvedené v § Věta nelze zobecnit na žádnou hlavní ideální doménu, ale její zobecnění na Euklidovské domény je přímočará. The jednorozměrné polynomy přes pole je typickým příkladem euklidovské domény, která není celými čísly. Proto uvedeme větu pro případ prstence univariate domény ${ displaystyle R = K [X]}$ přes pole ${ displaystyle K.}$ Pro získání věty pro obecnou euklidovskou doménu stačí nahradit stupeň znakem Euklidovská funkce euklidovské domény.

Čínská věta o zbytku pro polynomy je tedy: Let ${ displaystyle P_ {i} (X)}$ (moduly) být, pro i=1, ..., k, dvojice coprime polynomy v ${ displaystyle R = K [X]}$. Nechat ${ displaystyle d_ {i} = deg P_ {i}}$ být mírou ${ displaystyle P_ {i} (X)}$, a ${ displaystyle D}$ být součtem ${ displaystyle d_ {i}.}$Li ${ displaystyle A_ {i} (X), ldots, A_ {k} (X)}$ jsou polynomy takové, že ${ displaystyle A_ {i} (X) = 0}$ nebo ${ displaystyle deg A_ {i}$ pro každého i, pak existuje jeden a pouze jeden polynom ${ displaystyle P (X)}$, takový, že ${ displaystyle deg P$ a zbytek Euklidovské dělení z ${ displaystyle P (X)}$ podle ${ displaystyle P_ {i} (X)}$ je ${ displaystyle A_ {i} (X)}$ pro každého i.

Konstrukci řešení lze provést jako v § Existence (konstruktivní důkaz) nebo § Existence (přímý důkaz). Tuto druhou konstrukci však lze zjednodušit pomocí následujícího postupu: rozklad částečné frakce namísto rozšířený euklidovský algoritmus.

Chceme tedy najít polynom ${ displaystyle P (X)}$, což uspokojí shodu

${ displaystyle P (X) equiv A_ {i} (X) { pmod {P_ {i} (X)}},}$

pro ${ displaystyle i = 1, ldots, k.}$

Zvažte polynomy

${ displaystyle { begin {zarovnaný} Q (X) & = prod _ {i = 1} ^ {k} P_ {i} (X) Q_ {i} (X) & = { frac {Q (X)} {P_ {i} (X)}}. End {zarovnáno}}}$

Rozklad částečné frakce ${ displaystyle 1 / Q (X)}$ dává k polynomy ${ displaystyle S_ {i} (X)}$ se stupni ${ displaystyle deg S_ {i} (X)$ takhle

${ displaystyle { frac {1} {Q (X)}} = součet _ {i = 1} ^ {k} { frac {S_ {i} (X)} {P_ {i} (X)} },}$

a tudíž

${ displaystyle 1 = součet _ {i = 1} ^ {k} S_ {i} (X) Q_ {i} (X).}$

Pak je polynomem dáno řešení systému simultánní kongruence

${ displaystyle sum _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X).}$

Ve skutečnosti máme

${ displaystyle sum _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X) = A_ {i} (X) + součet _ {j = 1} ^ {k} (A_ {j} (X) -A_ {i} (X)) S_ {j} (X) Q_ {j} (X) equiv A_ {i} (X) { pmod {P_ {i} (X)}},}$

pro ${ Displaystyle 1 leq i leq k.}$

Toto řešení může mít o stupeň větší velikost ${ displaystyle D = sum _ {i = 1} ^ {k} d_ {i}.}$ Unikátní řešení stupně méně než ${ displaystyle D}$ lze odvodit zvážením zbývající části ${ displaystyle B_ {i} (X)}$ euklidovské divize ${ displaystyle A_ {i} (X) S_ {i} (X)}$ podle ${ displaystyle P_ {i} (X).}$ Toto řešení je

${ displaystyle P (X) = součet _ {i = 1} ^ {k} B_ {i} (X) Q_ {i} (X).}$

Lagrangeova interpolace

Zvláštní případ čínské věty o zbytku pro polynomy je Lagrangeova interpolace. Z tohoto důvodu zvažte k monické polynomy prvního stupně:

${ displaystyle P_ {i} (X) = X-x_ {i}.}$

Jsou to párové coprime, pokud ${ displaystyle x_ {i}}$ jsou různé. Zbývající část divize ${ displaystyle P_ {i} (X)}$ polynomu ${ displaystyle P (X)}$ je ${ displaystyle P (x_ {i}).}$

Teď, pojďme ${ displaystyle A_ {1}, ldots, A_ {k}}$ být konstanty (polynomy stupně 0) v ${ displaystyle K.}$ Lagrangeova interpolace i čínská věta o zbytku tvrdí, že existuje jedinečný polynom ${ displaystyle P (X),}$ stupně menší než ${ displaystyle k}$ takhle

${ displaystyle P (x_ {i}) = A_ {i},}$

pro každého ${ displaystyle i.}$

Lagrangeův interpolační vzorec je v tomto případě přesně výsledkem výše uvedené konstrukce řešení. Přesněji řečeno

${ displaystyle { begin {aligned} Q (X) & = prod _ {i = 1} ^ {k} (X-x_ {i}) [6pt] Q_ {i} (X) & = { frac {Q (X)} {X-x_ {i}}}. end {zarovnáno}}}$

The rozklad částečné frakce z ${ displaystyle { frac {1} {Q (X)}}}$ je

${ displaystyle { frac {1} {Q (X)}} = součet _ {i = 1} ^ {k} { frac {1} {Q_ {i} (x_ {i}) (X-X_ {i})}}.}$

Ve skutečnosti se redukce na pravé straně stane společným jmenovatelem

${ displaystyle sum _ {i = 1} ^ {k} { frac {1} {Q_ {i} (x_ {i}) (X-X_ {i})}} = { frac {1} { Q (X)}} sum _ {i = 1} ^ {k} { frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}}}}$

a čitatel se rovná jedné, jako polynom stupně menšího než ${ displaystyle k,}$ což má hodnotu jedna pro ${ displaystyle k}$ různé hodnoty ${ displaystyle X.}$

Pomocí výše uvedeného obecného vzorce získáme Lagrangeův interpolační vzorec:

${ displaystyle P (X) = součet _ {i = 1} ^ {k} A_ {i} { frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}}. }$

Hermitova interpolace

Hermitova interpolace je aplikace čínské věty o zbytku pro jednorozměrné polynomy, které mohou zahrnovat moduly libovolných stupňů (Lagrangeova interpolace zahrnuje pouze moduly prvního stupně).

Problém spočívá v nalezení polynomu co nejmenšího stupně, aby polynom a jeho první derivace získaly dané hodnoty v některých pevných bodech.

Přesněji řečeno ${ displaystyle x_ {1}, ldots, x_ {k}}$ být ${ displaystyle k}$ prvky země pole ${ displaystyle K,}$ a pro ${ displaystyle i = 1, ldots, k,}$ nechat ${ displaystyle a_ {i, 0}, a_ {i, 1}, ldots, a_ {i, r_ {i} -1}}$ být hodnoty prvního ${ displaystyle r_ {i}}$ deriváty hledaného polynomu v ${ displaystyle x_ {i}}$ (včetně 0. derivace, což je hodnota samotného polynomu). Problém je najít polynom ${ displaystyle P (X)}$ takový, že jeho jhodnota derivace ${ displaystyle a_ {i, j}}$ na ${ displaystyle x_ {i},}$ pro ${ displaystyle i = 1, ldots, k}$ a ${ displaystyle j = 0, ldots, r_ {j}.}$

Zvažte polynom

${ displaystyle P_ {i} (X) = součet _ {j = 0} ^ {r_ {i} -1} { frac {a_ {i, j}} {j!}} (X-x_ {i }) ^ {j}.}$

Toto je Taylorův polynom řádu ${ displaystyle r_ {i} -1}$ na ${ displaystyle x_ {i}}$, neznámého polynomu ${ displaystyle P (X).}$ Proto musíme mít

${ displaystyle P (X) equiv P_ {i} (X) { pmod {(X-x_ {i}) ^ {r_ {i}}}}.}$

Naopak jakýkoli polynom ${ displaystyle P (X)}$ to je uspokojuje ${ displaystyle k}$ shody, zejména ověřuje, pro všechny ${ displaystyle i = 1, ldots, k}$

${ displaystyle P (X) = P_ {i} (X) + o (X-x_ {i}) ^ {r_ {i} -1}}$

proto ${ displaystyle P_ {i} (X)}$ je jeho Taylorův polynom řádu ${ displaystyle r_ {i} -1}$ na ${ displaystyle x_ {i}}$, to znamená, ${ displaystyle P (X)}$ řeší počáteční problém s Hermitovou interpolací. Čínská věta o zbytku tvrdí, že existuje přesně jeden polynom stupně menší než součet ${ displaystyle r_ {i},}$ což je uspokojuje ${ displaystyle k}$ shody.

Existuje několik způsobů výpočtu řešení ${ displaystyle P (X).}$ Lze použít metodu popsanou na začátku roku 2006 § Přes jednorozměrné polynomiální kruhy a euklidovské domény. Lze také použít konstrukce uvedené v § Existence (konstruktivní důkaz) nebo § Existence (přímý důkaz).

Zobecnění na non-coprime moduly

Čínskou větu o zbytku lze zobecnit na non-coprime moduly. Nechat ${ displaystyle m, n, a, b}$ být jakákoli celá čísla, ať ${ displaystyle g = gcd (m, n)}$, a zvážit systém shody:

${ displaystyle { begin {zarovnáno} x & equiv a { pmod {m}} x & equiv b { pmod {n}}, end {zarovnáno}}}$

Li ${ displaystyle a equiv b { pmod {g}}}$, pak má tento systém rovnic jedinečné řešení modulo ${ displaystyle operatorname {lcm} (m, n) = mn / g}$. Jinak nemá žádná řešení.

Pokud použijeme Bézoutova identita psát ${ displaystyle g = um + vn}$, pak řešení je

${ displaystyle x = { frac {avn + bum} {g}}.}$

Toto definuje celé číslo jako G rozděluje obě m a n. Jinak je důkaz velmi podobný důkazu pro coprime modulyi.

Zobecnění na libovolné prsteny

Čínskou větu o zbytku lze zobecnit na jakoukoli prsten, používáním coprime ideály (také zvaný komaximální ideály ). Dva ideály Já a J jsou coprime, pokud existují prvky ${ displaystyle i in I}$ a ${ displaystyle j v J}$ takhle ${ displaystyle i + j = 1.}$ Tento vztah hraje roli Bézoutova identita v důkazech souvisejících s tímto zevšeobecněním, které jsou jinak velmi podobné. Zevšeobecnění lze konstatovat následovně.^[16]

Nechat Já₁, ..., Já_k být oboustranné ideály prstenu ${ displaystyle R}$ a nechte Já být jejich křižovatkou. Pokud jsou ideály párové coprime, máme izomorfismus:

${ displaystyle { begin {zarovnáno} R / I & na R / I_ {1} krát cdots krát R / I_ {k} x { bmod {I}} & mapsto (x { bmod {I}} _ {1}, , ldots, , x { bmod {I}} _ {k}), end {zarovnáno}}}$

mezi kvocientový kroužek ${ displaystyle R / I}$ a přímý produkt z ${ displaystyle R / I_ {i},}$kde "${ displaystyle x { bmod {I}}}$"označuje obrázek prvku ${ displaystyle x}$ v kvocientovém kruhu definovaném ideálem ${ displaystyle I.}$Navíc pokud ${ displaystyle R}$ je komutativní, pak je ideální průnik ideálu párových coprime roven jejich produkt; to je

${ displaystyle I = I_ {1} cap I_ {2} cap cdots cap I_ {k} = I_ {1} I_ {2} cdots I_ {k},}$

-li Já_i a Já_j jsou coprime pro i ≠ j.

Aplikace

Sekvenční číslování

Čínská věta o zbytku byla použita ke konstrukci a Gödelovo číslování sekvencí, který je součástí dokladu o Gödelovy věty o neúplnosti.

Rychlá Fourierova transformace

The algoritmus FFT prime-factor (také nazývaný Good-Thomasův algoritmus) používá čínskou větu o zbytku ke snížení výpočtu a rychlá Fourierova transformace velikosti ${ displaystyle n_ {1} n_ {2}}$ k výpočtu dvou rychlých Fourierových transformací menších velikostí ${ displaystyle n_ {1}}$ a ${ displaystyle n_ {2}}$ (za předpokladu, že ${ displaystyle n_ {1}}$ a ${ displaystyle n_ {2}}$ jsou coprime).

Šifrování

Většina implementace RSA používají větu o čínském zbytku během podpisu HTTPS certifikáty a během dešifrování.

Čínská věta o zbytku může být také použita v tajné sdílení, který spočívá v distribuci sady akcií mezi skupinu lidí, kteří společně (ale nikdo sám) nemůže z dané sady akcií získat určité tajemství. Každá z akcií je reprezentována v kongruenci a tajemství, které je třeba obnovit, je řešení systému kongruencí pomocí čínské věty o zbytku. Tajné sdílení pomocí čínské věty o zbytku používá spolu s čínskou větou o zbytku speciální sekvence celých čísel, které zaručují nemožnost získání tajemství ze sady akcií s méně než určitou mohutnost.

Rozlišení nejednoznačnosti rozsahu

The rozlišení nejasností rozsahu techniky používané s střední frekvence opakování pulzů radar lze považovat za zvláštní případ věty o čínském zbytku.

Dedekindova věta

Dedekindova věta o lineární nezávislosti postav. Nechat M být monoidní a k an integrální doména, považováno za monoid s ohledem na násobení na k. Pak jakákoli konečná rodina ( F_i )_i∈Já zřetelných monoidních homomorfismů  F_i : M → k je lineárně nezávislý. Jinými slovy, každá rodina (α_i)_i∈Já prvků α_i ∈ k uspokojující

${ displaystyle sum _ {i v I} alfa _ {i} f_ {i} = 0}$

musí se rovnat rodině (0)_i∈Já.

Důkaz. Nejprve to předpokládej k je pole, jinak nahraďte integrální doménu k podle pole kvocientu a nic se nezmění. Monoidní homomorfismy můžeme lineárně rozšířit  F_i : M → k na k-algebrické homomorfismy F_i : k[M] → k, kde k[M] je monoidní prsten z M přes k. Potom podle linearity podmínka

${ displaystyle sum _ {i v I} alfa _ {i} f_ {i} = 0,}$

výnosy

${ displaystyle sum _ {i in I} alpha _ {i} F_ {i} = 0.}$

Dále pro i, j ∈ Já; i ≠ j dva k-lineární mapy F_i : k[M] → k a F_j : k[M] → k nejsou navzájem úměrné. v opačném případě  F_i  a  F_j  by také byly proporcionální, a tedy stejné, protože jako monoidní homomorfismy splňují:  F_i (1) = 1 =  F_j (1), což je v rozporu s předpokladem, že jsou odlišné.

Proto jádra Ker F_i a Ker F_j jsou odlišné. Od té doby k[M] / Ker F_i ≅ F_i(k[M]) = k je pole, Ker F_i je maximálním ideálem k[M] pro každého i ∈ Já. Protože jsou odlišné a maximální ideály Ker F_i a Ker F_j jsou coprime kdykoli i ≠ j. Věta o čínském zbytku (pro obecné prsteny) poskytuje izomorfismus:

${ displaystyle { begin {zarovnáno} phi: k [M] / K & to prod _ {i v I} k [M] / mathrm {Ker} F_ {i} phi (x + K) & = left (x + mathrm {Ker} F_ {i} right) _ {i in I} end {aligned}}}$

kde

${ displaystyle K = prod _ {i in I} mathrm {Ker} F_ {i} = bigcap _ {i in I} mathrm {Ker} F_ {i}.}$

Následně mapa

${ displaystyle { begin {zarovnáno} Phi: k [M] & to prod _ {i in I} k [M] / mathrm {Ker} F_ {i} Phi (x) & = left (x + mathrm {Ker} F_ {i} right) _ {i in I} end {aligned}}}$

je surjektivní. Pod izomorfismy k[M] / Ker F_i → F_i(k[M]) = k, mapa Φ odpovídá:

${ displaystyle { begin {zarovnáno} psi: k [M] & to prod _ {i in I} k psi (x) & = left [F_ {i} (x) right ] _ {i in I} end {zarovnáno}}}$

Nyní,

${ displaystyle sum _ {i v I} alfa _ {i} F_ {i} = 0}$

výnosy

${ displaystyle sum _ {i v I} alfa _ {i} u_ {i} = 0}$

pro každý vektor (u_i)_i∈Já na obrázku mapy ψ. Od té doby ψ je surjektivní, to znamená, že

${ displaystyle sum _ {i v I} alfa _ {i} u_ {i} = 0}$

pro každý vektor

${ displaystyle left (u_ {i} right) _ {i in I} in prod _ {i in I} k.}$

Tudíž, (α_i)_i∈Já = (0)_i∈Já. QED.

Viz také

• Krycí systém
• Hasseův princip
• Systém čísel zbytků

Poznámky

Reference

• Dauben, Joseph W. (2007), „Kapitola 3: Čínská matematika“, Katz, Victor J. (ed.), Matematika Egypta, Mezopotámie, Číny, Indie a islámu: Zdrojová kniha, Princeton University Press, s. 187–384, ISBN  978-0-691-11485-9
• Dence, Joseph B .; Dence, Thomas P. (1999), Základy teorie čísel Akademický tisk, ISBN  9780122091308
• Duchet, Pierre (1995), "Hypergraphs", Graham, R. L .; Grötschel, M.; Lovász, L. (eds.), Handbook of combineatorics, Vol. 1, 2, Amsterdam: Elsevier, s. 381–432, PAN  1373663. Viz zejména Oddíl 2.5, „Helly Property“, 393–394.
• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae, přeložil Clarke, Arthur A. (druhý, opravené vydání), New York: Springer, ISBN  978-0-387-96254-2
• Irsko, Kenneth; Rosen, Michael (1990), Klasický úvod do moderní teorie čísel (2. vyd.), Springer-Verlag, ISBN  0-387-97329-X
• Kak, Subhash (1986), „Výpočtové aspekty aryabhatského algoritmu“ (PDF), Indian Journal of History of Science, 21 (1): 62–71
• Katz, Victor J. (1998), Dějiny matematiky / Úvod (2. vyd.), Addison Wesley Longman, ISBN  978-0-321-01618-8
• Libbrecht, Ulrich (1973), Čínská matematika ve třináctém století: „Shu-shu Chiu-chang“ Ch'in Chiu-shao, Dover Publications Inc, ISBN  978-0-486-44619-6
• Ore, Oystein (1988) [1948], Teorie čísel a její historieDover, ISBN  978-0-486-65620-5
• Pisano, Leonardo (2002), Fibonacciho Liber Abaci, přeložil Sigler, Laurence E., Springer-Verlag, s. 402–403, ISBN  0-387-95419-8
• Rosen, Kenneth H. (1993), Teorie elementárních čísel a její aplikace (3. vyd.), Addison-Wesley, ISBN  978-0201-57889-8

Další čtení

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Úvod do algoritmů (Druhé vydání), MIT Stiskněte a McGraw-Hill, ISBN  0-262-03293-7. Viz část 31.5: Čínská věta o zbytku, str. 873–876.
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific Publishing, str.1–213, ISBN  981-02-2827-9
• Hungerford, Thomas W. (1974), Algebra, Graduate Texts in Mathematics, sv. 73, Springer-Verlag, str. 131–132, ISBN  978-1-4612-6101-8
• Knuth, Donald (1997), Umění počítačového programování, Díl 2: Seminumerické algoritmy (Třetí vydání), Addison-Wesley, ISBN  0-201-89684-2. Viz část 4.3.2 (str. 286–291), cvičení 4.6.2–3 (strana 456).

externí odkazy

• "Čínská věta o zbytku", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Weisstein, Eric W. "Čínská věta o zbytku". MathWorld.
• Čínská věta o zbytku na PlanetMath.
• Celý text Sun-tzu Suan-ťing (Čínština) - Čínský textový projekt