Chińskie twierdzenie o resztach - Chinese remainder theorem

W teorii liczb , na chiński pozostałość twierdzenie , że jeśli zna się resztek euklidesowej podziału wystąpienia całkowitej n o kilka liczb, można wyznaczyć jednoznaczną resztę z dzielenia n produktem z tych liczb, pod warunkiem, że te dzielniki są parami względnie pierwsze .

Najwcześniejsze znane stwierdzenie tego twierdzenia zostało wydane przez chińskiego matematyka Sun-tzu w Sun-tzu Suan-ching w III wieku n.e.

Chińskie twierdzenie o resztach jest szeroko stosowane do obliczeń z dużymi liczbami całkowitymi, ponieważ pozwala zastąpić obliczenia, dla których znamy granicę wielkości wyniku, kilkoma podobnymi obliczeniami na małych liczbach całkowitych.

Chińskie twierdzenie o resztach (wyrażone w kategoriach zgodności ) jest prawdziwe w odniesieniu do każdej głównej idealnej dziedziny . Został uogólniony na dowolny pierścień przemienny , ze sformułowaniem obejmującym ideały .

Historia

Najwcześniejsze znane stwierdzenie twierdzenia, jako problem z konkretnymi liczbami, pojawia się w książce Sun-tzu Suan-ching z III wieku autorstwa chińskiego matematyka Sun-tzu:

Są rzeczy, których liczba jest nieznana. Jeśli policzymy je przez trzy, zostaną nam dwa; piątkami, zostały nam trzy; a przy siódemkach zostają dwa. Ile jest tam rzeczy?

Praca Sun-tzu nie zawiera ani dowodu, ani pełnego algorytmu. To, co jest algorytmem rozwiązania tego problemu, opisał Aryabhata (VI wiek). Szczególne przypadki chińskiego twierdzenia o resztach były również znane Brahmagupta (7 wieku), i pojawiają się w Fibonacciego „s Liber abaci (1202). Wynik został później uogólniony za pomocą kompletnego rozwiązania zwanego Da-yan-shu (大衍術) w Traktacie Matematycznym w Dziewięciu Częściach Ch'in Chiu-shao z 1247 r. (數書九章, Shu-shu Chiu-chang ). przetłumaczony na język angielski na początku XIX wieku przez brytyjskiego misjonarza Alexandra Wylie .

Pojęcie kongruencji zostało po raz pierwszy wprowadzone i użyte przez Gaussa w jego Disquisitiones Arithmeticae z 1801 roku. Gauss ilustruje chińskie twierdzenie o resztach dotyczące problemu związanego z kalendarzami, a mianowicie „znalezienie lat, które mają określoną liczbę okresów w odniesieniu do słońca i księżyca”. cykl i indykacja rzymska”. Gauss wprowadza procedurę rozwiązywania problemu, która była już stosowana przez Eulera, ale w rzeczywistości była to starożytna metoda, która pojawiła się kilka razy.

Oświadczenie

Niech n ₁ , ..., n _k będą liczbami całkowitymi większymi od 1 , które często nazywane są modułami lub dzielnikami . Oznaczmy przez N iloczyn n _i .

Chińskie twierdzenie o resztach twierdzi, że jeśli n _i są parami względnie pierwsze , a jeśli do ₁ , ..., _k są liczbami całkowitymi takimi, że 0 ≤ _i < n _i dla każdego I , to nie jest jedna i tylko jedna liczba całkowita x , takie, że 0 ≤ x < N , a pozostała część euklidesowej Division of x o n _i jest _i dla każdego i .

To może być przekształcone w następujący okres kongruencji : Jeśli n _i są parami względnie pierwsze, a jeśli do ₁ , ..., _k są jakieś całkowitymi, wówczas system

${\ Displaystyle {\ zacząć {wyrównany} x i \ równoważny a_ {1} {\ pmod {n_ {1}}} \ \ & \, \, \, \ vdots \ \ x i \ równoważny a_ {k} {\ pmod { n_{k}}},\end{wyrównany}}}$

ma rozwiązanie, a dowolne dwa rozwiązania, powiedzmy x ₁ i x ₂ , są przystające modulo N , czyli x ₁ ≡ x ₂ (mod N ) .

W algebrze abstrakcyjnej twierdzenie jest często powtarzane jako: jeśli n _i są względnie pierwsze w parach, odwzorowanie

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

definiuje izomorfizm pierścienia

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

między pierścieniem z liczb całkowitych modulo N i bezpośredniego produktu z pierścieni całkowite modulo n _I . Oznacza to, że wykonując sekwencję operacji arytmetycznych w jednym, można wykonać te same obliczenia niezależnie w każdym, a następnie uzyskać wynik stosując izomorfizm (od prawej do lewej). Może to być znacznie szybsze niż obliczenia bezpośrednie, jeśli N i liczba operacji jest duża. Jest to powszechnie stosowane pod nazwą obliczenia wielomodułowe , do algebry liniowej nad liczbami całkowitymi lub liczbami wymiernymi . ${\ Displaystyle \ mathbb {Z} / N \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / n_ {i} \ mathbb {Z}}$

Twierdzenie to można również powtórzyć w języku kombinatoryki jako fakt, że nieskończone ciągi arytmetyczne liczb całkowitych tworzą rodzinę Helly .

Dowód

