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

V teorii čísel se Čínské věty uvádí, že pokud jeden zná zbytky v euklidovské rozdělení části o celé číslo n o několik celých čísel, pak je možné určit jedinečně zbytek dělení n produktem těchto celých čísel, pod podmínkou, že jsou dělitele jsou pairwise coprime .

Nejdříve známý výrok věty je od čínského matematika Sun-tzu v Sun-tzu Suan-ťing ve 3. století n. L.

Čí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 je známa hranice velikosti výsledku, několika podobnými výpočty na malých celých číslech.

Čínská věta o zbytku (vyjádřená kongruencemi ) platí pro každou hlavní ideální doménu . Byl zobecněn na jakýkoli komutativní kruh s formulací zahrnující ideály .

Dějiny

Nejdříve známé tvrzení věty, jako problém konkrétních čísel, se objevuje v knize 3. století Sun-tzu Suan-ching od čínského matematika Sun-tzu:

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 zbyly tři; a sedmým zbývají dva. Kolik věcí tam je?

Práce Sun-tzu neobsahuje ani důkaz, ani úplný algoritmus. Co se rovná algoritmu pro řešení tohoto problému, popsal Aryabhata (6. století). Zvláštní případy čínského zbytek věty byly také známo, že Brahmagupta (7. století), a objevují se v Fibonacci je Liber Abaci (1202). Výsledek byl později zobecněn pomocí kompletního řešení zvaného Da-yan-shu (大 衍 術) v Ch'in Chiu-shao 's 1247 Mathematical Treatise in Nine Sections (數 書 九章, Shu-shu Chiu-chang ), které bylo přeložil do angličtiny na počátku 19. století britský misionář Alexander Wylie .

Pojem kongruence byl poprvé představen a použit Gaussem v jeho Disquisitiones Arithmeticae z roku 1801. 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é období s ohledem na sluneční a lunární cyklus a římské obvinění “. Gauss zavádí postup pro řešení problému, který již použil Euler, ale ve skutečnosti to byla starodávná metoda, která se objevila několikrát.

Tvrzení

Nechť n ₁ , ..., n _k jsou celá čísla větší než 1, kterým se často říká moduly nebo dělitelé . Označme N součinem n _i .

Čínská věta o zbytku tvrdí, že pokud n _i jsou párové coprime , a pokud a ₁ , ..., a _k jsou celá čísla taková, že 0 ≤ a _i < n _i pro každé i , pak existuje jedno a pouze jedno celé číslo x , takové, že 0 ≤ x < N a zbytek euklidovské dělení z x o n _i je _i pro každé i .

To lze přepsat následovně z hlediska kongruencí : Pokud n _i jsou párové coprime a pokud a ₁ , ..., a _k jsou libovolná celá čísla, pak systém

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

má řešení a jakákoli dvě řešení, řekněme x ₁ a x ₂ , jsou shodná modulo N , to znamená x ₁ ≡ x ₂ (mod N ) .

V abstraktní algebře je věta č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 prstencový izomorfismus

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

mezi prstencem z celých čísel N a přímý produkt prstenců celých čísel modulo n _i . To znamená, že pro provádění posloupnosti aritmetických operací v jednom lze provést stejný výpočet nezávisle v každém a poté získat výsledek použitím izomorfismu (zprava doleva). Pokud je N a počet operací velký, může to být mnohem rychlejší než přímý výpočet . To je široce používáno pod názvem multi-modulární výpočet pro lineární algebru přes celá čísla nebo racionální čísla . ${\ displaystyle \ mathbb {Z} /N \ mathbb {Z},}$${\ Displaystyle \ mathbb {Z} /n_ {i} \ mathbb {Z}}$

Tuto větu lze také zopakovat v jazyce kombinatoriky jako skutečnost, že nekonečné aritmetické posloupnosti celých čísel tvoří rodinu Helly .

Důkaz

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

Jedinečnost

