Kínai maradéktétel

A kínai maradéktétel a több kongruenciából álló szimultán kongruenciarendszerek megoldhatóságára ad választ. Már több mint 2000 évvel ezelőtt ismerte egy kínai matematikus, Szun Cu; innen a tétel mai neve.

A tétel tulajdonképpen a következő feladatra ad választ (továbbá kimondja, hogy a megoldás egyértelmű maradékosztály): keressük azt az egész számot (maradékosztályt), ami bizonyos számokkal osztva, amelyek páronként relatív prímek, meghatározott maradékot ad.

A következőkben a tétel formális kimondása és bizonyítása található.

Tétel

Legyenek $m_{1},m_{2},\dots ,m_{k}>0$ páronként relatív prímek, $c_{1},c_{2},\dots ,c_{k}$ pedig tetszőleges egészek. Ekkor az

$${\begin{aligned}x&\equiv c_{1}{\pmod {m_{1}}}\\x&\equiv c_{2}{\pmod {m_{2}}}\\\vdots \\x&\equiv c_{k}{\pmod {m_{k}}}\end{aligned}}$$

kongruencia-rendszer megoldható, és a megoldás egyetlen maradékosztály lesz $\mod {M}$, ahol $M=m_{1}\cdot m_{2}\dots m_{k}$.

Bizonyítás

A megoldás egyértelműsége

Tegyük fel, hogy $\ x_{1}$ és $\ x_{2}$ is megoldások. Ekkor minden $i=0,1,\dots ,k$ esetén $m_{i}\mid x_{1}-x_{2}\Rightarrow M\mid x_{1}-x_{2}$ (mivel $\ m_{i}$-k relatív prímek), amiből a kongruenciák definíciója alapján következik, hogy $x_{1}\equiv x_{2}{\pmod {M}}$. Tehát $\ x_{1}$ és $\ x_{2}$ (azaz bármely két megoldás) ugyanabba a maradékosztályba tartoznak $\mod {M}$, így csak egy megoldó maradékosztálya van a kongruencia-rendszernek.

A megoldás létezése

Legyen $M=m_{1}\cdot m_{2}\dots m_{k}$ és $M_{i}={\frac {M}{m_{i}}}$. Legyen $z_{i}\in \mathbb {Z}$ olyan, hogy $M_{i}z_{i}\equiv 1{\pmod {m_{i}}}$. A megoldások számára vonatkozó tétel alapján ilyen$\ z_{i}$ létezik, mert $\ (M_{i},m_{i})=1$. Az $s=M_{1}z_{1}c_{1}+M_{2}z_{2}c_{2}+\dots +M_{k}z_{k}c_{k}$ jó megoldás lesz. Ennek bizonyításához nézzük meg, hogy $s\equiv c_{i}{\pmod {m_{i}}}$ valóban teljesül-e ($i=0,1,\dots ,k$). A kongruencia ekvivalens $s\equiv M_{i}z_{i}c_{i}{\pmod {m_{i}}}$ kongruenciával, mert $\ m_{i}\mid M_{j}$, ha $i\neq j$. Mivel $M_{i}z_{i}\equiv 1{\pmod {m_{i}}}$, ezért $s\equiv c_{i}{\pmod {m_{i}}}$ áll fenn, ami épp a bizonyítandó állítás.

Alkalmazásai

A kínai maradéktételt meglepő módon rengeteg helyen lehet használni, sok problémánál pedig nem is kapható meg nélküle az eredmény.

Polinom helyettesítési értéke

Tegyük fel, hogy ki szeretnénk számolni egy $f(x_{1},x_{2},\dots ,x_{n})$ egész együtthatós többváltozós polinom helyettesítési értékét adott $(x_{1},x_{2},\dots ,x_{n})=(a_{1},a_{2},\dots ,a_{n})$ helyen, és ismerjük, hogy $|f(a_{1},a_{2},\dots ,a_{n})|<{\frac {M}{2}}$ teljesül. Ekkor válasszunk olyan $m_{1},m_{2},\dots ,m_{k}$ egymáshoz relatív prím egészeket (praktikusan prímszámokat szokás) a kínai maradéktételhez, amelyekre: $m_{1}m_{2}\dots m_{k}<M$ teljesül, majd számoljuk ki a polinom helyettesítési értékeit minden $i$-re ${\pmod {m_{i}}}$, legyen az eredmény $c_{i}$, majd a kínai maradéktételt használva azt az egyértelmű $x$ egész számot, amelyre $-{\frac {M}{2}}\leq x<{\frac {M}{2}}$ és

