residue systems


Definition.  Let m be a positive integer.  A complete residue systemMathworldPlanetmath modulo m is a set  {a0,a1,,am-1}  of integers containing one and only one representant from every residue classMathworldPlanetmathPlanetmath modulo m.  Thus the numbers aν may be ordered such that for all ν=0, 1,,m-1,  they satisfy   aνν(modm).

The least nonnegative remainders modulo m, i.e. the numbers

0, 1,,m-1

form a complete residue system modulo m (see long division).  If m is odd, then also the absolutely least remainders

-m-12,-m-32,,-2,-1, 0, 1, 2,,m-32,m-12

offer a complete residue system modulo m.

Theorem 1.  If  gcd(a,m)=1  and b is an arbitrary integer, then the numbers

0a+b, 1a+b, 2a+b,,(m-1)a+b

form a complete residue system modulo m.

One may speak also of a reduced residue system modulo m, which contains only one representant from each prime residue class modulo m.  Such a system consists of φ(m) integers, where φ means the Euler’s totient function.

Remark.  A set of integers forms a reduced residue system modulo m if and only if
1 it contains φ(m) numbers,
2 its numbers are coprimeMathworldPlanetmathPlanetmath with m,
3 its numbers are incongruent modulo m.

Theorem 2.  If  gcd(a,m)=1  and  {k1,k2,,kφ(m)}  is a reduced residue system modulo m, then also the numbers

k1a,k2a,,kφ(a)a

form a reduced residue system modulo m.

References

  • 1 K. Väisälä: Lukuteorian ja korkeamman algebran alkeet.  Otava, Helsinki (1950).
Title residue systems
Canonical name ResidueSystems
Date of creation 2013-03-22 16:57:08
Last modified on 2013-03-22 16:57:08
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 12
Author pahio (2872)
Entry type Definition
Classification msc 11-00
Related topic PrimeResidueClass
Related topic TotativeMathworldPlanetmath
Related topic MathbbZ_n
Defines complete residue system
Defines reduced residue system
Defines least nonnegative remainder
Defines absolutely least remainder