Definition:Reduced Residue System
Jump to navigation
Jump to search
Definition
Let $m \in \Z_{> 0}$ be a (strictly) positive integer.
The reduced residue system modulo $m$, denoted $\Z'_m$, is the set of all residue classes of $k$ (modulo $m$) which are prime to $m$:
- $\Z'_m = \set {\eqclass k m \in \Z_m: k \perp m}$
Thus $\Z'_m$ is the set of all coprime residue classes modulo $m$:
- $\Z'_m = \set {\eqclass {a_1} m, \eqclass {a_2} m, \ldots, \eqclass {a_{\map \phi m} } m}$
where:
- $\forall k: a_k \perp m$
- $\map \phi m$ denotes the Euler phi function of $m$.
Least Positive Coprime Residues
The least positive reduced residue system modulo $m$ is the set of integers:
- $\set {a_1, a_2, \ldots, a_{\map \phi m} }$
with the following properties:
- $\map \phi m$ is the Euler $\phi$ function
- $\forall i: 0 < a_i < m$
- each of which is prime to $m$
- no two of which are congruent modulo $m$.
Also known as
A reduced residue system modulo $m$ is also known as a reduced set of residues modulo $m$.
Some authors refer to this as the set of relatively prime residue classes modulo $m$.
Some sources denote it $\Z^*_m$ or $Z^*_m$.
Examples
The reduced sets of residues modulo $n$ for the first few (strictly) positive integers are:
\(\ds 1\) | \(:\) | \(\ds \set 1\) | ||||||||||||
\(\ds 2\) | \(:\) | \(\ds \set 1\) | ||||||||||||
\(\ds 3\) | \(:\) | \(\ds \set {1, 2}\) | ||||||||||||
\(\ds 4\) | \(:\) | \(\ds \set {1, 3}\) | ||||||||||||
\(\ds 5\) | \(:\) | \(\ds \set {1, 2, 3, 4}\) | ||||||||||||
\(\ds 6\) | \(:\) | \(\ds \set {1, 5}\) | ||||||||||||
\(\ds 7\) | \(:\) | \(\ds \set {1, 2, 3, 4, 5, 6}\) | ||||||||||||
\(\ds 8\) | \(:\) | \(\ds \set {1, 3, 5, 7}\) | ||||||||||||
\(\ds 9\) | \(:\) | \(\ds \set {1, 2, 4, 5, 7, 8}\) | ||||||||||||
\(\ds 10\) | \(:\) | \(\ds \set {1, 3, 7, 9}\) |
Also see
- Results about reduced residue systems can be found here.
Sources
- 1964: Iain T. Adamson: Introduction to Field Theory ... (previous) ... (next): Chapter $\text {I}$: Elementary Definitions: $\S 1$. Rings and Fields: Example $4$
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-2}$ Residue Systems: Definition $\text {4-4}$
- 1971: Allan Clark: Elements of Abstract Algebra ... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 25$
- 1988: Dominic Welsh: Codes and Cryptography ... (previous) ... (next): Notation
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): reduced residue system