Předpokládejme, že x a y jsou obě řešení všech kongruencí. Protože x a y dávají stejný zbytek, děleno n _i je jejich rozdíl x - y násobkem každého n _i . Vzhledem k tomu, n _i , jsou po dvou coprime, jejich produkt N dělí také x - y , a tím i x a y jsou shodné modulo N . Pokud 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, pouze pokud 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 injektivní . Protože doména a codoména této mapy mají stejný počet prvků, je mapa 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 může následující důkaz.

Existence (konstruktivní důkaz)

Existenci lze stanovit explicitní konstrukcí x . 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 indukcí 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 a jsou coprime. ${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$

Bézoutova identita potvrzuje existenci dvou celých čísel a podobně ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$

${\ Displaystyle m_ {1} n_ {1}+m_ {2} n_ {2} = 1.}$

Celá čísla a mohou být vypočítána rozšířeným euklidovským algoritmem . ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$

Řešení je dáno pomocí

${\ 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}, \ konec {zarovnaný}}}$

z čehož vyplývá, že Druhá shoda se prokazuje podobně výměnou dolních indexů 1 a 2. ${\ Displaystyle x \ equiv a_ {1} {\ pmod {n_ {1}}}.}$

Obecný případ

Zvažte posloupnost kongruenčních rovnic:

${\ Displaystyle {\ begin {aligned} x & \ equiv a_ {1} {\ pmod {n_ {1}}} \\ & \ vdots \\ x & \ equiv a_ {k} {\ pmod {n_ {k}}} , \ end {aligned}}}$

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

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

Protože ostatní jsou souběžné, redukuje to řešení počátečního problému k rovnic na podobný problém s rovnicemi. Iterací procesu se nakonec dočká řešení původního problému. ${\ displaystyle n_ {i}}$${\ displaystyle n_ {1} n_ {2},}$${\ Displaystyle k-1}$

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ž ji činí méně efektivní a méně používanou. Nicméně, Lagrange interpolace je zvláštní případ této stavby, působící na polynomy namísto čísel.

Nechť je produktem všech modulů kromě jednoho. Jako jsou párové coprime a jsou coprime. Platí tedy Bézoutova identita a existují celá čísla a podobně ${\ displaystyle N_ {i} = N/n_ {i}}$${\ displaystyle n_ {i}}$${\ displaystyle N_ {i}}$${\ displaystyle n_ {i}}$${\ displaystyle M_ {i}}$${\ displaystyle m_ {i}}$

${\ 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, jak je násobkem pro máme ${\ displaystyle N_ {j}}$${\ displaystyle n_ {i}}$${\ Displaystyle i \ neq j,}$

${\ 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 {aligned}}}$

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

