Kínai maradéktétel

számelméleti té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ételSzerkeszté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ásSzerkesztés

A megoldás egyértelműségeSzerkeszté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éseSzerkeszté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ásaiSzerkeszté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ékeSzerkeszté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ésSzerkeszté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ételSzerkeszté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ásokSzerkeszté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 meneteSzerkeszté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éldaSzerkeszté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 esetSzerkeszté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ásSzerkeszté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űkbenSzerkeszté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űvel, mégpedig az alábbi izomorfia van köztük:

 

Egységelemes gyűrűkbenSzerkeszté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.

JegyzetekSzerkesztés

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

FordításSzerkeszté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 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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információkSzerkesztés

ForrásokSzerkeszté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. 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. 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