Reduced residue system

Definition

Let $n$ be a positive integer. A reduced residue system modulo $n$ is a set $R$ of integers with these properties. Each element of $R$ is coprime to $n$. No two distinct elements of $R$ are congruent modulo $n$. Each integer coprime to $n$ is congruent modulo $n$ to some element of $R$.

Remarks

Thus $R$ contains exactly one element of each residue class of integers coprime to $n$. It has $\varphi(n)$ elements, where $\varphi$ is Euler's totient function. For example, $\{1, 5, 7, 11\}$ is a reduced residue system modulo $12$. If $R$ is a reduced residue system modulo $n$ and $\gcd(a, n) = 1$, then $\{ a r : r \in R \}$ is also a reduced residue system modulo $n$. This fact gives a proof of Euler's theorem.

Explanations

L1 human

Take a complete residue system modulo $n$, and keep only the numbers with no common factor with $n$. For $n = 10$, the numbers $0, 1, \dots, 9$ give the reduced residue system $\{1, 3, 7, 9\}$.