Definition:Reduced Residue System

Definition

Let $n \in \Z: n \ge 1$.

Let $\phi \left({n}\right)$ be the Euler phi function of $n$.

The reduced residue system modulo $n$ is a set of integers:

$\left\{{a_1, a_2, \ldots, a_{\phi \left({n}\right)}}\right\}$

with the following properties:

• each of which is prime to $n$
• no two of which are congruent modulo n.

Also known as a reduced set of residues modulo $n$.

Each of the residue classes in this system can be referred to as a relatively prime residue class or coprime residue class.

Least Positive Residues

If each element of $\left\{{a_1, a_2, \ldots, a_{\phi \left({n}\right)}}\right\}$ is a positive integer less than or equal to $n$, this is called the reduced set of least positive residues modulo $n$.

Examples

The reduced set of least positive residues modulo $n$ for the first few integers are:

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

Sources

• Iain T. Adamson: Introduction to Field Theory (1964)... (previous)... (next): $\S 1.1$: Example $4$