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

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

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 komplex pontok, és hozzájuk rendre az értékek. Keressünk egy 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 -ben van egy egyértelmű polinom, hogy:

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

polinomokat. Ekkor törtfelbontása polinomot ad, a továbbiakban ezeket jelöli, és fokszámuk . Ezzel

így

Tehát a kongruenciarendszer megoldása

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

Dedekind-tétel[szerkesztés]

Dedekind tétele a lineárisan független karakterekről: Legyen monoid, integritási tartomány, amit szintén monoidnak tekintünk a rajta vett szorzással. Ekkor minden véges egyenként különböző monoidhomomorfia független, ahol minden . Más szavakkal, elemek minden családja, ahol és , ugyanaz, mint .

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

feltételből következik

Állítjuk, hogy az indexekre és nem arányosak egymáshoz. Különben és is arányos lenne, így monoid homomorfiaként egyenlőek lennének, emiatt , ami ellentmond annak, hogy különböznek.

Ezért a és magok különböznek. Mivel test, maximális ideálja -nek, minden 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 , izomorfiákkal a leképezés megfelel ennek:

Most abból, hogy

kapjuk, hogy:

minden vektorra a leképezés szerinti képben. Mivel szürjektív, ez azt jelenti, hogy

minden

vektorra. Tehát .

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 -re az számok és relatív prímek, azért a kiterjesztett euklideszi algoritmussal találhatók és 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 egész számot, amire teljesülnek a következők:

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

, tehát
, tehát
, tehát

Eszerint az 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

.[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ékul, 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 és 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 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 , akkor az hányadosgyűrű izomorf az szorzatgyűrű, mégpedig az alábbi izomorfia van köztük:

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

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

Ha még kommutatív is, akkor 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) és határozatlanokkal, és tekintjük ezeket az ideálokat: az által generált principiális ideál és az által generált principiális ideál. Ekkor , de .

Az ideál azokból a polinomokból áll, amelyek minden monomjában tényezőként szerepel . A polinomjai eltűnnek, ha . Ekkor . Definiáljuk termjeit úgy, mint és által generált multiplikatív monoidjának elemét, és foka a szokásos fok az helyettesítés után.

Másrészt legyen egy . Ekkor minden maximális fokú egytagja függ -tól, különben az helyettesítés nem tüntetné el a polinomot. Hasonlóak igazak, ha . Vegyük észre, hogy a legmagasabb fokú egytagokban a legutolsó -os tényezőt legalább egy megelőzi. Például az polinomban az utolsó -t három előzi meg. Eszerint , mivel benne az utolsó -t csak egy előzi meg. Tehát .

Ezzel szemben általánosan implikálja, hogy . Ehhez elég belátni, hogy , mivel a másik irány triviális. Ha páronként relatív prímek, akkor az

természetes leképezés izomorfia.

Jegyzetek[szerkesztés]

  1. Alexander Bogolmony: Chinese Remainder Theorem. Interactive Mathematics Miscellany and Puzzles (Hozzáférés: 2017. dec. 22.)

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 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. Amszerdam: 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. dec. 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. dec. 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