Reduced Residue System/Examples

From ProofWiki
Jump to navigation Jump to search

Examples of Reduced Residue Systems

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}\)


Modulo $18$

Least Positive Residues

The least positive reduced residue system of $18$ is the set of positive integers:

$\set {1, 5, 7, 11, 13, 17}$


Powers of $5$

The set of integers:

$\set {1, 5, 25, 125, 625, 3125}$

forms a reduced residue system modulo $18$.


Arithmetic Progression

The arithmetic progression:

$\set {5, 11, 17, 23, 29, 35}$

does not form a reduced residue system modulo $18$.


Square Numbers

The set of integers:

$\set {1, 25, 49, 121, 169, 289}$

does not form a reduced residue system modulo $18$.


Sources