restklasser

Restklasser, or residue classes, are the equivalence classes of integers under congruence modulo a fixed positive integer n. Two integers a and b are in the same restklass modulo n if n divides their difference, written a ≡ b (mod n). The set of all integers congruent to a modulo n forms one restklass [a], and the restklasser modulo n partition the integers into exactly n distinct classes.

For a fixed n, the restklasser can be represented by the canonical representatives 0, 1, ..., n−1. The collection of all these classes is denoted Z/nZ. The relation is an equivalence relation, and the resulting cosets form a quotient structure that inherits addition and multiplication from the integers, with the results reduced modulo n.

Operations on restklasser are well-defined: addition and multiplication are performed by adding or multiplying representatives and reducing the result modulo n. Thus Z/nZ is a finite ring with n elements. If n is prime, the entire ring Z/nZ is a field, and every nonzero restklass has a multiplicative inverse.

When n is composite, not every restklass has an inverse. The units, i.e., the Restklasser with inverses, are precisely those represented by integers coprime to n; their number is Euler’s totient φ(n). A reduced residue system mod n is any set of φ(n) representatives, one from each unit restklass.

Applications of restklasser include solving congruences, performing modular arithmetic, and uses in number theory and cryptography (such as RSA). They provide a compact framework for working with equivalence of integers under modular constraints.