Istnienie i wyjątkowość rozwiązania można udowodnić samodzielnie. Jednak pierwszy dowód istnienia, podany poniżej, wykorzystuje tę wyjątkowość.

Wyjątkowość

Załóżmy, że x i y są rozwiązaniami wszystkich kongruencji. Ponieważ x i y dają tę samą resztę, po podzieleniu przez n _i , ich różnica x − y jest wielokrotnością każdego n _i . Ponieważ n _i są parami względnie pierwsze, ich iloczyn N dzieli również x − y , a zatem x i y są przystające modulo N . Jeśli x i y mają być nieujemne i mniejsze niż N (jak w pierwszym stwierdzeniu twierdzenia), to ich różnica może być wielokrotnością N tylko wtedy, gdy x = y .

Istnienie (pierwszy dowód)

Mapa

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

odwzorowuje klasy kongruencji modulo N na sekwencje klas kongruencji modulo n _i . Dowód wyjątkowości pokazuje, że mapa ta jest iniektywna . Ponieważ domena i codomain tej mapy mają taką samą liczbę elementów, mapa jest również suriekcją , co dowodzi istnienia rozwiązania.

Ten dowód jest bardzo prosty, ale nie dostarcza żadnego bezpośredniego sposobu obliczania rozwiązania. Co więcej, nie można go uogólnić na inne sytuacje, w których poniższy dowód może.

Istnienie (konstruktywny dowód)

Istnienie można ustalić przez jawną konstrukcję x . Konstrukcję tę można podzielić na dwa etapy, po pierwsze przez rozwiązanie problemu w przypadku dwóch modułów, a drugi przez rozszerzenie tego rozwiązania na przypadek ogólny przez indukcję na liczbie modułów.

Przypadek dwóch modułów

Chcemy rozwiązać system:

${\ Displaystyle {\ zacząć {wyrównane} x i \ równoważne a_ {1} {\ pmod {n_ {1}}} \ \ x i \ równoważne a_ {2} {\ pmod {n_ {2}}}, \ koniec {wyrównane }}}$

gdzie i są względnie pierwsze. ${\displaystyle n_{1}}$${\displaystyle n_{2}}$

Tożsamość Bézouta potwierdza istnienie dwóch liczb całkowitych i takich, że ${\displaystyle m_{1}}$${\displaystyle m_{2}}$

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

Liczby całkowite i mogą być obliczane przez rozszerzony algorytm euklidesowy . ${\displaystyle m_{1}}$${\displaystyle m_{2}}$

Rozwiązanie podaje

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

W rzeczy samej,

${\ Displaystyle {\ zacząć {wyrównany} 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 {wyrównany}}}$

sugerując, że druga zgodność jest udowodniona podobnie, wymieniając indeksy 1 i 2. ${\displaystyle x\equiv a_{1}{\pmod {n_{1}}}.}$

Sprawa ogólna

Rozważ sekwencję równań kongruencji:

${\ Displaystyle {\ zacząć {wyrównany} x i \ równoważny a_ {1} {\ pmod {n_ {1}}} \ \ & \ vdots \ \ x i \ równoważny a_ {k} {\ pmod {n_ {k}}} ,\koniec{wyrównany}}}$

gdzie są parami względnie pierwsze. Dwa pierwsze równania mają rozwiązanie dostarczone metodą z poprzedniej sekcji. Zbiór rozwiązań tych dwóch pierwszych równań jest zbiorem wszystkich rozwiązań równania ${\displaystyle n_{i}}$${\ Displaystyle a_ {1,2}}$

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

Ponieważ inne są względnie pierwsze, sprowadza to rozwiązanie początkowego problemu równań k do podobnego problemu z równaniami. Iterując proces, w końcu otrzymuje się rozwiązania początkowego problemu. ${\displaystyle n_{i}}$${\displaystyle n_{1}n_{2},}$${\ Displaystyle k-1}$

Istnienie (budownictwo bezpośrednie)

Aby skonstruować rozwiązanie, nie jest konieczne wykonanie indukcji na podstawie liczby modułów. Jednak taka bezpośrednia konstrukcja wiąże się z większą liczbą obliczeń przy dużych liczbach, co sprawia, że ​​jest mniej wydajna i mniej używana. Niemniej jednak interpolacja Lagrange'a jest szczególnym przypadkiem tej konstrukcji, stosowaną do wielomianów zamiast liczb całkowitych.

Niech będzie iloczynem wszystkich modułów oprócz jednego. Ponieważ parami są względnie pierwsze i względnie pierwsze. Zatem tożsamość Bézouta ma zastosowanie, a istnieją liczby całkowite i takie, które ${\ 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.}$

Rozwiązaniem systemu kongruencji jest:

${\ Displaystyle x = \ suma _ {i = 1} ^ {k} a_ {i} M_ {i} N_ {i}.}$

W rzeczywistości, podobnie jak wielokrotność dla mamy ${\ Displaystyle N_ {j}}$${\displaystyle n_{i}}$${\displaystyle i\neqj,}$

${\ Displaystyle x \ równoważne a_ {i} M_ {i} N_ {i} \ równoważne a_ {i} (1-m_ {i} n_ {i}) \ równoważne a_ {i} {\ pmod {n_ {i} }},}$

dla każdego ${\displaystyle ja.}$

Obliczenie

Rozważ system kongruencji:

${\ Displaystyle {\ zacząć {wyrównany} x i \ równoważny a_ {1} {\ pmod {n_ {1}}} \ \ & \ vdots \ \ x i \ równoważny a_ {k} {\ pmod {n_ {k}}} ,\\\koniec{wyrównany}}}$

gdzie są parami względnie pierwsze , i niech W tej sekcji opisano kilka metod obliczania unikalnego rozwiązania dla , tak że i te metody są stosowane na przykładzie: ${\displaystyle n_{i}}$${\ Displaystyle N = n_ {1} n_ {2} \ cdots n_ {k}.}$${\displaystyle x}$${\displaystyle 0\leq x<N}$

${\ Displaystyle {\ zacząć {wyrównane} x i \ równoważne 0 {\ pmod {3}} \ \ x i \ równoważne 3 {\ pmod {4}} \ \ x i \ równoważne 4 {\ pmod {5}}. \ koniec { wyrównany}}}$

Wyszukiwanie systematyczne

Jest to łatwe do sprawdzenia, czy wartość x jest rozwiązanie: wystarczy obliczyć resztę euklidesowej Division of X przez każde n _I . Tak więc, aby znaleźć rozwiązanie, wystarczy sprawdzać kolejno liczby całkowite od 0 do N, aż do znalezienia rozwiązania.

Chociaż bardzo prosta, ta metoda jest bardzo nieefektywna. Dla rozważanego tutaj prostego przykładu, aby znaleźć rozwiązanie, należy sprawdzić 40 liczb całkowitych (w tym 0 ), czyli 39 . Jest to algorytm czasu wykładniczego , ponieważ wielkość danych wejściowych jest, do stałego współczynnika, liczbą cyfr N , a średnia liczba operacji jest rzędu N .

Dlatego ta metoda jest rzadko stosowana, ani do obliczeń odręcznych, ani na komputerach.

Szukaj przez przesiewanie

Poszukiwanie rozwiązania można znacznie przyspieszyć przez przesiewanie. W przypadku tej metody zakładamy, bez utraty ogólności, że (gdyby tak nie było, wystarczyłoby zastąpić każdą z pozostałych z dzielenia przez ). Oznacza to, że rozwiązanie należy do ciągu arytmetycznego${\ 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}$

Testując wartości tych liczb modulo można ostatecznie znaleźć rozwiązanie dwóch pierwszych kongruencji. Wtedy rozwiązanie należy do ciągu arytmetycznego ${\displaystyle n_{2},}$${\displaystyle x_{2}}$

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

Testowanie wartości tych liczb modulo i kontynuowanie do momentu, gdy każdy moduł zostanie przetestowany, daje ostatecznie rozwiązanie. ${\displaystyle n_{3},}$

Ta metoda jest szybsza, jeśli moduły zostały uporządkowane według malejącej wartości, czyli jeśli Dla przykładu daje to następujące obliczenie. Rozważamy najpierw liczby, które są przystające do 4 modulo 5 (największy moduł), czyli 4, 9 = 4 + 5 , 14 = 9 + 5 , ... Dla każdej z nich oblicz resztę przez 4 (drugi największy moduł) aż do uzyskania liczby zgodnej z 3 modulo 4. Następnie można przystąpić, dodając w każdym kroku 20 = 5×4 i obliczając tylko reszty przez 3. Daje to ${\displaystyle n_{1}>n_{2}>\cdots>n_{k}.}$

4 mod 4 → 0. Kontynuuj

4 + 5 = 9 mod 4 →1. Kontyntynuj

9 + 5 = 14 mod 4 → 2. Kontynuuj

14 + 5 = 19 mod 4 → 3. OK, kontynuuj, biorąc pod uwagę reszty modulo 3 i dodając za każdym razem 5×4 = 20

19 mod 3 → 1. Kontynuuj

19 + 20 = 39 mod 3 → 0. OK, to jest wynik.

Ta metoda sprawdza się dobrze w przypadku obliczeń odręcznych z iloczynem modułów, który nie jest zbyt duży. Jest jednak znacznie wolniejszy niż inne metody, dla bardzo dużych produktów modułowych. Chociaż jest znacznie szybsza niż wyszukiwanie systematyczne, ta metoda ma również złożoność czasu wykładniczego i dlatego nie jest używana na komputerach.

Korzystanie z konstrukcji istnienia

W konstrukcyjne okna istnienie wynika, że w przypadku dwóch modułów , rozwiązanie może być uzyskane przez obliczenie tych współczynników Bézout z modułów, a następnie przez kilka mnożenia, dodatki i redukcji modulo (dla uzyskania efektu w przedziale ). Ponieważ współczynniki w Bézout mogą być obliczane z rozszerzonego algorytmu Euklidesa , cała obliczeń, co najwyżej, ma kwadratową złożoność czasowa w którym oznacza liczbę cyfr${\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}.}$

Dla więcej niż dwóch modułów, metoda dla dwóch modułów pozwala na zastąpienie dowolnych dwóch kongruencji pojedynczym modułem kongruencji iloczynem modułów. Iteracja tego procesu zapewnia ostatecznie rozwiązanie o złożoności, która jest kwadratowa pod względem liczby cyfr iloczynu wszystkich modułów. Ta kwadratowa złożoność czasu nie zależy od kolejności, w jakiej moduły są przegrupowywane. Można przegrupować dwa pierwsze moduły, a następnie przegrupować wynikowy moduł z następnym i tak dalej. Ta strategia jest najłatwiejsza do wdrożenia, ale wymaga również większej liczby obliczeń z udziałem dużych liczb.

