Currently studying Dirichlets proof of Primes in arithmetic progressions. Is there a difference between a Reduced Residue Class and a Reduced Residue System?
Any subset R of the integers is called a reduced residue system modulo n if:
gcd(r, n) = 1 for each r contained in R; R contains φ(n) elements; no two elements of R are congruent modulo n.
For example, if a reduced residue system for 12 is a = {1,5,7,11}, and we have also {13,17,19,23}, would the reduced residue class be the general description of this? e.g all the terms that are equal to the terms in a mod 12?
Is the reduced residue class the same as the set of all congruence classes?
$\endgroup$ 22 Answers
$\begingroup$The relation "congruence $\!\bmod n$" is an equivalence relation on $\Bbb Z$ so it partitions $\Bbb Z$ into equivalence classes $$ [\![a]\!]_n = \{b\in \Bbb Z\ :\ a\equiv b\!\!\!\pmod{\!n}\} = \{\ldots, a-2n,\, a-n,\, a,\, a+n,\, a+2n,\,\ldots\}$$
For such congruence relations these classes are also called residue classes since the typical normalized (least nonegative) element is the remainder $\,a\bmod n,\,$ i.e. the "residue" left after dividing $\,a\,$ by $\,n,\,$ using Euclidean division with remainder.
A residue class $\,[\![a]\!]_n$ is called reduced if $\,\gcd(a,n)=1\,$ (recall, by the Bezout gcd identity, this is equivalent to $\,a\,$ is a unit (invertible) modulo $\,n).\,$ This definition is well-defined, i.e. it does not depend on the choice of representative of the class, since $\,[\![a']\!]_n = [\![a]\!]_n\,$ $\Rightarrow\, a'\equiv a\pmod{\!n}\,$ $\Rightarrow\, \gcd(a',n)=\gcd(a,n)=1,\,$ by the Euclidean algorithm, using $\,a' = a + kn.\,$
A residue system is a list of residue classes that is complete and irredundant i.e. it lists all classes in the associated partition of $\Bbb Z$ exactly once, i.e. given any integer there is a unique class in the list that contains it. Similarly for reduced residue systems.
For simplicity, many authors drop the class notation and instead denote each class by choosing a canonical normalized representative - usually either the remainder $\,a\bmod n,\,$ or else the least magnitude reps, e.g. $\, 0,\pm1,\pm2\pmod{\!5}.\,$ Then we simply pullback the congruence arithmetic operations to these normal reps in the usual manner - via transport of structure..
For example, a residue system $\bmod 6\,$ is $\,[\![0]\!]_6, [\![1]\!]_6, [\![2]\!]_6, [\![3]\!]_6, [\![4]\!]_6, [\![5]\!]_6$ or, dropping class notation, $0,1,2,3,4,5,\,$ and a reduced residue system is $\,[\![1]\!]_6, [\![5]\!]_6\,$ or $\,1,5,\,$ i.e. all classes of units (= invertibles) $\bmod 6,\,$ where $[\![5]\!]_6 [\![5]\!]_6 = [\![1]\!]_6,\,$ or $\,5\cdot 5\equiv 1\pmod{\!6}$
$\endgroup$ 1 $\begingroup$Is there a difference between a reduced residue class and a reduced residue system? NO. Class and system have the same meaning in this context.
Is the reduced residue class the same as the set of all congruence classes? NO.
A set of m representatives, one from each of the residue classes 1, 2, ... , m, is called a complete residue system modulo m. ( Apostol IANT, pg. 110)
Example: mod 10 0,1,2,3,4,5,6,7,8,9
By a reduced residue system modulo m we mean any set of EulerPhi(m) integers, incongruent modulo m, each of which is relatively prime to m. ( Apostol IANT, pg. 113)
Example: mod 10 1,3,7,9
$\endgroup$