${\ 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 hodnota x je řešení: stačí pro výpočet zbytku euklidovské rozdělení z x každý n _i . K nalezení řešení tedy stačí postupně kontrolovat celá čísla od 0 do N, dokud řešení nenajdete .

Přestože je tato metoda velmi jednoduchá, je velmi neefektivní. Pro jednoduchý zde uvažovaný příklad je třeba pro nalezení řešení zkontrolovat 40 celých čísel (včetně 0 ), což je 39 . To je exponenciální čas algoritmus, jako je velikost vstupu je, až na konstantní faktor, počet číslic z N , a průměrný počet operací je v řádu N .

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

Hledejte podle sítování

Hledání řešení může být dramaticky rychlejší prosíváním. U této metody předpokládáme bez ztráty obecnosti, že (pokud by tomu tak nebylo, stačilo by nahradit každou zbývající částí jejího dělení ). To znamená, že řešení patří do aritmetické progrese${\ Displaystyle 0 \ leq a_ {i} <n_ {i}}$${\ displaystyle a_ {i}}$${\ displaystyle n_ {i}}$

${\ Displaystyle a_ {1}, a_ {1}+n_ {1}, a_ {1}+2n_ {1}, \ ldots}$

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

${\ Displaystyle x_ {2}, x_ {2}+n_ {1} n_ {2}, x_ {2}+2n_ {1} n_ {2}, \ ldots}$

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

Tato metoda je rychlejší, pokud byly moduly uspořádány podle klesající hodnoty, to znamená, že v případě příkladu to poskytuje následující výpočet. Nejprve uvažujeme čísla, která jsou shodná se 4 modulo 5 (největší modul), což jsou 4, 9 = 4 + 5 , 14 = 9 + 5 , ... Pro každé z nich spočítejte zbytek o 4 (druhý největší modul), dokud nedosáhneme čísla shodného se 3 modulo 4. Poté lze pokračovat tak, že v každém kroku přidáme 20 = 5 × 4 a vypočítáme pouze zbytky o 3. Tím dostaneme ${\ Displaystyle n_ {1}> n_ {2}> \ cdots> n_ {k}.}$

4 mod 4 → 0. Pokračujte

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

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

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

19 mod 3 → 1. Pokračujte

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

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

Použití konstrukce existence

Tyto konstrukční existence důkaz ukazuje, že v případě dvou modulů , může být roztok, získané výpočtem z Bézout koeficientů z modulů, následovaná několika násobení, dodatky a snížení modulo (pro získání výsledku v intervalu ). Jako Bézout se koeficienty mohou být vypočteny s prodlouženým Euclidean algoritmem , celý výpočet nanejvýš má kvadratickou časovou složitost a kde označuje počet číslic${\ displaystyle n_ {1} n_ {2}}$${\ Displaystyle (0, n_ {1} n_ {2} -1)}$${\ displaystyle O ((s_ {1}+s_ {2})^{2}),}$${\ displaystyle s_ {i}}$${\ displaystyle n_ {i}.}$

U více než dvou modulů umožňuje metoda pro dva moduly nahrazení jakýchkoli dvou kongruencí jediným modulem kongruence modulem produktu modulů. Iterace tohoto procesu nakonec poskytne řešení se složitostí, která je kvadratická v počtu číslic součinu 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, pak přeskupit výsledný modul s dalším a tak dále. Tuto strategii je nejjednodušší implementovat, ale také vyžaduje více výpočtů zahrnujících velký počet.

Další strategie spočívá v rozdělení modulů do párů, jejichž produkt má srovnatelné velikosti (co nejvíce), paralelní použití metody dvou modulů na každý pár a iterace s počtem modulů přibližně dělených dvěma. Tato metoda umožňuje snadnou paralelizaci algoritmu. Pokud jsou pro základní operace použity také rychlé algoritmy (tj. Algoritmy pracující v kvazineárním čase ), poskytuje tato metoda algoritmus pro celý výpočet, který funguje v kvazineárním čase.

Na současném příkladu (který má pouze tři moduly) jsou obě strategie totožné a fungují následovně.

Bézoutova identita pro 3 a 4 je

${\ Displaystyle 1 \ times 4+(-1) \ times 3 = 1.}$

Dát to do vzorce uvedeného pro prokázání existence dává

${\ Displaystyle 0 \ times 1 \ times 4+3 \ times (-1) \ times 3 = -9}$

pro řešení dvou prvních kongruencí se ostatní řešení získají přičtením k -9 libovolného násobku 3 × 4 = 12 . Lze pokračovat jakýmkoli z těchto řešení, ale řešení 3 = −9 +12 je menší (v absolutní hodnotě), a proto pravděpodobně vede ke snadnějšímu výpočtu

Bézoutova identita pro 5 a 3 × 4 = 12 je

${\ displaystyle 5 \ times 5+(-2) \ times 12 = 1.}$

Když znovu použijeme stejný vzorec, dostaneme řešení problému:

${\ displaystyle 25 \ times 3-24 \ times 4 = -21.}$

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

Jako lineární diofantinový systém

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

${\ displaystyle {\ begin {aligned} x & = a_ {1}+x_ {1} n_ {1} \\ & \ vdots \\ x & = a_ {k}+x_ {k} n_ {k}, \ end { zarovnaný}}}$

kde jsou neznámá celá čísla a proto může být pro nalezení řešení čínské zbytkové věty použita každá obecná metoda řešení takových systémů, jako je redukce matice systému na Smithovu normální formu nebo Hermitovu normální formu . Nicméně, jako obvykle při použití obecného algoritmu pro konkrétnější problém, je tento přístup méně účinný než metoda z předchozí části, založená na přímém použití Bézoutovy identity . ${\ displaystyle x}$${\ displaystyle x_ {i}.}$

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

V § prohlášení byla čínská věta o zbytku uvedena třemi různými způsoby: pokud jde o zbytky, kongruence a kruhový izomorfismus. Prohlášení týkající se zbytků se obecně nevztahuje na hlavní ideální domény , protože zbytky nejsou v takových prstencích definovány. Nicméně, dvě další verze smysl přes hlavní ideální domény R : stačí nahradit „číslo“ od „prvek domény“, a tím, R . Tyto dvě verze věty jsou v tomto kontextu pravdivé, protože důkazy (s výjimkou prvního důkazu existence) jsou založeny na Euclidově lemmatu a Bézoutově identitě , které platí pro každou hlavní doménu. ${\ displaystyle \ mathbb {Z}}$

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

Přes univariační polynomické prstence a euklidovské domény

Prohlášení týkající se zbytků uvedených v § Věta tvrzení nelze zobecnit na žádnou hlavní ideální doménu, ale její zobecnění na euklidovské domény je přímočaré. V jednorozměrné polynomy nad pole je typickým příkladem euklidovské domény, která není celá čísla. Proto uvádíme větu pro případ prstence univariační domény nad polem Pro získání věty pro obecnou euklidovskou doménu postačí nahradit stupeň euklidovskou funkcí euklidovské domény. ${\ displaystyle R = K [X]}$${\ Displaystyle K.}$

Čínská zbývající věta pro polynomy je tedy: Nechť (moduly) jsou pro i = 1, ..., k , párové coprime polynomy v . Dovolit být stupeň a bude součtem If jsou polynomy takové, že ani pro každý i , pak je tam jeden a pouze jeden polynom , takže i zbytek euklidovské divize ze tím je pro každého i . ${\ displaystyle P_ {i} (X)}$${\ displaystyle R = K [X]}$${\ displaystyle d_ {i} = \ deg P_ {i}}$${\ displaystyle P_ {i} (X)}$${\ displaystyle D}$${\ displaystyle d_ {i}.}$${\ displaystyle A_ {i} (X), \ ldots, A_ {k} (X)}$${\ displaystyle A_ {i} (X) = 0}$${\ Displaystyle \ deg A_ {i} <d_ {i}}$${\ displaystyle P (X)}$${\ Displaystyle \ deg P <D}$${\ displaystyle P (X)}$${\ displaystyle P_ {i} (X)}$${\ displaystyle A_ {i} (X)}$

Konstrukci řešení lze provést podle § Existence (konstruktivní důkaz) nebo § Existence (přímý důkaz) . Posledně jmenovanou konstrukci však lze zjednodušit použitím níže uvedeného rozkladu částečných zlomků namísto rozšířeného euklidovského algoritmu .

Chceme tedy najít polynom , který splňuje kongruence ${\ displaystyle P (X)}$

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

pro ${\ Displaystyle i = 1, \ ldots, k.}$

Zvažte polynomy

${\ Displaystyle {\ begin {aligned} Q (X) & = \ prod _ {i = 1}^{k} P_ {i} (X) \\ Q_ {i} (X) & = {\ frac {Q (X)} {P_ {i} (X)}}. \ End {aligned}}}$

Částečný zlomkový rozklad dává k polynomů se stupni takovými, že ${\ displaystyle 1/Q (X)}$${\ displaystyle S_ {i} (X)}$${\ Displaystyle \ deg S_ {i} (X) <d_ {i},}$

${\ Displaystyle {\ frac {1} {Q (X)}} = \ sum _ {i = 1}^{k} {\ frac {S_ {i} (X)} {P_ {i} (X)} },}$

a tudíž

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

Pak je řešení simultánního kongruenčního systému dáno polynomem

${\ 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)+\ sum _ {j = 1}^{k} (A_ {j} (X) -A_ {i} (X)) S_ {j} (X) Q_ {j} (X) \ ekviv A_ {i} (X) {\ pmod {P_ {i} (X)}},}$

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

