residue systems
Definition. Let be a positive integer. A complete residue system modulo is a set of integers containing one and only one representant from every residue class
modulo . Thus the numbers may be ordered such that for all , they satisfy .
The least nonnegative remainders modulo , i.e. the numbers
form a complete residue system modulo (see long division). If is odd, then also the absolutely least remainders
offer a complete residue system modulo .
Theorem 1. If and is an arbitrary integer, then the numbers
form a complete residue system modulo .
One may speak also of a reduced residue system modulo , which contains only one representant from each prime residue class modulo . Such a system consists of integers, where means the Euler’s totient function.
Remark. A set of integers forms a reduced residue system modulo if and only if
it contains numbers,
its numbers are coprime with ,
its numbers are incongruent modulo .
Theorem 2. If and is a reduced residue system modulo , then also the numbers
form a reduced residue system modulo .
References
- 1 K. Väisälä: Lukuteorian ja korkeamman algebran alkeet. Otava, Helsinki (1950).