Reststelsel

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search

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

Speciale reststelsels zijn volledige reststelsels en gereduceerde reststelsels.

Volledig reststelsel[bewerken]

Een reststelsel heet een volledig reststelsel (of volledig restsysteeem) modulo als het stelsel van elke restklasse een element bevat. Een volledig reststelsel heeft dus precies elementen.

Gereduceerd reststelsel[bewerken]

Een reststelsel heet een gereduceerd reststelsel (of gereduceerd restsysteem), als het bestaat uit getallen die relatief priem zijn met en het aantal elementen gelijk is aan . Dus:

  1. voor elke ;
  2. ;
  3. Geen twee elementen van zijn congruent modulo .

Hierin is de indicator- of totientfunctie.

Een dergelijk gereduceerd reststelsel modulo kan verkregen worden uit een volledig reststelsel door alle getallen die niet relatief priem zijn met weg te laten.

Voorbeelden

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: .

Andere gereduceerde reststelsels modulo 12 zijn:

  • {13,17,19,23}
  • {- 11, -7, -5, -1}
  • {- 7, -13,13,31}
  • {35,43,53,61}

Eigenschappen[bewerken]

Als een gereduceerd reststelsel is en , dan is

.

Elk getal in een gereduceerd reststelsel modulo is een voortbrenger van de optelgroep van gehele getallen modulo .

Zie ook[bewerken]

Externe links[bewerken]