Reststelsel

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

Er wordt verschil gemaakt tussen volledige reststelsels en gereduceerde reststelsels.

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

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

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

Hierin is ${\displaystyle \varphi }$ de indicator- of totientfunctie.

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

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: ${\displaystyle \varphi (12)=4}$.

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

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

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

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

• MathWorld. Reduced residu systeem.