Redukált maradékrendszer

A Wikipédiából, a szabad enciklopédiából
(Redukált maradékosztály szócikkből átirányítva)

Legyen az m modulus rögzített. Az a-val reprezentált maradékosztályt redukált maradékosztálynak nevezzük, ha a és m relatív prímek.

Ha minden redukált maradékosztályt egy-egy számmal reprezentálunk, akkor ezek redukált maradékrendszert alkotnak.

Tulajdonságok, tételek[szerkesztés]

A mod m redukált maradékosztályok száma (ahol az Euler-függvény), így a mod m redukált maradékrendszerek eleműek.

Kritériumok[szerkesztés]

Tétel Néhány egész szám akkor és csak akkor alkot redukált maradékrendszert mod m, ha teljesülnek a következők:

  • számuk
  • inkongruensek egymással mod m
  • relatív prímek m-hez

Bizonyítás

A redukált maradékosztályok száma . Mindegyiket egy és csak egy elemmel reprezentáltunk, ezért van belőlük.

Minden egyes maradékosztályból egy elemet vettünk ki, ezért ezek nem kongruensek egymással.

A reprezentánsrendszer minden eleme relatív prím m-hez, mert mindegyik redukált maradékosztályból való.

Tekintsünk most darab, a kritériumoknak megfelelő számot. Mivel nincsenek közöttük egymással kongruens elemek, azért csupa különböző maradékosztályokba tartoznak.

Relatív prímek m-hez, így csak redukált maradékosztályoknak lehetnek elemei.

Számuk , ezért az összes redukált maradékosztályt reprezentálják.

Újabb redukált maradékrendszer[szerkesztés]

Tétel

Ha redukált maradékrendszer, és a relatív prím m-hez, akkor az ari számok is redukált maradékrendszert alkotnak mod m.

Bizonyítás - Ellenőrizzük az előző tételben szereplő tulajdonságokat.

  • az új rendszer elemszáma
  • ha ari kongruens arj lenne, akkor ri kongruens rj lenne, mert a relatív prím m-hez
  • m-hez relatív prímek szorzásával m-hez relatív prímeket kapunk.

Források[szerkesztés]

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