Maradékosztály

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

Legyen az m egy 1-nél nagyobb természetes szám. Az egész számok szétválogathatók aszerint, hogy az m-mel való maradékos osztás után mennyit adnak maradékul. Ha két egész szám az m-mel maradékosan elosztva ugyanannyit ad maradékul, akkor azt mondjuk, hogy ez a két egész szám egymással kongruens. A kongruencia egy ekvivalenciareláció, és az általa létrehozott ekvivalenciaosztályok az m szerinti maradékosztályok. Minden m esetében m darab különböző maradékosztály létezik.

Szabatosan megfogalmazva: 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 (rövid jelölése: mod 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 modulo 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.

A maradékosztályok fogalmát Carl Friedrich Gauss vezette be 1801-es Számelméleti vizsgálódások című művében.

Példa[szerkesztés]

Legyen m = 5.

Ekkor 5 maradékosztály létezik

  • a { ..., –20, –15, –10, –5, 0, 5, 10, 15, 20, ... } számhalmaz a 0-maradékosztály, azaz az 5·i vagy 5·i+0 alakú számok, ahol i tetszőleges egész szám;
  • a { ..., –19, –14, –9, –4, 1, 6, 11, 16, 21, ... } számhalmaz az 1-maradékosztály, azaz az 5·i+1 alakú számok, ahol i tetszőleges egész szám;
  • a { ..., –18, –13, –8, –3, 2, 7, 12, 17, 22, ... } számhalmaza 2-maradékosztály, azaz az 5·i+2 alakú számok, ahol i tetszőleges egész szám;
  • a { ..., –17, –12, –7, –2, 3, 8 13, 18, 23, ... } számhalmaz a 3-maradékosztály, azaz az 5·i+3 alakú számok, ahol i tetszőleges egész szám;
  • a { ..., –16, –11, –6, –1, 4, 9, 14, 19, 24, ... } számhalmaz a 4-maradékosztály, azaz az 5·i+4 alakú számok, ahol i tetszőleges egész szám.

Általában 0, 1, 2, ..., (m-1) mod m maradékosztályokról beszélhetünk, ahol az egyszerűség kedvéért a 0, 1, 2, ... és m-1 a megnevezésben szereplő reprezentáns elemek.

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.

Maradékosztályokkal úgy számolhatunk, hogy tetszőleges reprezentáns elemükkel számolunk, ugyanis a maradékosztályok elemei egymást helyettesíthetik az egyenletekben.

Teljes maradékrendszer[szerkesztés]

Ha adott m darab egész szám, és közülük mindegyik más mod m maradékosztályt reprezentál, akkor ezek a számok teljes maradékrendszert alkotnak.

Fontosabb tételek[szerkesztés]

1. tétel[szerkesztés]

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.

2. tétel[szerkesztés]

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.

3. tétel[szerkesztés]

Ha a kongruens b mod m, akkor lnko(a, m) = lnko(b, m).

Bizonyítás: A kongruencia azt jelenti, hogy b = a + m·c 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. Budapest: Tankönyvkiadó. 2000. ISBN 963 19 0784 8