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]

Legyenek páronként relatív prímek, pedig tetszőleges egészek. Ekkor az

kongruencia-rendszer megoldható, és a megoldás egyetlen maradékosztály lesz , ahol

Bizonyítás[szerkesztés]

A megoldás egyértelműsége
Tegyük fel, hogy és is megoldások. Ekkor minden esetén (mivel -k relatív prímek), amiből a kongruenciák definíciója alapján következik, hogy . Tehát és (azaz bármely két megoldás) ugyanabba a maradékosztályba tartoznak , így csak egy megoldó maradékosztálya van a kongruencia-rendszernek.

A megoldás létezése
Legyen és . Legyen olyan, hogy . A megoldások számára vonatkozó tétel alapján ilyen létezik, mert . Az jó megoldás lesz. Ennek bizonyításához nézzük meg, hogy valóban teljesül-e ().
A kongruencia ekvivalens kongruenciával, mert , ha . Mivel , ezért áll fenn, ami épp a bizonyítandó állítás.

Alkalmazásai[szerkeszté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.

Polinom helyettesítési értéke[szerkesztés]

Tegyük fel, hogy ki szeretnénk számolni egy egész együtthatós többváltozós polinom helyettesítési értékét adott helyen, és ismerjük, hogy teljesül. Ekkor válasszunk olyan egymáshoz relatív prím egészeket (praktikusan prímszámokat szokás) a kínai maradéktételhez, amelyekre: teljesül, majd számoljuk ki a polinom helyettesítési értékeit minden -re legyen az eredmény , majd a kínai maradéktételt használva azt az egyértelmű egész számot, amelyre és

teljesül. Ekkor 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 , 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[szerkeszté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észt vevő 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ó[szerkesztés]

Az általános Hermite-interpoláció: Adva vannak a λ1, …, λr komplex pontok, és hozzájuk rendre az aj,k: 1 ≤ jr, 0 ≤ k < νj értékek. Keressünk egy P(x) ∈ C[x] polinomot úgy, hogy:

A megoldás: Vezessük be az

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

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

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

polinomokat. Ekkor törtfelbontása r polinomot ad, a továbbiakban ezeket Sj jelöli, és fokszámuk deg(Sj) < νj. Ezzel

így

Tehát a kongruenciarendszer megoldása

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

Dedekind-tétel[szerkesztés]

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 fi iI egyenként különböző monoidhomomorfia független, ahol minden fi: Mk. Más szavakkal, (αi)iI elemek minden családja, ahol αik, és , ugyanaz, mint (0)iI.

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 fi : Mkhomomorfiákat k-algebra homomorfiákká, ahol k[M] M monoid gyűrűje k fölött. Ekkor a linearitás miatt a

feltételből következik

Állítjuk, hogy az i, jI; ij indexekre Fi : k[M] → k és Fj : k[M] → k nem arányosak egymáshoz. Különben fi és ;fj is arányos lenne, így monoid homomorfiaként egyenlőek lennének, emiatt fi (1) = 1 =  fj, ami ellentmond annak, hogy különböznek.

Ezért a Ker Fi és Ker Fj magok különböznek. Mivel k[M]/Ker FiFi(k[M]) = k test, Ker Fi maximális ideálja k[M]-nek, minden iI 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:

ahol

Következik, hogy a

leképezés szürjektív. A k[M]/Ker FiFi(k[M]) = k, izomorfiákkal a Φ leképezés megfelel ennek:

Most abból, hogy

kapjuk, hogy:

minden (ui)iIvektorra a ψ leképezés szerinti képben. Mivel ψ szürjektív, ez azt jelenti, hogy

minden

vektorra. Tehát (αi)iI = (0)iI.

Más alkalmazások[szerkesztés]

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 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 -val osztani is kell (legyen most prím), ha az adott szám osztható -vel, ez pedig nem elvégezhető művelet. Ilyenkor dobjuk el az 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[szerkesztés]

Mivel minden i-re az mi számok és relatív prímek, azért a kiterjesztett euklideszi algoritmussal találhatók ri és si számok, hogy

.

Végezzük el az helyettesítést, ezzel

.

Ekkor

a szimultán kongruencia egy megoldása.

Példa[szerkesztés]

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

Itt . A kibővített euklideszi algoritmussal kiszámítható, hogy

, also
, also
, also

Eszerint auz egyenletrendszer egy megoldása. Mivel , azért az összes megoldás kongruens 47-tel modulo 60.

Általános eset[szerkesztés]

Á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 párra

lnko.

[1] 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ékot, de osztható héttel. Tehát keressük ennek az egyenletrendszernek a megoldását:

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:

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

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[szerkesztés]

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

Ha ezek megoldhatók, akkor , ezért ekvivalensek az

kongruenciával, ahol

.

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[szerkesztés]

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

Ha az elemek páronként relatív prímek, és szorzatuk m, akkor az hányadosgyűrű izomofr az szorzatgyűrű, mégpedig az alábbi izomorfia van köztök:

Egységelemes gyűrűkben[szerkesztés]

Ha R egységelemes gyűrű, akkor a következők tudhatók: Ha ideálok, és minden indexre, és az ideálok metszete I, akkor az gyűrű izomorf az szortzatgyűrűvel, mégpedig ezzel az izomorfiával:

Ha R még kommutatív is, akkor I az 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 ∩ J ≠ 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 ∈ I ∩ 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 ∈ 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 ∈ 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 x2yxyx5 polinomban az utolsó y-t három x előzi meg. Eszerint p = (xy + 1)x ∉ IJ , mivel benne az utolsó y-t csak egy x előzi meg. Tehát I ∩ J ≠ IJ.

Ezzel szemben I + J = R általánosan implikálja, hogy I ∩ J = IJ + JI. Ehhez elég belátni, hogy I ∩ J = (I ∩ J)(I + J) ⊂ IJ + JI, mivel a másik irány triviális. Ha I1, ..., Im páronként relatív prímek, akkor az

természetes leképezés izomorfia.

Jegyzetek[szerkesztés]

  1. A. Bogomolny: Chinese Remainder Theorem, Theorem 2 auf Interactive Mathematics Miscellany and Puzzles

Fordítás[szerkeszté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 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.

Források[szerkesztés]

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

Dauben, Joseph W. (2007), "Chapter 3: Chinese Mathematics", in Katz, Victor J., The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook, Princeton University Press, pp. 187-384, ISBN 978-0-691-11485-9

Duchet, Pierre (1995), "Hypergraphs", in Graham, R. L.; Grötschel, M. & Lovász, L., Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 381–432. See in particular Section 2.5, "Helly Property", pp. 393–394.

Gauss, Carl Friedrich & Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected ed.), New York: Springer, ISBN 978-0-387-96254-2, <http://www.springer.com/mathematics/algebra/book/978-0-387-96254-2>

Ireland, Kenneth & Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X

Kak, Subhash (1986), "Computational aspects of the Aryabhata algorithm", Indian Journal of History of Science 21 (1): 62–71, <http://www.ece.lsu.edu/kak/AryabhataAlgorithm.pdf>

Katz, Victor J. (1998), A History of Mathematics / An Introduction (2nd ed.), Addison Wesley Longman, ISBN 978-0-321-01618-8

Ore, Oystein (1988), Number Theory and Its History, Dover, ISBN 978-0-486-65620-5

Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0201-57889-8