Toto řešení může mít stupeň větší než Unikátní řešení stupně menší, než lze odvodit s ohledem na zbývající část euklidovského rozdělení podle Toto řešení je ${\ Displaystyle D = \ sum _ {i = 1}^{k} d_ {i}.}$${\ displaystyle D}$${\ displaystyle B_ {i} (X)}$${\ displaystyle A_ {i} (X) S_ {i} (X)}$${\ displaystyle P_ {i} (X).}$

${\ Displaystyle P (X) = \ sum _ {i = 1}^{k} B_ {i} (X) Q_ {i} (X).}$

Lagrangeova interpolace

Zvláštním případem čínské zbytkové věty pro polynomy je Lagrangeova interpolace . Zvažte proto k monické polynomy prvního stupně:

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

Jsou párové coprime, pokud jsou všechny odlišné. Zbývající část dělení polynomem je${\ displaystyle x_ {i}}$${\ displaystyle P_ {i} (X)}$${\ displaystyle P (X)}$${\ displaystyle P (x_ {i}).}$

Nyní nechť jsou konstanty (polynomy stupně 0) v Lagrangeově interpolaci i čínské větě o zbytku potvrzují existenci jedinečného polynomu stupně menšího než takového, že ${\ displaystyle A_ {1}, \ ldots, A_ {k}}$${\ Displaystyle K.}$${\ displaystyle P (X),}$${\ displaystyle k}$

