# Definition:Reduced Residue System

Jump to navigation
Jump to search

## Contents

## 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

- 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): Entry:**reduced residue system**