Definition:Reduced Residue System

From ProofWiki
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:

\(\displaystyle 1\) \(:\) \(\displaystyle \set 1\)
\(\displaystyle 2\) \(:\) \(\displaystyle \set 1\)
\(\displaystyle 3\) \(:\) \(\displaystyle \set {1, 2}\)
\(\displaystyle 4\) \(:\) \(\displaystyle \set {1, 3}\)
\(\displaystyle 5\) \(:\) \(\displaystyle \set {1, 2, 3, 4}\)
\(\displaystyle 6\) \(:\) \(\displaystyle \set {1, 5}\)
\(\displaystyle 7\) \(:\) \(\displaystyle \set {1, 2, 3, 4, 5, 6}\)
\(\displaystyle 8\) \(:\) \(\displaystyle \set {1, 3, 5, 7}\)
\(\displaystyle 9\) \(:\) \(\displaystyle \set {1, 2, 4, 5, 7, 8}\)
\(\displaystyle 10\) \(:\) \(\displaystyle \set {1, 3, 7, 9}\)


Also see

  • Results about reduced residue systems can be found here.


Sources