Reststelsel

In de elementaire getaltheorie is een reststelsel of restsysteem modulo het positieve gehele getal $n$ een verzameling getallen uit verschillende restklassen modulo $n$. Een reststelsel bestaat dus uit een aantal getallen waarvan er geen twee congruent zijn modulo $n$.

Er wordt verschil gemaakt tussen volledige reststelsels en gereduceerde reststelsels.

Volledig reststelsel

Een reststelsel $R$ heet een volledig reststelsel modulo $n$ als het stelsel van iedere restklasse een element bevat. Een volledig reststelsel heeft dus precies $n$ elementen.

Gereduceerd reststelsel

Een reststelsel $R$ heet een gereduceerd reststelsel als het bestaat uit getallen die met $n$ relatief priem zijn. Het aantal elementen is gelijk aan $\varphi (n)$. Dus:

1. ${\rm {ggd}}(x,n)=1$ voor elke $x\in R$;
2. $|R|=\varphi (n)$;
3. Geen twee elementen van $R$ zijn congruent modulo $n$.

Hierin is $\varphi$ de indicator- of totientfunctie.

Een dergelijk gereduceerd reststelsel modulo $n$ ontstaat uit een volledig reststelsel door alle getallen die niet relatief priem zijn met $n$ weg te laten.

Voorbeeld

Een volledig reststelsel modulo 12 is bijvoorbeeld {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Daarin zijn 1, 5, 7 en 11 de enige getallen die relatief priem zijn met 12. Zij vormen een gereduceerd reststelsel modulo 12: {1,5,7,11}. De kardinaliteit van dit stelsel is 4 en gelijk aan de indicator van 12: $\varphi (12)=4$.

Andere gereduceerde reststelsels modulo 12 zijn { 13, 17, 19, 23 } en { - 11, -7, -5, -1 }.

Eigenschappen

Als $R=\{x_{1},x_{2},\ldots ,x_{\varphi (n)}\}\ {\text{mod}}\ n$ een gereduceerd reststelsel is en $n>2$, dan is

$\sum _{i=1}^{\varphi (n)}x_{i}\equiv 0\quad {\text{mod}}\ n$.

Ieder getal in een gereduceerd reststelsel modulo $n$ is een voortbrenger van de additieve groep van gehele getallen modulo $n$.

Websites

• MathWorld. Reduced residu systeem.