$${\begin{aligned}x&\equiv c_{1}{\pmod {m_{1}}}\\x&\equiv c_{2}{\pmod {m_{2}}}\\\vdots \\x&\equiv c_{k}{\pmod {m_{k}}}\end{aligned}}$$

teljesül. Ekkor $f(a_{1},a_{2},\dots ,a_{n})=x$ lesz.

Így nagy számokkal való műveleteket nem kell végezni, csak amikor az eljárás elején redukáljuk a polinom együtthatóit ${\pmod {m_{i}}}$, illetve a végén, amikor megoldjuk a kongruenciarendszert. Ezáltal lényegesen kevesebb memóriát használva ki tudjuk számítani a végeredményt.

Rejtjelezés

Az RSA legtöbb implementációja a kínai maradéktételt használja a HTTPS hitelesítésre és a visszafejtésre.

A tétel használható a titokmegosztásra, amivel úgy lehet titkot megosztani, hogy csak néhányan közösen tudjanak hozzáférni. Az érzékeny adat egy kongruenciarendszer megoldása, amiből minden résztvevő egy egyenletet ismer. Van arra is algoritmus, hogy megkonstruálja a modulusokat, hogy a kívánt számnál kevesebb ember együtt ne férhessen hozzá a titokhoz.

Hermite-interpoláció

Az általános Hermite-interpoláció: Adva vannak a $\lambda _{1},\dots ,\lambda _{r}$ komplex pontok, és hozzájuk rendre az $a_{j,k}:\ 1\leq j\leq r,\ 0\leq k<\nu _{j}$ értékek. Keressünk egy $P(x)\in \mathbb {C} [x]$ polinomot úgy, hogy:

$P^{(k)}(\lambda _{j})=a_{j,k}\qquad 1\leq j\leq r,\quad 0\leq k<\nu _{j}.$

A megoldás: Vezessük be az

$A_{j}(x):=\sum _{k=0}^{\nu _{j}-1}{\frac {a_{j,k}}{k!}}(x-\lambda _{j})^{k}$

polinomokat, így a rendszer szimultán kongruenciákra írható át:

$P(x)\equiv A_{j}(x){\pmod {(x-\lambda _{j})^{\nu _{j}}}},\qquad 1\leq j\leq r$

A kínai maradéktétel szerint $\mathbb {C} [x]$-ben van egy egyértelmű $P(x)$ polinom, hogy:

$\deg(P)<n:=\sum _{j}\nu _{j}.$

A közvetlen konstrukció így valósítható meg: Definiáljuk a

${\begin{aligned}Q&=\prod _{i=1}^{r}(x-\lambda _{i})^{\nu _{i}}\\Q_{j}&={\frac {Q}{(x-\lambda _{j})^{\nu _{j}}}}\end{aligned}}$

polinomokat. Ekkor ${\frac {1}{Q}}$ törtfelbontása $r$ polinomot ad, a továbbiakban ezeket $S_{j}$ jelöli, és fokszámuk $\deg(S_{j})<\nu _{j}$. Ezzel

${\frac {1}{Q}}=\sum _{i=1}^{r}{\frac {S_{i}}{(x-\lambda _{i})^{\nu _{i}}}}$

így

$1=\sum _{i=1}^{r}S_{i}Q_{i}.$

Tehát a kongruenciarendszer megoldása

$\sum _{i=1}^{r}A_{i}S_{i}Q_{i}=A_{j}+\sum _{i=1}^{r}(A_{i}-A_{j})S_{i}Q_{i}\equiv A_{j}{\pmod {(x-\lambda _{j})^{\nu _{j}}}}\qquad 1\leq j\leq r,$

ami az egyértelmű $n$-nél kisebb fokú polinom.

Dedekind-tétel

Dedekind tétele a lineárisan független karakterekről: Legyen $M$ monoid, $k$ integritási tartomány, amit szintén monoidnak tekintünk a rajta vett szorzással. Ekkor minden véges $(f_{i})_{i\in I}$ egyenként különböző monoidhomomorfia független, ahol minden $f_{i}:\ M\rightarrow k$. Más szavakkal, $(\alpha _{i}){}_{i\in I}$ elemek minden családja, ahol $\alpha _{i}\in k$ és $\sum _{i\in I}\alpha _{i}f_{i}=0$, ugyanaz, mint $(0){}_{i\in I}$.

