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{array}{rl}x& \equiv c_1(\mathrm{mod}{m}_1)\\ x& \equiv c_2(\mathrm{mod}{m}_2)\\ ⋮\\ x& \equiv c_k(\mathrm{mod}{m}_k)\end{array}$$ kongruencia-rendszer megoldható, és a megoldás egyetlen maradékosztály lesz $modM$, 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=1,2,\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(\mathrm{mod}M)$. Tehát ${x}_1$ és ${x}_2$ (azaz bármely két megoldás) ugyanabba a maradékosztályba tartoznak $modM$, í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{\mathbb{Z}}$ olyan, hogy $M_i{z}_i\equiv 1(\mathrm{mod}{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(\mathrm{mod}{m}_i)$ valóban teljesül-e ($i=1,2,\dots ,k$). A kongruencia ekvivalens $s\equiv M_i{z}_i{c}_i(\mathrm{mod}{m}_i)$ kongruenciával, mert ${m}_i\mid M_j$, ha $i\ne j$. Mivel $M_i{z}_i\equiv 1(\mathrm{mod}{m}_i)$, ezért $s\equiv c_i(\mathrm{mod}{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 $(\mathrm{mod}{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}\le x<\frac{M}{2}$ és $$\begin{array}{rl}x& \equiv c_1(\mathrm{mod}{m}_1)\\ x& \equiv c_2(\mathrm{mod}{m}_2)\\ ⋮\\ x& \equiv c_k(\mathrm{mod}{m}_k)\end{array}$$ 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 $(\mathrm{mod}{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 $$\begin{gathered} a_{j,k}: \\ 1\le j\le r, \\ 0\le k<{\nu }_j \end{gathered}$$ értékek. Keressünk egy $P(x)\in \mathbb{ℂ}[x]$ polinomot úgy, hogy:

$P^{(k)}({\lambda }_j)=a_{j,k}1\le j\le r,0\le 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)(\mathrm{mod}(x-{\lambda }_j{)}^{{\nu }_j}),1\le j\le r$

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

$\mathrm{deg}(P)<n:=\sum _j{\nu }_j.$

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

$\begin{array}{rl}Q& =\prod _{i=1}^r(x-{\lambda }_i{)}^{{\nu }_i}\\ Q_j& =\frac{Q}{(x-{\lambda }_j{)}^{{\nu }_j}}\end{array}$

polinomokat. Ekkor $\frac{1}{Q}$ törtfelbontása $r$ polinomot ad, a továbbiakban ezeket $S_j$ jelöli, és fokszámuk $\mathrm{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(\mathrm{mod}(x-{\lambda }_j{)}^{{\nu }_j})1\le j\le 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 $$\begin{gathered} f_i: \\ M\to k \end{gathered}$$. 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 $$\begin{gathered} f_i: \\ M\to k \end{gathered}$$ 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 $$\begin{gathered} i,j\in I; \\ i\ne j \end{gathered}$$ indexekre $$\begin{gathered} F_i: \\ k[M]\to k \end{gathered}$$ és $$\begin{gathered} F_j: \\ k[M]\to k \end{gathered}$$ 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 $\mathrm{Ker}{F}_i$ és $\mathrm{Ker}{F}_j$ magok különböznek. Mivel $k[M]/\mathrm{Ker}{F}_i\cong F_i(k[M])=k$ test, $\mathrm{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{array}{rl}\varphi :k[M]/K& \to \prod _{i\in I}k[M]/\mathrm{Ker}{F}_i\\ \varphi (x+K)& ={(x+\mathrm{Ker}{F}_i)}_{i\in I}\end{array}$

ahol

$K=\prod _{i\in I}\mathrm{Ker}{F}_i=\bigcap _{i\in I}\mathrm{Ker}{F}_i.$

Következik, hogy a

$\begin{array}{rl}\mathrm{\Phi }:k[M]& \to \prod _{i\in I}k[M]/\mathrm{Ker}{F}_i\\ \mathrm{\Phi }(x)& ={(x+\mathrm{Ker}{F}_i)}_{i\in I}\end{array}$

leképezés szürjektív. A $k[M]/\mathrm{Ker}{F}_i\to F_i(k[M])=k$, izomorfiákkal a $\mathrm{\Phi }$ leképezés megfelel ennek:

$\begin{array}{rl}\psi :k[M]& \to \prod _{i\in I}k\\ \psi (x)& ={[F_i(x)]}_{i\in I}\end{array}$

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 $(\mathrm{mod}{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{gathered} \begin{array}{rl}{e}_i& \equiv 1(\mathrm{mod}{m}_i)\\ e_j& \equiv 0(\mathrm{mod}{m}_j), \\ j\ne i.\end{array} \end{gathered}$$.

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{array}{rl}x& \equiv 2(\mathrm{mod}3)\\ x& \equiv 3(\mathrm{mod}4)\\ x& \equiv 2(\mathrm{mod}5)\\ \end{array}$

Itt $$\begin{gathered} M=3\cdot 4\cdot 5=60, \\ {M}_1=M/3=20, \\ {M}_2=M/4=15, \\ {M}_3=M/5=12 \end{gathered}$$. 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 47mod60$, 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\ne j$ párra

$a_i\equiv a_j(\mathrm{mod}\mathrm{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{array}{rl}x& \equiv 1mod2\\ x& \equiv 1mod3\\ x& \equiv 1mod4\\ x& \equiv 1mod5\\ x& \equiv 1mod6\\ x& \equiv 0mod7\\ \end{array}$

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 1mod\mathrm{lkkt}(2,3,4,5,6)$

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

$\begin{array}{rl}x& \equiv 1mod60\\ x& \equiv 0mod7\\ \end{array}$

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{array}{rl}x& \equiv a(\mathrm{mod}n)\\ x& \equiv b(\mathrm{mod}m)\\ \end{array}$

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

$x\equiv a-yn\frac{a-b}{d}(\mathrm{mod}\frac{nm}{d})$

kongruenciával, ahol

$d=\mathrm{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,\dots ,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{array}{cccc}f:& R/mR& \to & R/m_{1}R\times \cdots \times R/m_{n}R\\ & x+mR& \mapsto & (x+m_{1}R,\dots ,x+m_{n}R)\end{array}$

Egységelemes gyűrűkben

Ha $R$ egységelemes gyűrű, akkor a következők tudhatók: Ha $I_1,\dots ,I_n$ ideálok, és $I_i+I_j=R$ minden $i\ne 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{array}{cccc}f:& R/I& \to & R/I_1\times \cdots \times R/I_n\\ & x+I& \mapsto & (x+I_1,\dots ,x+I_n).\end{array}$

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\ne 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}yxy{x}^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\ne 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