A redukált maradékrendszer a moduláris aritmetika egyik alapvető fogalma. Legyen az m modulus rögzített. Az a egész számmal 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 együtt redukált maradékrendszert alkotnak.
Tulajdonságok, tételek
A mod m redukált maradékosztályok száma (az Euler-függvény értéke m-re), így a mod m redukált maradékrendszerek eleműek.
Kritériumok 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 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 lenne arj-vel, akkor ri kongruens lenne rj-vel, mert a relatív prím m-hez; m-hez relatív prímek szorzásával m-hez relatív prímeket kapunk.
További információk Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
Források Freud Róbert - Gyarmati Edit: Számelmélet
Kategória:Számelmélet