Inna strategia polega na podzieleniu modułów na pary, których iloczyn ma porównywalne rozmiary (w miarę możliwości), przy jednoczesnym zastosowaniu metody dwóch modułów do każdej pary i iteracji z liczbą modułów podzieloną w przybliżeniu przez dwa. Ta metoda pozwala na łatwe zrównoleglenie algorytmu. Ponadto, jeśli do podstawowych operacji wykorzystywane są algorytmy szybkie (czyli algorytmy pracujące w czasie quasilinearnym ), metoda ta dostarcza algorytmu dla całego obliczenia działającego w czasie quasilinearnym.

W obecnym przykładzie (który ma tylko trzy moduły) obie strategie są identyczne i działają w następujący sposób.

Tożsamość Bézout dla 3 i 4 to

${\displaystyle 1\razy 4+(-1)\razy 3=1.}$

Umieszczenie tego we wzorze podanym na udowodnienie istnienia daje

${\displaystyle 0\razy 1\razy 4+3\razy (-1)\razy 3=-9}$

dla rozwiązania dwóch pierwszych kongruencji, pozostałe rozwiązania otrzymuje się przez dodanie do -9 dowolnej wielokrotności 3×4 = 12 . Można kontynuować dowolne z tych rozwiązań, ale rozwiązanie 3 = -9 +12 jest mniejsze (w wartości bezwzględnej) i dlatego prawdopodobnie prowadzi do łatwiejszego obliczenia

Tożsamość Bézout dla 5 i 3×4 = 12 is

${\ Displaystyle 5 \ razy 5 + (-2) \ razy 12 = 1.}$

Stosując ponownie tę samą formułę, otrzymujemy rozwiązanie problemu:

${\ Displaystyle 25 \ razy 3-24 \ razy 4 = 21.}$

Pozostałe rozwiązania otrzymuje się przez dodanie dowolnej wielokrotności 3×4×5 = 60 , a najmniejszym dodatnim rozwiązaniem jest −21 + 60 = 39 .

Jako liniowy system diofantyny

Układ kongruencji rozwiązywany przez chińskie twierdzenie o resztach można przepisać jako układ równoczesnych liniowych równań diofantycznych :

${\ Displaystyle {\ zacząć {wyrównany} x & = a_ {1} + x_ {1} n_ {1} \ \ & \ vdots \ \ x & = a_ {k} + x_ {k} n_ {k}, \ koniec { wyrównany}}}$

gdzie nieznane są liczby całkowite i Dlatego każda ogólna metoda rozwiązywania takich układów może być użyta do znalezienia rozwiązania chińskiego twierdzenia o resztach, takich jak redukcja macierzy układu do postaci normalnej Smitha lub postaci normalnej Hermite'a . Jednak, jak zwykle przy użyciu ogólnego algorytmu dla bardziej szczegółowego problemu, podejście to jest mniej wydajne niż metoda z poprzedniej sekcji, oparta na bezpośrednim użyciu tożsamości Bézouta . ${\displaystyle x}$${\displaystyle x_{i}.}$

Ponad główne idealne domeny

W § Statement , chińskie twierdzenie o resztach zostało sformułowane na trzy różne sposoby: w kategoriach reszt, kongruencji i izomorfizmu pierścienia. Stwierdzenie w kategoriach reszt nie stosuje się na ogół do głównych domen idealnych , ponieważ reszty nie są zdefiniowane w takich pierścieniach. Jednak dwie inne wersje mają sens w odniesieniu do głównej idealnej domeny R : wystarczy zastąpić „liczbę całkowitą” przez „element domeny” i przez R . Te dwie wersje twierdzenia są prawdziwe w tym kontekście, ponieważ dowody (z wyjątkiem pierwszego dowodu istnienia) oparte są na lemie Euklidesa i identyczności Bézout , które są prawdziwe w każdej głównej dziedzinie. ${\ Displaystyle \ mathbb {Z}}$

Jednak ogólnie rzecz biorąc, twierdzenie to jest tylko twierdzeniem o istnieniu i nie zapewnia żadnego sposobu obliczania rozwiązania, chyba że ma się algorytm do obliczania współczynników tożsamości Bézouta.

Nad jednowymiarowymi pierścieniami wielomianowymi i domenami euklidesowymi

Twierdzenie w kategoriach reszt podanych w § Twierdzenie nie może być uogólnione na jakąkolwiek główną dziedzinę idealną, ale jego uogólnienie na dziedziny euklidesowe jest proste. W jednowymiarowe wielomiany nad dziedzinie jest typowym przykładem euklidesowej domeny, która nie jest całkowite. Dlatego stawiamy twierdzenie dla przypadku pierścienia dziedziny jednowymiarowej nad ciałem Aby otrzymać twierdzenie o ogólnej dziedzinie euklidesowej, wystarczy zastąpić stopień funkcją euklidesową dziedziny euklidesowej. ${\ Displaystyle R = K [X]}$${\ Displaystyle K.}$

