Kínai maradéktétel

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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 megoldható, és a megoldás egyetlen maradékosztály lesz \mod{M}, ahol M=m_1 m_2 \dots m_k.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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, \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 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 kongruenciarendszert. 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[szerkesztés | forrásszöveg szerkesztése]

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