A tétel bizonyításához az alábbi két állítást kell igazolni: Az maradékosztály valóban az maradékosztálypár metszete, azaz . Nincs másik olyan maradékosztálypár a halmazban, amelynek a metszete lenne. Az 1. állítás: A utáni megjegyzés 5. pontja …
Az és maradékosztályok metszete pontosan azokat az egész számokat fogja tartalmazni, amelyek mindkét maradékosztályban benne vannak. Ezek az alábbi kongruenciarendszert kielégítő egész számok lesznek: A kínai maradéktétel () alapján ezek az egész számok pontosan egy …
Először a kongruenciarendszer megoldhatóságát igazoljuk. Az első kongruencia a alapján pontosan akkor oldható meg, ha az kitüntetett közös osztónak többszöröse a jobboldalon álló egész szám. Ehhez hasonlóan a második kongruencia pontosan akkor oldható meg, ha …
Amennyiben relatív prím a modulushoz, akkor alkalmazható az Euler-Fermat tétel (). Eszerint teljesül az alábbi kongruencia: A alapján az Euler-féle -függvény értéke ebben az esetben . Ebből a tétel első állítása adódik: Ám ebben az …
Nézzük először az 1. állítást! A a alapján a , , , …, közül a -hoz relatív prím egészek számát adja meg. Nincs más dolgunk tehát, mint ezeket megszámlálni. A alapján egy tetszőleges egész szám …
A tehát azon -nél nemnagyobb pozitív egészeknek a számával egyezik meg, amelyek -hez relatív prímek. Vegyük észre, hogy tetszőleges egész szám akkor és csak akkor relatív prím -hez, ha relatív prím -hoz is és -hez …
Legyen és az integritástartomány két tetszőleges eleme, és jelöljük -rel a nullelemet, -rel pedig az egységelemet – amely ugye létezik, hiszen a alapján minden euklidészi gyűrű egységelemes. Ha és közül mindkettő , akkor a 1. …
Az általánosság megsértése nélkül feltehetjük, hogy az feltétel teljesül. Ha ugyanis mégsem így lenne, akkor a tétel szövege alapján szükségképpen teljesül az feltétel, és az alábbi gondolatmenet az és együtthatók szerepének felcserélésével ugyanígy végigjátszható. Először …
A alapján az állítás teljesül minden főideálgyűrűben. Minthogy a értelmében minden euklidészi gyűrű főideálgyűrű, ezért az állítás nyilvánvalóan teljesül speciálisan az euklidészi gyűrűkben is.
Nézzük először a teljes maradékrendszerre vonatkozó állítást! Mivel az új maradékrendszer elemszáma is , ezért a alapján elegendő a páronkénti inkongruenciát ellenőrizni. Legyen tehát és az új maradékrendszer két tetszőleges eleme, és tegyük fel, hogy …
Nézzük először a teljes maradékrendszerekre vonatkozó állítást! Tegyük fel, hogy teljes maradékrendszer modulo . Mivel a modulo maradékosztályok száma a alapján , és minden maradékosztályból pontosan egy elemet tartalmaz, ezért elemszáma szükségképpen . Továbbá elemei …
Az maradékosztály a alapján pontosan akkor redukált, ha invertálható, azaz egyértelműen létezik olyan maradékosztály, amelyre teljesül az alábbi: Ez pontosan az alábbi lineáris kongruencia egyértelmű megoldhatóságát jelenti: Ez viszont a szerint pontosan akkor oldható meg, …
Elegendő a 2. állítást igazolni, abból ugyanis automatikusan következik a megoldásszámra vonatkozó 1. állítás. Azt mondtuk, hogy az egész szám által reprezentált maradékosztály megoldása a kongruenciának, azaz: Válasszunk most egy tetszőleges egész számot. Az általa …
Először is a balideálok elemeire vonatkozó állítást igazoljuk. Jelöljük -vel azt a halmazt, amely pontosan az alakban felírható elemeket tartalmazza. Azt kell bizonyítani, hogy a legszűkebb olyan balideál, amely tartalmazza az , , …, elemeket. …
A modulo maradékosztályok pontosan az főideál szerinti maradékosztályokkal egyeznek meg. Emiatt a halmaz a tételben bevezetett és műveletekkel nem más, mint a gyűrűnek az főideál szerinti faktorgyűrűje, azaz a ben bevezetett jelölésekkel . Innentől kezdve …
A ben bevezetett modulo kongruencia ekvivalens az főideál szerinti kongruenciával. Ez utóbbi a alapján valóban egy ekvivalenciareláció, így tehát a modulo kongruencia is az. Mivel e két kongruencia ekvivalens, ezért pontosan ugyanazok lesznek a maradékosztályaik. …
A utáni megjegyzés 5. pontja alapján a maradékképző függvény a , , , …, egész számokhoz mind különböző modulo maradékot rendel. Így a 1. pontja alapján ezek a számok páronként inkongruensek. Továbbá, mivel a számuk …
Az 1. állítás: Minthogy egy ideál az egész számok gyűrűjében, ezért a miatt ő biztosan magja egy valamilyen -ből kiinduló gyűrűhomomorfizmusnak. Ugyanezen tétel, valamint a utáni megjegyzés miatt azonban a ban definiált ideál szerinti kongruencia …
Tekintsünk egy tetszőleges modulo redukált maradékrendszert. Mivel relatív prím -hez, ezért a alapján az számhalmaz is egy modulo redukált maradékrendszert alkotnak. Ez azt jelenti, hogy mindkét számhalmaz tartalmaz egy-egy reprezentánselemet az összes létező redukált maradékosztályból. …
Elsőként megmutatjuk, hogy az lineáris kongruencia pontosan akkor oldható meg, amikor megoldható az lineáris diofantoszi egyenlet. Az megoldhatósága azt jelenti, hogy létezik olyan maradékosztály, amely megoldása ennek a kongruenciának. Az maradékosztályt tehát az egész számmal …