Chińskie twierdzenie o resztach dla wielomianów jest następujące: Niech (moduły) będą, dla i =1, ..., k , parami względnie pierwszymi wielomianami w . Pozwolić być stopień , a być sumą If są takie, że wielomiany lub dla każdego I , a następnie, jest jeden i tylko jeden wielomian , tak że i reszta euklidesowej podział na przez to dla każdego I . ${\ Displaystyle P_ {i} (X)}$${\ Displaystyle R = K [X]}$${\ Displaystyle d_ {i} = \ stopień 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 \ stopnie A_ {i} <d_ {i}}$${\ Displaystyle P (X)}$${\ Displaystyle \ stopnie P < D}$${\ Displaystyle P (X)}$${\ Displaystyle P_ {i} (X)}$${\ Displaystyle A_ {i} (X)}$

Konstrukcję rozwiązania można wykonać jak w § Istnienie (dowód konstruktywny) lub § Istnienie (dowód bezpośredni) . Jednak ta ostatnia konstrukcja może być uproszczona przez zastosowanie, jak następuje, częściowej dekompozycji na ułamki zamiast rozszerzonego algorytmu euklidesowego .

Zatem chcemy znaleźć wielomian , który spełnia kongruencje ${\ Displaystyle P (X)}$

${\ Displaystyle P (X) \ równoważnik A_ {i} (X) {\ pmod {P_ {i} (X)}}}$

dla ${\displaystyle i=1,\ldots,k.}$

Rozważ wielomiany

${\ Displaystyle {\ zacząć {wyrównany} Q (X) = \ prod _ {i = 1} ^ {k} P_ {i} (X) \ \ Q_ {i} (X) i = {\ Frac {Q (X)}{P_{i}(X)}}.\end{wyrównany}}}$

Rozkład częściowy na ułamki daje k wielomianów o stopniach takich, że ${\ Displaystyle 1/Q (X)}$${\ Displaystyle S_ {i} (X)}$${\ Displaystyle \ stopnie S_ {i} (X) <d_ {i}}$

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

a zatem

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

Wtedy rozwiązanie równoczesnego systemu kongruencji jest podane przez wielomian

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

W rzeczywistości mamy

${\ Displaystyle \ suma _ {i = 1} ^ {k} A_ {i} (X) S_ {i} (X) Q_ {i} (X) = A_ {i} (X) + \ suma _ {j =1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {Szkatułka)}},}$

dla ${\displaystyle 1\leq i\leq k.}$

To rozwiązanie może miećo stopień większy niż Unikalne rozwiązanie stopnia mniejszego niż można wywnioskować biorąc pod uwagę resztę z dzielenia euklidesowego przez To rozwiązanie jest ${\ Displaystyle D = \ suma _ {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) = \ suma _ {i = 1} ^ {k} B_ {i} (X) Q_ {i} (X).}$

Interpolacja Lagrange'a

Szczególnym przypadkiem chińskiego twierdzenia o resztach dla wielomianów jest interpolacja Lagrange'a . W tym celu rozważmy k wielomianów monicznych pierwszego stopnia:

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

Są parami względnie pierwsze, jeśli wszystkie są różne. Pozostała część dzielenia przez wielomian to${\displaystyle x_{i}}$${\ Displaystyle P_ {i} (X)}$${\ Displaystyle P (X)}$${\ Displaystyle P (x_ {i}).}$

Teraz niech będą stałe (wielomiany stopnia 0) zarówno w interpolacji Lagrange'a, jak i chińskim twierdzeniu o resztach zapewniają istnienie unikalnego wielomianu stopnia mniejszego niż taki, że ${\ Displaystyle A_ {1}, \ ldots, A_ {k}}$${\ Displaystyle K.}$${\displaystyle P(X)}$${\displaystyle k}$

${\ Displaystyle P (x_ {i}) = A_ {i}}$

dla każdego ${\displaystyle ja.}$

Wzór na interpolację Lagrange'a jest w tym przypadku wynikiem powyższej konstrukcji rozwiązania. Dokładniej, niech

${\ Displaystyle {\ zacząć {wyrównany} Q (X) i = \ prod _ {i = 1} ^ {k} (X-X_ {i}) \ \ [6 pkt] Q_ {i} (X) i = { \frac {Q(X)}{X-x_{i}}}.\end{wyrównany}}}$

Częściowy rozkład frakcji o Is ${\displaystyle {\frac {1}{Q(X)}}}$

${\ Displaystyle {\ Frac {1} {Q (X)}} = \ suma _ {i = 1} ^ {k} {\ Frac {1} {Q_ {i} (x_ {i}) (X-X_ {i})}}.}$

W rzeczywistości sprowadzając prawą stronę do wspólnego mianownika, który otrzymujemy

${\ Displaystyle \ suma _ {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 licznik jest równy jeden, jako wielomian stopnia mniejszego, który przyjmuje wartość jeden dla różnych wartości${\displaystyle k}$${\displaystyle k}$${\ Displaystyle X.}$

Korzystając z powyższego wzoru ogólnego otrzymujemy wzór na interpolację Lagrange'a:

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

Interpolacja hermita

Interpolacja Hermite'a jest zastosowaniem chińskiego twierdzenia o resztach dla jednowymiarowych wielomianów, które mogą obejmować moduły dowolnych stopni (interpolacja Lagrange'a obejmuje tylko moduły pierwszego stopnia).

Problem polega na znalezieniu wielomianu najmniejszego możliwego stopnia, tak aby wielomian i jego pierwsze pochodne przybrały dane wartości w pewnych ustalonych punktach.

Dokładniej, niech będzie elementy gruntu pola i przez niech będzie wartości pierwszych pochodnych poszukiwanych w wielomian (w tym 0th pochodnej, która jest wartością wielomianu siebie). Problemem jest znalezienie wielomian tak, że jego j th pochodnej przyjmuje wartość w za i${\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}.}$