${\ 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 {aligned}}}$

Parciální zlomky rozklad z IS ${\ displaystyle {\ frac {1} {Q (X)}}}$

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

Ve skutečnosti redukce pravé strany na společného jmenovatele dostane

${\ 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é, protože je to polynom stupně menšího, než který bere hodnotu jedna pro různé hodnoty${\ displaystyle k,}$${\ displaystyle k}$${\ displaystyle X.}$

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

${\ Displaystyle P (X) = \ sum _ {i = 1}^{k} A_ {i} {\ frac {Q_ {i} (X)} {Q_ {i} (x_ {i})}}. }$

Hermitská interpolace

Hermitova interpolace je aplikace čínské zbývající věty pro univariační polynomy, které mohou zahrnovat moduly libovolných stupňů (Lagrangeova interpolace zahrnuje pouze moduly prvního stupně).

Problém spočívá v nalezení polynomu nejmenšího možného stupně, takže polynom a jeho první derivace nabývají daných hodnot v některých pevných bodech.

Přesněji řečeno, nechme být prvky základního pole a, nechme být hodnoty prvních derivací hledaného polynomu na (včetně 0. derivace, což je hodnota samotného polynomu). Problém je najít polynom tak, že jeho j th derivát má hodnotu v pro a${\ displaystyle x_ {1}, \ ldots, x_ {k}}$${\ displaystyle k}$ ${\ displaystyle K,}$${\ Displaystyle i = 1, \ ldots, k,}$${\ Displaystyle a_ {i, 0}, a_ {i, 1}, \ ldots, a_ {i, r_ {i} -1}}$${\ displaystyle r_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle P (X)}$${\ displaystyle a_ {i, j}}$${\ displaystyle x_ {i},}$${\ Displaystyle i = 1, \ ldots, k}$${\ Displaystyle j = 0, \ ldots, r_ {j}.}$

Zvažte polynom

${\ Displaystyle P_ {i} (X) = \ sum _ {j = 0}^{r_ {i} -1} {\ frac {a_ {i, j}} {j!}} (X-x_ {i })^{j}.}$

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

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

Naopak jakýkoli polynom, který splňuje tyto kongruence, zejména ověřuje, pro libovolný${\ displaystyle P (X)}$${\ displaystyle k}$${\ Displaystyle i = 1, \ ldots, k}$

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

proto je jeho Taylorův polynom řádu v , tj. řeší počáteční interpolační problém Hermitů. Čínská věta o zbytku tvrdí, že existuje přesně jeden polynom stupně menšího než součet, který splňuje tyto kongruence. ${\ displaystyle P_ {i} (X)}$${\ displaystyle r_ {i} -1}$${\ displaystyle x_ {i}}$${\ displaystyle P (X)}$${\ displaystyle r_ {i},}$${\ displaystyle k}$

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

Zobecnění na moduly, které nejsou coprime

Čínskou větu o zbytku lze zobecnit na moduly, které nejsou coprime. Nechť jsou libovolná celá čísla, nechme a zvažte systém kongruencí: ${\ Displaystyle m, n, a, b}$${\ Displaystyle g = \ gcd (m, n)}$

${\ Displaystyle {\ begin {aligned} x & \ equiv a {\ pmod {m}} \\ x & \ equiv b {\ pmod {n}}, \ end {aligned}}}$

Pokud , pak tento systém rovnic má jedinečné řešení modulo . V opačném případě nemá řešení. ${\ Displaystyle a \ equiv b {\ pmod {g}}}$${\ displaystyle \ operatorname {lcm} (m, n) = mn/g}$

Pokud k zápisu použijeme Bézoutovu identitu , pak je řešení ${\ displaystyle g = um+vn}$

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

Toto definuje celé číslo, protože g dělí jak m, tak n . Jinak je důkaz velmi podobný tomu pro coprime moduly.

Zobecnění na libovolné prsteny

Čínskou zbytkovou větu lze zobecnit na jakýkoli prsten pomocí coprime ideálů (nazývaných také comaximální ideály ). Dva ideály I a J jsou coprime v případě, že jsou prvky, a tak, že tento vztah hraje roli bézoutova rovnost v dokladech týkajících se tohoto zobecnění, která jsou jinak velmi podobné. Zobecnění může být uvedeno následovně. ${\ displaystyle i \ in I}$${\ Displaystyle j \ v J}$${\ Displaystyle i+j = 1.}$

Nechť I ₁ , ..., I _K být oboustranné ideály kruhu a nechal jsem je jejich průsečík. Pokud jsou ideály párové coprime, máme izomorfismus : ${\ displaystyle R}$

${\ Displaystyle {\ begin {aligned} R/I & \ to R/I_ {1} \ times \ cdots \ times R/I_ {k} \\ x {\ bmod {I}} & \ mapsto (x {\ bmod {I}} _ {1}, \, \ ldots, \, x {\ bmod {I}} _ {k}), \ end {aligned}}}$

mezi faktorokruh a přímý produkt z , kde „ “ označuje obraz prvku v faktorokruh definované ideální Kromě toho, pokud je komutativní , pak ideální průsečík párových coprime ideály je rovna jejich výrobku ; to je ${\ displaystyle R/I}$${\ displaystyle R/I_ {i},}$${\ displaystyle x {\ bmod {I}}}$${\ displaystyle x}$${\ Displaystyle I.}$${\ displaystyle R}$

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

pokud I _i a I _j jsou coprime pro i ≠ j .

Aplikace

Pořadové číslování

Čínská zbývající věta byla použita ke konstrukci Gödelova číslování sekvencí , které se podílí na důkazu Gödelových vět o neúplnosti .

Rychlá Fourierova transformace

Algoritmus prime-faktor FFT (také nazývaný Good-Thomas algoritmus) používá čínské věty o zbytcích pro snížení výpočet rychlá Fourierova transformace velikosti k výpočtu dvou rychlá Fourierova transformace menších velikostí a (za předpokladu, že a jsou coprime). ${\ displaystyle n_ {1} n_ {2}}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$

Šifrování

Většina implementací RSA používá čínskou zbytkovou větu při podepisování certifikátů HTTPS a během dešifrování.

Čínskou větu o zbytku lze také použít při tajném sdílení , které spočívá v distribuci sady akcií mezi skupinu lidí, kteří všichni dohromady (ale nikdo sám) mohou z dané sady akcií získat určité tajemství. Každá z akcií je zastoupena v shodě a řešení systému kongruencí pomocí čínské věty o zbytku je tajemstvím, které je třeba získat zpět. Sdílení tajemství pomocí čínské zbytkové věty využívá spolu s čínskou zbytkovou větou 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

K řešení rozsah dvojznačnost techniky používané při střední frekvenci opakování pulsů radaru může být viděn jako zvláštní případ čínského zbytek věty.

Rozklad spekulací konečných abelianských skupin

Vzhledem k přesvědčení konečných abelianských skupin můžeme použít čínskou zbytkovou větu k poskytnutí úplného popisu jakékoli takové mapy. Za prvé, věta dává izomorfismy${\ Displaystyle \ mathbb {Z} /n \ to \ mathbb {Z} /m}$

${\ Displaystyle {\ begin {aligned} \ mathbb {Z} /n & \ cong \ mathbb {Z} /p_ {n_ {1}}^{a_ {1}} \ times \ cdots \ times \ mathbb {Z} / p_ {n_ {i}}^{a_ {i}} \\\ mathbb {Z} /m & \ cong \ mathbb {Z} /p_ {m_ {1}}^{b_ {1}} \ times \ cdots \ times \ mathbb {Z} /p_ {m_ {j}}^{b_ {i}} \ end {aligned}}}$

kde . Navíc pro jakoukoli indukovanou mapu${\ Displaystyle \ {p_ {m_ {1}}, \ ldots, p_ {m_ {j}} \} \ subseteq \ {p_ {n_ {1}}, \ ldots, p_ {n_ {i}} \}}$

${\ Displaystyle \ mathbb {Z} /p_ {n_ {k}}^{a_ {k}} \ to \ mathbb {Z} /p_ {m_ {l}}^{b_ {l}}}$

z původního přelíčení máme, a protože pro dvojici prvočísel jsou jediná nenulová přelíčení${\ displaystyle a_ {k} \ geq b_ {l}}$${\ displaystyle p_ {n_ {k}} = p_ {m_ {l}}}$${\ displaystyle p, q}$

${\ Displaystyle \ mathbb {Z} /p^{a} \ to \ mathbb {Z} /q^{b}}$

lze definovat, pokud a . ${\ displaystyle p = q}$${\ Displaystyle a \ geq b}$

Všimněte si, že tato pozorování jsou klíčová pro konstrukci prstence profinitivních celých čísel , který je uveden jako inverzní limit všech takových map.

Dedekindova věta

Dedekindova věta o lineární nezávislosti postav. Nechť M být monoidů a K je integrální doménu , zobrazil jako monoidu zvážením násobení na k . Pak je každá konečná rodina (  f _i  ) _{i ∈ I} zřetelných monoidních homomorfismů f _i  : M → k lineárně nezávislá. Jinými slovy, každá rodina ( α _i ) _{i ∈ I} prvků α _i ∈ k uspokojivá  

${\ Displaystyle \ sum _ {i \ in I} \ alpha _ {i} f_ {i} = 0}$

se musí rovnat rodině (0) _{i ∈ I} .

Důkaz. Předpokládejme, že k je pole, v opačném případě nahraďte integrální doménu k jeho kvocientovým polem a nic se nezmění. Můžeme lineárně rozšířit monoidu homomorfismů f _i  : M → k k k algebra homomorfizmy F _i  : K [ M ] → k , kde k [ M ] je monoid kroužek z M nad k . Potom podle linearity podmínka  

${\ Displaystyle \ sum _ {i \ in I} \ alpha _ {i} f_ {i} = 0,}$

výnosy

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

Dále pro i , j ∈ I ; i ≠ j dvě k -lineární mapy F _i  : k [ M ] → k a F _j  : k [ M ] → k nejsou navzájem úměrné. Jinak by f _i a f _j byly také 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 jsou jádra Ker F _i a Ker F _j odlišná. Vzhledem k tomu, K [ M ] / Ker F _i ≅ F _i ( K [ M ]) = k , je pole, Ker F _i je maximální ideál k [ M ] pro každý i ∈ I . Protože jsou zřetelné a maximální, ideály Ker F _i a Ker F _j jsou coprime, kdykoli i ≠ j . Čínská věta o zbytku (pro obecné prsteny) poskytuje izomorfismus:

${\ Displaystyle {\ begin {aligned} \ phi: k [M]/K & \ to \ prod _ {i \ in 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}.}$

V důsledku toho mapa

${\ Displaystyle {\ begin {aligned} \ 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í. Za izomorfismů k [ M ]/Ker F _i → F _i ( k [ M ]) = k , mapa Φ odpovídá:

${\ Displaystyle {\ begin {aligned} \ psi: k [M] & \ to \ prod _ {i \ in I} k \\\ psi (x) & = \ left [F_ {i} (x) \ right ] _ {i \ in I} \ end {aligned}}}$

Nyní,

${\ Displaystyle \ sum _ {i \ in I} \ alpha _ {i} F_ {i} = 0}$

výnosy

${\ Displaystyle \ sum _ {i \ in I} \ alpha _ {i} u_ {i} = 0}$

pro každý vektor ( u _i ) _{i ∈ I} na obrázku mapy ψ . Protože ψ je surjektivní, znamená to, že

${\ Displaystyle \ sum _ {i \ in I} \ alpha _ {i} u_ {i} = 0}$

pro každý vektor

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

V důsledku toho ( α _i ) _{i ∈ I} = (0) _{i ∈ I} . QED.

Viz také

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

Poznámky

Reference

• Dauben, Joseph W. (2007), „Kapitola 3: Čínská matematika“, in Katz, Victor J. (ed.), The Mathematics of Egypt, Mezopotamia, China, India and Islam: A Sourcebook , Princeton University Press, pp. 187–384, ISBN 978-0-691-11485-9
• Dence, Joseph B .; Dence, Thomas P. (1999), Elements of the Theory of Numbers , Academic Press, ISBN 9780122091308
• Duchet, Pierre (1995), „Hypergraphs“, v Graham, RL; Grötschel, M .; Lovász, L. (eds.), Handbook of combinationatorics, Vol. 1, 2 , Amsterdam: Elsevier, s. 381–432, MR  1373663. Viz zejména oddíl 2.5, „Vlastnost Helly“, s. 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četní aspekty algoritmu Aryabhata“ (PDF) , Indian Journal of History of Science , 21 (1): 62–71
• Katz, Victor J. (1998), A History of Mathematics / An Introduction (2nd ed.), 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í historie , Dover, ISBN 978-0-486-65620-5
• Pisano, Leonardo (2002), Fibonacciho Liber Abaci , překlad Sigler, Laurence E., Springer-Verlag, s. 402–403, ISBN 0-387-95419-8
• Rosen, Kenneth H. (1993), The Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0201-57889-8
• Sengupta, Ambar N. (2012), Representing Finite Groups, A A Simimsimple Introduction , Springer, ISBN 978-1-4614-1232-8

Další čtení

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press a McGraw-Hill, ISBN 0-262-03293-7. Viz část 31.5: Čínská věta o zbytku, s. 873–876.
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography , World Scientific Publishing, pp.  1–213 , ISBN 981-02-2827-9
• Hungerford, Thomas W. (1974), Algebra , absolventské texty z matematiky, sv. 73, Springer-Verlag, s. 131–132, ISBN 978-1-4612-6101-8
• Knuth, Donald (1997), The Art of Computer Programming , Volume 2: Seminumerical Algorithms (Third ed.), Addison-Wesley, ISBN 0-201-89684-2 |volume=má další text ( nápověda ). Viz oddíl 4.3.2 (str. 286–291), cvičení 4.6.2–3 (strana 456).

externí odkazy

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