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

$x\equiv c_1 \pmod{m_1}$

$x\equiv c_2 \pmod{m_2}$

$\vdots$

$x\equiv c_k \pmod{m_k}$

kongruencia-rendszer bármilyen $c_1, c_2, \dots, c_k$ egészek esetén megoldható, és a megoldás egyetlen maradékosztály lesz $\mod{M}$, ahol $M=m_1 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 m_2 \dots m_k$ és $\ M_i=\frac{M}{m_i}$. Legyen $z_i \in \Bbb Z$ olyan, hogy $M_iz_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_1z_1c_1 + M_2z_2c_2 + \dots + M_kz_kc_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_iz_ic_i \pmod{m_i}$ kongruenciával, mert $\ m_i \mid M_j$, ha $i \neq j$. Mivel $M_iz_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ás

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. 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 M2$ teljesül. Ekkor válasszunk olyan $m_1,m_2, \cdots,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 M2 \leq x<\frac M2$ és

$x\equiv c_1 \pmod{m_1}$

$x\equiv c_2 \pmod{m_2}$

$\vdots$

$x\equiv c_k \pmod{m_k}$

teljesül. Ekkor $f(a_1,a_2, \dots ,a_n )=M$ 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 kongurenciarendszert. Ezáltal lényegesen kevesebb memóriát használva ki tudjuk számítani a végeredményt. 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.

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).

Forrás

• Freud─Gyarmati: Számélmélet, Nemzeti Tankönyvkiadó, 2000