Rozważ wielomian

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

Jest to wielomian Taylora rzędu w , nieznanego wielomianu Dlatego musimy mieć ${\ Displaystyle r_ {i}-1}$${\displaystyle x_{i}}$${\ Displaystyle P (X).}$

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

I odwrotnie, każdy wielomian, który spełnia te kongruencje, w szczególności weryfikuje dla dowolnego${\ Displaystyle P (X)}$${\displaystyle k}$${\displaystyle i=1,\ldots,k}$

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

dlatego jest jego wielomianem Taylora rzędu w , czyli rozwiązuje początkowy problem interpolacji Hermite'a. Chińskie twierdzenie o resztach twierdzi, że istnieje dokładnie jeden wielomian stopnia mniejszy niż suma, który spełnia te kongruencje. ${\ Displaystyle P_ {i} (X)}$${\ Displaystyle r_ {i}-1}$${\displaystyle x_{i}}$${\ Displaystyle P (X)}$${\displaystyle r_{i},}$${\displaystyle k}$

Istnieje kilka sposobów obliczania rozwiązania. Można użyć metody opisanej na początku § Nad jednowymiarowymi pierścieniami wielomianowymi i domenami euklidesowymi . Można również użyć konstrukcji podanych w § Istnienie (dowód konstruktywny) lub § Istnienie (dowód bezpośredni) . ${\ Displaystyle P (X).}$

Uogólnienie na moduły non-coprime

Chińskie twierdzenie o resztach można uogólnić na moduły inne niż względnie pierwsze. Niech będą liczbami całkowitymi, niech , i rozważmy system kongruencji: ${\displaystyle m,n,a,b}$${\ Displaystyle g = \ gcd (m, n)}$

${\ Displaystyle {\ zacząć {wyrównane} x i \ równoważne a {\ pmod {m}} \ \ x i \ równoważne b {\ pmod {n}}, \ koniec {wyrównane}}}$

Jeśli , to ten układ równań ma unikalne rozwiązanie modulo . W przeciwnym razie nie ma rozwiązań. ${\displaystyle a\equivb{\pmod {g}}}$${\ Displaystyle \ Operatorname {lcm} (m, n) = mn / g}$

Jeśli użyjemy tożsamości Bézout do pisania , to rozwiązaniem jest ${\displaystyle g=um+vn}$

${\ Displaystyle x = {\ Frac {avn + bum} {g}}.}$

Definiuje to liczbę całkowitą, ponieważ g dzieli zarówno m, jak i n . W przeciwnym razie dowód jest bardzo podobny do tego dla modułów względnie pierwszych.

Uogólnienie na dowolne pierścienie

Chińskie twierdzenie o resztach można uogólnić na dowolny pierścień , używając ideałów względnie pierwszych (zwanych także ideałami komaksymalnymi ). Dwa ideały I i J są względnie pierwsze, jeśli istnieją elementy i takie, że Ta relacja odgrywa rolę tożsamości Bézout w dowodach związanych z tym uogólnieniem, które poza tym są bardzo podobne. Uogólnienie można przedstawić następująco. ${\displaystyle ja\w ja}$${\ Displaystyle j \ w J}$${\displaystyle i+j=1.}$

Niech I ₁ , ..., I _k będą dwustronnymi ideałami pierścienia i niech ja będę ich przecięciem. Jeśli ideały są względnie pierwsze parami, mamy izomorfizm : ${\ Displaystyle R}$

