Saturday, 7 March 2026

Exercise (5.2).2

Write down two different reduced residue systems modulo 8.


We remind ourselves of Definition (5.11). 

A reduced residue system modulo $n$ is the set of integers $\{r_1, r_2, \ldots , r_{\phi (n)}\}$ such that

(i) $\gcd (r_i, n) = 1$ for $i = 1, 2, 3, \ldots , \phi (n)$.

(ii) $r_i \not \equiv r_j \pmod n$ where $i \ne j$.


One reduced residue system modulo 8 is

$$ \{1, 3, 5, 7 \} $$

Another is derived from the above by simply adding $n=8$ to each natural number

$$ \{ 9, 11, 13, 15 \} $$