residueklasser

Residueklasser, eller restklasser, er et grunnleggende begrep i tallteori som beskriver hvordan heltall kan grupperes etter sin rest når de deles på et fast heltall n. To heltall a og b er kongruente modulo n hvis n deler differansen a − b. Residueklassen til a modulo n er mengden [a]_n = { a + k n | k ∈ Z }. Alle heltall som tilhører samme klasse har samme rest ved divisjon med n, og antallet klasser er n. Man kan velge en representant i hver klasse, ofte de minste restene 0, 1, ..., n−1, og skrive [a] eller a mod n som klasseledende representant.

Operasjoner mellom klasser er veldefinerte: [a]_n + [b]_n = [a+b]_n, [a]_n − [b]_n = [a−b]_n, og [a]_n · [b]_n = [ab]_n. Divisjon er ikke alltid mulig i mod-aritmetikk; en invers finnes for [a]_n hvis og bare hvis gcd(a,n) = 1, og slike enheter utgjør gruppen (Z/nZ)^× under multiplikasjon.

Strukturen Z/nZ kalles ringen med heltallsmodulus n. For å løse kongruenser og utføre modulære beregninger benytter man egenskapene til restklasser og ofte teoremer som den kinesiske restteoremen når n har flere faktorer. Residueklasser er sentrale i kryptografi, for eksempel RSA, samt i algoritmer for reduksjon og effektive beregninger i datamaskiner.