${\ Displaystyle {\ zacząć {wyrównany} R / I i \ do R / I_ {1} \ razy \ cdots \ razy R / I_ {k} \ \ x {\ bmod {I}} i \ mapsto (x {\ bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{wyrównany}}}$

między pierścieniem iloraz i bezpośredni produkt z którym „ ” oznacza obraz elementu w pierścieniu iloraz określonej przez idealny Ponadto, jeśli jest przemienne , wówczas idealnym przecięcia par idei względnie pierwsze równa jest produkt ; to jest ${\ Displaystyle R/I}$${\ Displaystyle R/I_ {i},}$${\displaystyle x{\bmod {ja}}}$${\displaystyle x}$${\ Displaystyle I.}$${\ Displaystyle R}$

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

jeśli ja _mam i ja _j są względnie pierwsze dla í ≠ j .

Aplikacje

Numeracja sekwencyjna

Chińskie twierdzenie o resztach zostało użyte do skonstruowania numeracji Gödla dla sekwencji , która jest zaangażowana w dowód twierdzenia o niezupełności Gödla .

Szybka transformata Fouriera

Algorytm FFT prime-factor (zwany także algorytm Good-Thomas) wykorzystuje chińską twierdzenie pozostałą zmniejszania obliczenia wyniku szybkiej transformaty Fouriera wielkości do wyliczenia dwóch Szybka transformacja Fouriera mniejszych rozmiarach i (pod warunkiem, że i są względnie pierwsze). ${\displaystyle n_{1}n_{2}}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$

Szyfrowanie

Większość implementacji RSA używa chińskiego twierdzenia o resztach podczas podpisywania certyfikatów HTTPS i podczas deszyfrowania.

Chińskie twierdzenie o resztach może być również wykorzystywane w udostępnianiu sekretów , które polega na rozdysponowaniu zbioru udziałów wśród grupy ludzi, którzy wszyscy razem (ale nikt w pojedynkę) może odzyskać pewien sekret z danego zestawu udziałów. Każda z udziałów jest reprezentowana w kongruencji, a tajemnicą do odzyskania jest rozwiązanie systemu kongruencji przy użyciu chińskiego twierdzenia o resztach. Udostępnianie sekretu przy użyciu chińskiego twierdzenia o resztach wykorzystuje, wraz z chińskim twierdzeniem o resztach, specjalne sekwencje liczb całkowitych, które gwarantują niemożność odzyskania sekretu ze zbioru udziałów o mniejszej niż pewna kardynalność .

Rozdzielczość niejednoznaczności zakresu

Że rozkład zakres niejednoznaczności techniki stosowane przy średniej częstotliwości powtarzania impulsów radaru mogą być postrzegane jako szczególny przypadek chińskiego twierdzenia resztę.

Dekompozycja surjekcji skończonych grup abelowych

Mając przypuszczenie skończonych grup abelowych , możemy użyć chińskiego twierdzenia o resztach, aby podać pełny opis takiej mapy. Przede wszystkim twierdzenie daje izomorfizmy${\ Displaystyle \ mathbb {Z} / n \ do \ mathbb {Z} / m}$

${\ Displaystyle {\ zacząć {wyrównany} \ mathbb {Z} / n & \ cong \ mathbb {Z} / p_ {n_ {1}} ^ {a_ {1}} \ razy \ cdots \ razy \ mathbb {Z} / p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \ razy \mathbb {Z} /p_{m_{j}}^{b_{i}}\end{wyrównany}}}$

gdzie . Ponadto dla dowolnej mapy indukowanej${\ Displaystyle \ {p_ {m_ {1}}, \ ldots, p_ {m_ {j}} \} \ subseteq \ {p_ {n_ {1}}, \ ldots, p_ {n_ {i}} \}}$

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

z oryginalnej surjekcji mamy i , ponieważ dla pary liczb pierwszych , jedyne niezerowe surjekcje${\ Displaystyle a_ {k} \ geq b_ {l}}$${\ Displaystyle p_ {n_ {k}} = p_ {m_ {l}}}$${\displaystyle p,q}$

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

można zdefiniować, jeśli i . ${\displaystyle p=q}$${\displaystyle a\geq b}$

Zauważ, że te obserwacje mają kluczowe znaczenie dla skonstruowania pierścienia liczb całkowitych nieskończonych , który jest podany jako odwrotna granica wszystkich takich map.

Twierdzenie Dedekinda

Twierdzenie Dedekinda o liniowej niezależności postaci. Niech M będzie monoid a k jest integralną domenę , widzianego jako monoid rozważając mnożenia na k . Następnie każdy skończonej rodziny (  f _I  ) _{i ∈ I} odrębnych homomorfizmów monoid f _I  : M → K jest liniowo niezależne. Innymi słowy, każda rodzina ( α _i ) _{i ∈ I} elementów α _i ∈ k spełniających  

${\ Displaystyle \ suma _ {i \ w I} \ alfa _ {i} f_ {i} = 0}$

musi być równa rodzinie (0) _{i ∈ I} .

Dowód. Najpierw załóżmy, że k jest polem, w przeciwnym razie zastąp domenę całkową k jej polem ilorazu i nic się nie zmieni. Można liniowe rozszerzenie Homomorfizmy monoid f _I  : M → K do K -algebra homomorfizmy M _i  : k [ M ] → K , gdzie K [ M ] jest pierścień monoid z M na k . Następnie, przez liniowość, warunek  

${\ Displaystyle \ suma _ {i \ w I} \ alfa _ {i} f_ {i} = 0,}$

plony

${\ Displaystyle \ suma _ {i \ w I} \ alfa _ {i} F_ {i} = 0.}$

Następnie dla i , j ∈ I ; i ≠ j dwa k- liniowe odwzorowania F _i  : k [ M ] → k oraz F _j  : k [ M ] → k nie są do siebie proporcjonalne. Inaczej C _I i f _j będzie proporcjonalna, a więc jest równa od jako monoid homomorfizmów spełniają: f _I  (1) = 1 =   F _j  (1) , co jest sprzeczne z założenia, że są one różne.      

Dlatego jądrach Ker F _I i Ker F _j są różne. Od k [ M ] / Ker F _i ≅ K _I ( k [ M ]) = K jest pole, Ker C _i jest maksymalna ideał k [ M ] dla każdej I ∈ I . Ponieważ są one różne i najdłuższej, ideał Ker F _I i Ker F _J jest względnie pierwsze, gdy i ≠ j . Chińskie twierdzenie o resztach (dla ogólnych pierścieni) daje izomorfizm:

${\ Displaystyle {\ zacząć {wyrównany} \ phi : k [M] / K i \ do \ prod _ {i \ w ja} k [M] / \ operatorname {Ker} F_ {i} \ \ \ phi (x + K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{wyrównany}}}$

gdzie

${\ Displaystyle K = \ prod _ {i \ w ja} \ operatorname {Ker} F_ {i} = \ bigcap _ {i \ w ja} \ operatorname {Ker} F_ {i}.}$

W związku z tym mapa

${\ Displaystyle {\ zacząć {wyrównany} \ Phi: k [M] i \ do \ prod _ {i \ w ja} k [M] / \ operatorname {Ker} F_ {i} \ \ \ Phi (x) i =\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{wyrównany}}}$

jest suriektywna. Pod isomorphisms k [ M ] / Ker C _i → F _ı ( K [ M ]) = k , MAPIE cp odpowiada:

${\ Displaystyle {\ zacząć {wyrównany} \ psi: k [M] i \ do \ prod _ {i \ w ja} k \ \ \ psi (x) i = \ lewo [F_ {i} (x) \ prawo ]_{i\w I}\end{wyrównany}}}$

Ale już,

${\ Displaystyle \ suma _ {i \ w I} \ alfa _ {i} F_ {i} = 0}$

plony

${\ Displaystyle \ suma _ {i \ w I} \ alfa _ {i} u_ {i} = 0}$

dla każdego wektora ( u _i ) _{i ∈ I} w obrazie mapy ψ . Ponieważ ψ jest suriektywna, oznacza to, że

${\ Displaystyle \ suma _ {i \ w I} \ alfa _ {i} u_ {i} = 0}$

dla każdego wektora

${\ Displaystyle \ lewo (u_ {i} \ prawo) _ {i \ w I} \ w \ prod _ {i \ w I} k.}$

W konsekwencji ( α _i ) _{i ∈ I} = (0) _{i ∈ I} . CO BYŁO DO OKAZANIA.

Zobacz też

• System zakrywający
• Zasada Hassego
• System numerów rezydualnych

Uwagi

Bibliografia

• Dauben, Joseph W. (2007), „Rozdział 3: Matematyka chińska”, w Katz, Victor J. (red.), Matematyka Egiptu, Mezopotamii, Chin, Indii i islamu: podręcznik źródłowy , Princeton University Press, s. 187-384, ISBN 978-0-691-11485-9
• Dence, Józef B.; Dence, Thomas P. (1999), Elementy teorii liczb , Academic Press, ISBN 9780122091308
• Duchet, Pierre (1995), „Hipergrafy”, w Graham, RL; Grötschel, M .; Lovász, L. (red.), Podręcznik kombinatoryki, t. 1, 2 , Amsterdam: Elsevier, s. 381-432, MR  1373663. Patrz w szczególności sekcja 2.5, „Właściwość Helly”, s. 393–394 .
• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae , przekład Clarke, Arthur A. (druga, poprawiona red.), New York: Springer , ISBN 978-0-387-96254-2
• Irlandia, Kenneth; Rosen, Michael (1990), klasyczne wprowadzenie do nowoczesnej teorii liczb (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X
• Kak, Subhash (1986), „Aspekty obliczeniowe algorytmu Aryabhata” (PDF) , Indian Journal of History of Science , 21 (1): 62-71
• Katz, Victor J. (1998), Historia matematyki / Wprowadzenie (2nd ed.), Addison Wesley Longman, ISBN 978-0-321-01618-8
• Libbrecht Ulrich (1973), Matematyka chińska w XIII wieku: „Shu-shu Chiu-chang” Ch'in Chiu-shao , Dover Publications Inc, ISBN 978-0-486-44619-6
• Ore, Oystein (1988) [1948], Teoria liczb i jej historia , Dover, ISBN 978-0-486-65620-5
• Pisano, Leonardo (2002), Liber Abaci Fibonacciego , przekład Sigler, Laurence E., Springer-Verlag, s. 402-403, ISBN 0-387-95419-8
• Rosen, Kenneth H. (1993), Elementarna teoria liczb i jej zastosowania (3rd ed.), Addison-Wesley, ISBN 978-0201-57889-8
• Sengupta, Ambar N. (2012), Reprezentowanie grup skończonych, A Semimsimple Introduction , Springer, ISBN 978-1-4614-1232-8

Dalsza lektura

• Cormen, Thomas H .; Leiserson, Charles E. ; Rivest, Ronald L .; Stein, Clifford (2001), Wprowadzenie do algorytmów (druga red.), MIT Press i McGraw-Hill, ISBN 0-262-03293-7. Patrz Sekcja 31.5: Chińskie twierdzenie o resztach, s. 873–876.
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), chińskie twierdzenie o pozostałościach. Zastosowania w informatyce, kodowaniu, kryptografii , World Scientific Publishing, s.  1-213 , ISBN 981-02-2827-9
• Hungerford, Thomas W. (1974), Algebra , Graduate Texts in Mathematics, tom. 73, Springer-Verlag, s. 131–132, ISBN 978-1-4612-6101-8
• Knuth, Donald (1997), The Art of Computer Programming , Tom 2: Algorytmy półnumeryczne (wyd. trzecie.), Addison-Wesley, ISBN 0-201-89684-2 |volume=ma dodatkowy tekst ( pomoc ). Patrz sekcja 4.3.2 (str. 286–291), ćwiczenie 4.6.2–3 (str. 456).

Zewnętrzne linki

• "Chińskie twierdzenie o resztach" , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Chińskie twierdzenie o reszcie” . MatematykaŚwiat .
• Chińskie twierdzenie o resztach w PlanetMath .
• Pełny tekst Sun-tzu Suan-ching (chiński) – chiński projekt tekstowy