Redukált maradékrendszer

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.

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

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 ${\displaystyle \phi (m)}$
• inkongruensek egymással mod m
• relatív prímek m-hez

Bizonyítás

A redukált maradékosztályok száma ${\displaystyle \phi (m)}$. Mindegyiket egy és csak egy elemmel reprezentáltunk, ezért ${\displaystyle \phi (m)}$ 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 ${\displaystyle \phi (m)}$ 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 ${\displaystyle \phi (m)}$, ezért az összes redukált maradékosztályt reprezentálják.

Tétel

Ha ${\displaystyle r_{1},r_{2},\dots ,r_{\phi (m)}}$ redukált maradékrendszer, és a relatív prím m-hez, akkor az ar_i 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 ${\displaystyle \phi (m)}$
• ha ar_i kongruens ar_j lenne, akkor r_i kongruens r_j 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.

• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat

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