Bizonyítás: Először is tegyük fel, hogy $k$ test; ha nem az, helyettesítsük hányadostestével, és semmi sem változik. Lineárisan kiterjesztjük az $f_{i}:\ M\rightarrow k$ homomorfiákat $k$-algebra homomorfiákká, ahol $k[M]$ $M$ monoid gyűrűje $k$ fölött. Ekkor a linearitás miatt a

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

feltételből következik

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

Állítjuk, hogy az $i,j\in I;\ i\neq j$ indexekre $F_{i}:\ k[M]\rightarrow k$ és $F_{j}:\ k[M]\rightarrow k$ nem arányosak egymáshoz. Különben $f_{i}$ és $f_{j}$ is arányos lenne, így monoid homomorfiaként egyenlőek lennének, emiatt $f_{i}(1)=1=f_{j}$, ami ellentmond annak, hogy különböznek.

Ezért a $\operatorname {Ker} F_{i}$ és $\operatorname {Ker} F_{j}$ magok különböznek. Mivel $k[M]/\operatorname {Ker} F_{i}\cong F_{i}(k[M])=k$ test, $\operatorname {Ker} F_{i}$ maximális ideálja $k[M]$-nek, minden $i\in I$ indexre. Mivel ezek különbözők és maximálisak, ezért relatív prímek egymáshoz. A kínai maradéktétel a következő izomorfiát adja:

${\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\operatorname {Ker} F_{i}\\\phi (x+K)&=\left(x+\operatorname {Ker} F_{i}\right)_{i\in I}\end{aligned}}$

ahol

$K=\prod _{i\in I}\operatorname {Ker} F_{i}=\bigcap _{i\in I}\operatorname {Ker} F_{i}.$

Következik, hogy a

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

leképezés szürjektív. A $k[M]/\operatorname {Ker} F_{i}\rightarrow F_{i}(k[M])=k$, izomorfiákkal a $\Phi$ leképezés megfelel ennek:

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

Most abból, hogy

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

kapjuk, hogy:

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

minden $(u_{i}){}_{i\in I}$ vektorra a $\psi$ leképezés szerinti képben. Mivel $\psi$ szürjektív, ez azt jelenti, hogy

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

minden

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

vektorra. Tehát $(\alpha _{i}){}_{i\in I}=(0){}_{i\in I}$.

Más alkalmazások

Egész elemű mátrixok determinánsának kiszámolása klasszikus példa az alkalmazására, illetve a gyors szorzás FFT módszerénél is gyakran felbukkan, ott a számítógép felépítése miatt $2$ hatványhoz közeli prímeket célszerű választani a módszer gyorsításához. Az algoritmus a tétel alapján újraindexeli az adatokat. Gödel nemteljességi tételéhez a sorozatok számozását is elegánsan lehet megoldani a kínai maradéktétellel.

A módszer kiterjeszthető arra az esetre is, amikor osztani is kell egy feladatban. Ekkor persze problémák adódhatnak, hiszen előfordulhat, hogy $0$-val osztani is kell (legyen most $m_{i}$ prím), ha az adott szám osztható $m_{i}$-vel, ez pedig ${\pmod {m_{i}}}$ nem elvégezhető művelet. Ilyenkor dobjuk el az $m_{i}$ prímet és válasszunk helyette egy másikat. Így például már egész elemű lineáris egyenletrendszerek is megoldhatóak a kínai maradéktétellel, kevés memóriával (illetve felszorzás miatt racionális elemű lineáris egyenletrendszerek is).

A radarral végzett felméréseknél a tartományfelosztás egyértelműsítésére is használják.

A megoldás menete

Mivel minden $i$-re az $m_{i}$ számok és $M_{i}:=M/m_{i}$ relatív prímek, azért a kiterjesztett euklideszi algoritmussal találhatók $r_{i}$ és $s_{i}$ számok, hogy

$r_{i}\cdot m_{i}+s_{i}\cdot M_{i}=1$.

Végezzük el az $e_{i}:=s_{i}\cdot M_{i}$ helyettesítést, ezzel

${\begin{aligned}e_{i}&\equiv 1{\pmod {m_{i}}}\\e_{j}&\equiv 0{\pmod {m_{j}}},\ j\neq i.\end{aligned}}$.

Ekkor

$x:=\sum _{i=1}^{n}a_{i}e_{i}$

a szimultán kongruencia egy megoldása.

Példa

Keresünk egy $x$ egész számot, amire teljesülnek a következők:

