Maradékosztály

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

Legyen az m egy természetes szám. Mivel a kongruencia ekvivalenciareláció, ezért osztályoz.

Tetszőleges egész esetén az egész számok halmaza m diszjunkt osztály uniójára bomlik fel, mégpedig úgy, hogy esetén az i-dik osztályban alakú számok vannak, ahol k végigfut az egészeken (más szóval, az i-dik osztályba az m-mel osztva i maradékot adó számok tartoznak). Ezeket az osztályokat m szerinti, vagy másképpen modulo m maradékosztályoknak nevezzük. A maradékosztályok jelentősége az, hogy ha két szám azonos maradékosztályba esik (modulo m), akkor kongruensek egymással modulo m, ha pedig különböző maradékosztályból valók, akkor nem kongruensek.

Egy mod m maradékosztályból kiválasztott tetszőleges a elemet a maradékosztály reprezentáns elemének nevezzük, s azt mondjuk, hogy a reprezentálja a maradékosztályt.

Tulajdonságok[szerkesztés]

A mod m maradékosztályok gyűrűt alkotnak: összeadhatók, kivonhatók és szorozhatók, de az osztás nem végezhető el reprezentáns elemekkel. Multiplikatív inverze ugyanis pontosan a redukált maradékosztályoknak van. Ezek minden eleme relatív prím m-hez. Ha m prím, akkor az invertálás segítségével az osztás is definiálható; ekkor a maradékosztályok gyűrűje test.

Teljes maradékrendszer[szerkesztés]

Ha minden egyes mod m maradékosztályt egy elem reprezentál, akkor ezek a számok teljes maradékrendszert alkotnak.

Tételek[szerkesztés]

Tétel - Néhány egész szám teljes maradékrendszert alkot mod m akkor és csak akkor, ha számuk m, és nincs köztük két egymással kongruens szám.

Bizonyítás - Legyen Tm teljes maradékrendszer mod m. Minden maradékosztályból egy és csak egy elem van Tm-ben, ezért Tm elemszáma m.

Mivel minden maradékosztályból egy elemet választottuk, ezért Tm elemei között nincs két szám, amely egymással kongruens.

Tekintsünk most m darab egész számot, amik között nincsenek kongruensek. Ezek csupa különböző maradékosztályba tartoznak, és mivel m darab van belőlük, azért az összes maradékosztály képviselve van.

Tétel - Legyen r1, r2,…,rm teljes maradékrendszer mod m. Legyen továbbá a relatív prím m-hez, b tetszőleges egész szám. Ekkor ar1+b, ar2+b, …, arm+b is teljes maradékrendszer mod m.

Bizonyítás - Az előző kritériumokra épül. Sorra ellenőrizünk mindent:

Az új rendszer elemszáma m.

Ha ari+b és arj+b kongruensek mod m, akkor a kongruencia mindkét oldalából b-t kivonva ari és arj kongruensek lennének. a relatív prím m-hez, ezért lehet vele egyszerűsíteni. Kapjuk, hogy ri és rj kongruensek. Ez csak úgy lehet, hogy i = j.

Tétel - Ha a kongruens b mod m, akkor lnko(a,m) = lnko(b,m)

Bizonyítás - A kongruencia azt jelenti, hogy b = a + mc valamely c egész számra. a és m is osztható lnko(a,m)-mel, ezért lnko(a,m) b-nek és m-nek is közös osztója, így lnko(a,m) osztója lnko(b,m)-nek.

A fordított oszthatóság ugyanígy, szerepcserével adódik.

Források[szerkesztés]

Freud Róbert - Gyarmati Edit: Számelmélet