Zredukowany układ reszt modulo

Zredukowany układ reszt modulo $n$ – jest to układ reprezentantów klas abstrakcji relacji przystawania reszt modulo $n,$ będących względnie pierwszych z $n,$ tzn. zbiór: $\Phi _{n}:=\{a\in \mathbb {Z} _{n}:{\mbox{NWD}}(a,n)=1\},$ gdzie $\mathbb {Z} _{n}$ jest zbiorem reszt modulo $n$.

Łatwo można zauważyć, że $|\Phi _{n}|=\varphi (n),$ gdzie $\varphi$ jest φ-funkcją Eulera.