Restklasse

In de rekenkunde verstaat men onder de restklasse modulo een positief geheel getal ${\displaystyle n}$, de verzameling gehele getallen die bij deling door ${\displaystyle n}$ dezelfde rest opleveren. Deze rest wordt niet-negatief gekozen. De getallen in een bepaalde restklasse zijn dus per definitie congruent modulo ${\displaystyle n}$.

In veel gevallen is ${\displaystyle n}$ een vast gekozen getal, en noteert men de restklasse waartoe het gehele getal ${\displaystyle z}$ behoort met een streepje boven de ${\displaystyle z}$:

${\displaystyle {\overline {z}}=\{\ldots ,z-2n,z-n,z,z+n,z+2n,\ldots \}}$

Er zijn precies ${\displaystyle n}$ verschillende restklassen modulo ${\displaystyle n}$.

In het algemeen behoren twee gehele getallen tot dezelfde restklasse modulo ${\displaystyle n}$ als en slechts als hun verschil een veelvoud is van ${\displaystyle n}$ (als ze congruent zijn modulo ${\displaystyle n}$).

Zij ${\displaystyle n=5}$. Er bestaan vijf verschillende restklassen modulo 5. Het gaat om de volgende vijf oneindige verzamelingen:

${\displaystyle {\overline {0}}=\left\{\ldots ,-10,-5,0,5,10,15,\ldots \right\}}$

${\displaystyle {\overline {1}}=\left\{\ldots ,-9,-4,1,6,11,16,\ldots \right\}}$

${\displaystyle {\overline {2}}=\left\{\ldots ,-8,-3,2,7,12,17,\ldots \right\}}$

${\displaystyle {\overline {3}}=\left\{\ldots ,-7,-2,3,8,13,18,\ldots \right\}}$

${\displaystyle {\overline {4}}=\left\{\ldots ,-6,-1,4,9,14,19,\ldots \right\}}$

De klasse

${\displaystyle {\overline {5}}=\left\{\ldots ,-5,0,5,10,15,20,\ldots \right\}}$

is geen nieuwe klasse, het is gewoon een andere schrijfwijze van de klasse ${\displaystyle {\overline {0}}}$.

De restklassen modulo ${\displaystyle n}$ zijn de partitieklassen die horen bij de equivalentierelatie "is congruent met".

Elke geheel getal ${\displaystyle z}$ behoort tot precies één restklasse modulo ${\displaystyle n}$, namelijk, de klasse waar de rest van de geheeltallige deling van ${\displaystyle z}$ door ${\displaystyle n}$ toe behoort.

De restklasse modulo ${\displaystyle n}$ waar het getal ${\displaystyle z}$ toe behoort, is de nevenklasse van ${\displaystyle z}$ ten opzichte van de deelgroep

${\displaystyle n\mathbb {Z} ={\overline {0}}=\left\{\ldots ,-2n,-n,0,n,2n,\ldots \right\}}$

van de groep ${\displaystyle (\mathbb {Z} ,+)}$ der gehele getallen. Omdat de optelling van gehele getallen een abelse groep vormt, hoeven we geen onderscheid te maken tussen linker- en rechternevenklassen.

De factorgroep ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ definieert een commutatieve groepsbewerking op de verzameling der restklassen modulo ${\displaystyle n}$. Dit is de eindige cyclische groep met ${\displaystyle n}$ elementen.

Voor de optelling geldt dat, als ${\displaystyle a_{1}}$ en ${\displaystyle a_{2}}$ congruent zijn modulo ${\displaystyle n}$, en ook ${\displaystyle b_{1}}$ en ${\displaystyle b_{2}}$ congruent zijn modulo ${\displaystyle n}$, dat dan ook ${\displaystyle a_{1}+b_{1}}$ en ${\displaystyle a_{2}+b_{2}}$ congruent zijn modulo ${\displaystyle n}$. Hetzelfde geldt voor de vermenigvuldiging: ${\displaystyle a_{1}\cdot b_{1}}$ en ${\displaystyle a_{2}\cdot b_{2}}$ zijn congruent modulo ${\displaystyle n}$.

De deelring ${\displaystyle n\mathbb {Z} }$ van de commutatieve ring ${\displaystyle (\mathbb {Z} ,+,\cdot )}$ is een ideaal, zodat we de factorring of quotiëntring ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ kunnen beschouwen.

De verzameling der restklassen modulo ${\displaystyle n}$ vormt dus een commutatieve ring met eenheidselement.

In deze ring zijn niet noodzakelijk alle niet-triviale elementen omkeerbaar, met andere woorden: hij is niet altijd een lichaam. Dit is slechts het geval als ${\displaystyle n}$ een priemgetal is (het bijzondere geval ${\displaystyle n=1}$ wordt gewoonlijk buiten beschouwing gelaten). In alle andere gevallen is de ring zelfs niet nuldelervrij: als ${\displaystyle n}$ geschreven kan worden als het product van twee natuurlijke getallen ${\displaystyle a}$ en ${\displaystyle b}$ (strikt begrepen tussen 1 en ${\displaystyle n}$), dan is

${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {0}}}$

De omkeerbare elementen van ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ vormen een abelse groep voor de vermenigvuldiging van restklassen, genoteerd ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$

Het aantal elementen van deze vermenigvuldigingsgroep is de Euler-indicator (totiënt) van ${\displaystyle n}$, d.i. het aantal natuurlijke getallen tussen 0 en ${\displaystyle n}$ dat geen delers gemeenschappelijk heeft met ${\displaystyle n}$.

In deze context komt de stelling van Euler neer op de opmerking dat elk element in deze eindige groep een eindige orde heeft. Men bekomt het neutraal element door een willekeurig gegeven element net zo vaak met zichzelf te vermenigvuldigen als er elementen in de hele groep zijn.