${\begin{aligned}x&\equiv 2{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 2{\pmod {5}}\\\end{aligned}}$

Itt $M=3\cdot 4\cdot 5=60,\ M_{1}=M/3=20,\ M_{2}=M/4=15,\ M_{3}=M/5=12$. A kibővített euklideszi algoritmussal kiszámítható, hogy

$7\cdot 3+(-1)\cdot 20=1$, tehát $e_{1}=-20$

$4\cdot 4+(-1)\cdot 15=1$, tehát $e_{2}=-15$

$5\cdot 5+(-2)\cdot 12=1$, tehát $e_{3}=-24$

Eszerint $x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133$ az egyenletrendszer egy megoldása. Mivel $-133\equiv 47\mod 60$, azért az összes megoldás kongruens 47-tel modulo 60.

Általános eset

Általános esetben nem tesszük fel, hogy a modulusok relatív prímek. Néha még így is létezik megoldás, de a modulusok szorzata helyett a legkisebb közös többszöröst kell venni. A létezés feltétele: Minden $i\neq j$ párra

$a_{i}\equiv a_{j}{\pmod {\operatorname {lnko} (m_{i},m_{j})}}$.

Ekkor a szimultán kongruencia szukcesszív helyettesítéssel oldható meg.

Például egy klasszikus feladat megkeresni azt a legkisebb pozitív egész számot, ami a 2, 3, 4, 5 és 6 számokkal osztva egyet ad maradékul, de osztható héttel. Tehát keressük ennek az egyenletrendszernek a megoldását:

${\begin{aligned}x&\equiv 1\mod 2\\x&\equiv 1\mod 3\\x&\equiv 1\mod 4\\x&\equiv 1\mod 5\\x&\equiv 1\mod 6\\x&\equiv 0\mod 7\\\end{aligned}}$

Mivel a modulusok nem relatív prímek, azért nem alkalmazható közvetlenül a kínai maradéktétel. Az első öt feltételt összefoglalhatjuk a következőbe:

$x\equiv 1\mod \operatorname {lkkt} (2,3,4,5,6)$

így az egyenletrendszer a következő alakra hozható:

${\begin{aligned}x&\equiv 1\mod 60\\x&\equiv 0\mod 7\\\end{aligned}}$

amire már alkalmazható a kínai maradéktétel. A megoldások kongruensek 301-gyel modulo 420. Ezek közül a legkisebb pozitív egész a 301.

Közvetlen megoldás

Adva legyen a következő két kongruenciából álló rendszer:

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

Ha ezek megoldhatók, akkor $a\equiv b{\pmod {d}}$, ezért ekvivalensek az

$x\equiv a-yn{\frac {a-b}{d}}{\pmod {\frac {nm}{d}}}$

kongruenciával, ahol

$d=\operatorname {lnko} (n,m)=yn+zm$.

Ez akkor is működik, ha $n$ és $m$ nem relatív prímek, így nagyban megkönnyíti a szimultán kongruenciák megoldását.

Ha több kongruencia tartozik a rendszerhez, akkor többször kell alkalmazni az egyszerűsítést.

Főideálgyűrűkben

Ha $R$ főideálgyűrű, akkor a tétel a következő formát ölti:

Ha az $m_{1},\ldots ,m_{n}$ elemek páronként relatív prímek, és szorzatuk $m$, akkor az $R/mR$ hányadosgyűrű izomorf az $R/m_{1}R\times \cdots \times R/m_{n}R$ szorzatgyűrűvel, mégpedig az alábbi izomorfia van köztük:

${\begin{matrix}f:&R/mR&\to &R/m_{1}R\times \cdots \times R/m_{n}R\\&x+mR&\mapsto &(x+m_{1}R,\ldots ,x+m_{n}R)\end{matrix}}$

Egységelemes gyűrűkben

Ha $R$ egységelemes gyűrű, akkor a következők tudhatók: Ha $I_{1},\ldots ,I_{n}$ ideálok, és $I_{i}+I_{j}=R$ minden $i\neq j$ indexre, és az ideálok metszete $I$, akkor az $R/I$ gyűrű izomorf az $R/I_{1}\times \cdots \times R/I_{n}$ szorzatgyűrűvel, mégpedig ezzel az izomorfiával:

${\begin{matrix}f:&R/I&\to &R/I_{1}\times \cdots \times R/I_{n}\\&x+I&\mapsto &(x+I_{1},\ldots ,x+I_{n}).\end{matrix}}$

Ha $R$ még kommutatív is, akkor $I$ az $I_{j}$ ideálok szorzata. Ehhez a kommutatív tulajdonság szükséges, mivel erre ellenpélda is adható nem kommutatív esetben.

Vesszük a nem kommutatív polinomok gyűrűjét (például mátrixok fölött) $x$ és $y$ határozatlanokkal, és tekintjük ezeket az ideálokat: $I$ az $x$ által generált principiális ideál és $J$ az $xy+1$ által generált principiális ideál. Ekkor $I+J=R$, de $I\cap J\neq IJ$.

Az $I$ ideál azokból a polinomokból áll, amelyek minden monomjában tényezőként szerepel $x$. A $J$ polinomjai eltűnnek, ha $y=-1/x$. Ekkor $p=(xy+1)x\in I\cap J$. Definiáljuk $R$ termjeit úgy, mint $R$ $x$ és $y$ által generált multiplikatív monoidjának elemét, és foka a szokásos fok az $y=x$ helyettesítés után.

Másrészt legyen egy $q\in J$. Ekkor $q$ minden maximális fokú egytagja függ $y$-tól, különben az $y=-1/x$ helyettesítés nem tüntetné el a polinomot. Hasonlóak igazak, ha $q\in IJ$. Vegyük észre, hogy a legmagasabb fokú egytagokban a legutolsó $y$-os tényezőt legalább egy $x$ megelőzi. Például az $x^{2}yxyx^{5}$ polinomban az utolsó $y$-t három $x$ előzi meg. Eszerint $p=(xy+1)x\notin IJ$, mivel benne az utolsó $y$-t csak egy $x$ előzi meg. Tehát $I\cap J\neq IJ$.

Ezzel szemben $I+J=R$ általánosan implikálja, hogy $I\cap J=IJ+JI$. Ehhez elég belátni, hogy $I\cap J=(I\cap J)(I+J)\subset IJ+JI$, mivel a másik irány triviális. Ha $I_{1},\dots ,I_{m}$ páronként relatív prímek, akkor az

$R/(I_{1}\cap \cdots \cap I_{m})\to R/I_{1}\oplus \cdots \oplus R/I_{m}$

természetes leképezés izomorfia.

Fordítás

• Ez a szócikk részben vagy egészben a Chinesischer Restsatz című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
• Ez a szócikk részben vagy egészben a Chinese remainder theorem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Alice és Bob - 22. rész: Alice, Bob és a kínaiak

Források

• Freud Róbert – Gyarmati Edit: Számelmélet. Budapest: Nemzeti Tankönyvkiadó. 2000. ISBN 963-19-0784-8  
• Joseph W. Dauben: Chapter 3: Chinese Mathematics. In Victor J. Katz: The Mathematics of Egypt, Mesopotamia, China, India and Islam: A Sourcebook. Princeton: Princeton University Press. 2007. 187–384. o. ISBN 978-0-691-11485-9  
• Pierre Duchet: Hypergraphs. In Ronald L. Graham – Martin Grötschel – Lovász László: Handbook of Combinatorics, 1–2. kötet. Amszterdam: Elsevier. 1995. 381–432. o. ISBN 978-0-444-82346-5 Lásd különösen a 2.5. fejezetet (Helly property, 393–394. o.), MathSciNet  
• Carl Friedrich Gauss: Disquisitiones Arithemeticae. Angolra ford. Arthur A. Clarke. 2., jav. kiad. New York: Springer. 1986. ISBN 978-0-387-96254-2 Hozzáférés: 2017. december 22.  
• Kenneth Ireland – Michael Rosen: A Classical Introduction to Modern Number Theory. 2. kiad. New York: Springer. 1990. ISBN 0-387-97329-X  
• Subhash Kak: Computational aspects of the Āryabhaṭa algorithm. Indian Journal of History of Science, XXI. évf. 1. sz. (1986) 62–71. o. Hozzáférés: 2017. december 22.
• Victor J. Katz: A History of Mathematics: An Introduction. 2. kiad. (hely nélkül): Addison-Wesley. 1998. ISBN 978-0-321-01618-8  
• Oystein Ore: Number Theory and Its History. Reprint kiad. New York: Dover. 1988. ISBN 978-0-486-65620-5 Eredeti kiadás: 1948  
• Kenneth H. Rosen: Elementary Number Theory and its Applications. 3. kiad. (hely nélkül): Addison-Wesley. 1993. ISBN 978-0-201-57889-8