Reduced Residue Systems

Introduction

students, in modular arithmetic, numbers often “circle back” after reaching a certain point 🔁. For example, when working modulo $5$, the numbers $0,1,2,3,4 represent all possible remainders. But sometimes we only care about the numbers that are relatively prime to the modulus. That idea leads to a reduced residue system.

Learning goals

By the end of this lesson, students, you should be able to:

explain what a reduced residue system is and why it matters,
identify whether a number is relatively prime to a modulus,
build a reduced residue system for a given modulus,
connect reduced residue systems to linear congruences and modular inverses,
use examples to justify why a set is a reduced residue system.

Reduced residue systems are important because they help us understand when equations like $ax \equiv b \pmod n$ can be solved, especially when $a$ has an inverse modulo $n$.

What a reduced residue system means

A reduced residue system modulo $n$ is a set of integers that includes exactly one representative from each congruence class modulo $n$ among the numbers that are relatively prime to $n$.

That sounds long, so let’s break it down:

A number is relatively prime to $n$ if its greatest common divisor with $n$ is $1$, written $\gcd(a,n)=1$.
The numbers with $\gcd(a,n)=1$ are called the units modulo $n$.
A reduced residue system picks one number from each of those valid residue classes.

Usually, we choose the representatives from the set $\{1,2,3,\dots,n\}$ or $\{0,1,2,\dots,n-1\}$, but any integers in the same classes can work.

Example: modulo $10$

Look at the numbers from $1$ to $10$.

Which ones are relatively prime to $10$?

$\gcd(1,10)=1$
$\gcd(2,10)=2$
$\gcd(3,10)=1$
$\gcd(4,10)=2$
$\gcd(5,10)=5$
$\gcd(6,10)=2$
$\gcd(7,10)=1$
$\gcd(8,10)=2$
$\gcd(9,10)=1$
$\gcd(10,10)=10$

So a reduced residue system modulo $10$ is $\{1,3,7,9\}$.

Why only these? Because these are exactly the residue classes modulo $10$ that are relatively prime to $10$.

How to build one

To construct a reduced residue system modulo $n$, follow these steps:

List the integers from $1$ to $n-1$.
Keep only the numbers $a$ such that $\gcd(a,n)=1$.
Make sure each residue class appears only once.

Example: modulo $12$

Let’s find all numbers between $1$ and $11$ that are relatively prime to $12$.

$\gcd(1,12)=1$
$\gcd(2,12)=2$
$\gcd(3,12)=3$
$\gcd(4,12)=4$
$\gcd(5,12)=1$
$\gcd(6,12)=6$
$\gcd(7,12)=1$
$\gcd(8,12)=4$
$\gcd(9,12)=3$
$\gcd(10,12)=2$
$\gcd(11,12)=1$

So one reduced residue system modulo $12$ is $\{1,5,7,11\}$.

Notice that $12$ itself is congruent to $0 \pmod{12}$, and $0$ is not relatively prime to $12$, since $\gcd(0,12)=12$.

Why reduced residue systems matter

Reduced residue systems connect directly to the solvability of linear congruences.

Suppose we want to solve

$$ax \equiv b \pmod n.$$

If $\gcd(a,n)=1$, then $a$ has a multiplicative inverse modulo $n$, which means there is some number $a^{-1}$ such that

$$aa^{-1} \equiv 1 \pmod n.$$

Then we can multiply both sides of the congruence by $a^{-1}$ to get

$$x \equiv a^{-1}b \pmod n.$$

This works because $a$ is in the reduced residue system modulo $n$ if it is relatively prime to $n$.

Example: solving a congruence

Solve

$$3x \equiv 4 \pmod 7.$$

Since $\gcd(3,7)=1$, the number $3$ has an inverse modulo $7$. In fact, $3^{-1} \equiv 5 \pmod 7$ because

$$3 \cdot 5 = 15 \equiv 1 \pmod 7.$$

Multiply both sides by $5$:

$$x \equiv 5 \cdot 4 \equiv 20 \equiv 6 \pmod 7.$$

So the solution is

$$x \equiv 6 \pmod 7.$$

This example shows the link between reduced residue systems and linear congruences: only numbers relatively prime to the modulus can be inverted.

Counting how many there are

The number of integers in a reduced residue system modulo $n$ is given by Euler’s totient function, written $\varphi(n)$.

So $\varphi(n)$ counts the integers in $\{1,2,\dots,n\}$ that are relatively prime to $n$.

Examples

$\varphi(10)=4$, because the reduced residue system modulo $10$ has $4$ elements: $\{1,3,7,9\}$.
$\varphi(12)=4$, because the reduced residue system modulo $12$ has $4$ elements: $\{1,5,7,11\}$.
If $p$ is prime, then every number from $1$ to $p-1$ is relatively prime to $p$, so

$$\varphi(p)=p-1.$$

This counting idea is useful because it tells us how many invertible residue classes exist modulo $n$.

Different reduced residue systems can look different

A reduced residue system is not unique. The same modulus can have many different reduced residue systems, as long as each relatively prime residue class appears exactly once.

Example: modulo $8$

One reduced residue system modulo $8$ is

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

But this is also a reduced residue system modulo $8$:

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

Why? Because each of these numbers is congruent to one of $1,3,5,7$ modulo $8:

$9 \equiv 1 \pmod 8$
$11 \equiv 3 \pmod 8$
$13 \equiv 5 \pmod 8$
$15 \equiv 7 \pmod 8$

They represent the same four residue classes, just with different numbers.

This shows that a reduced residue system is about the classes, not the exact choice of integers.

Connection to linear congruences

Reduced residue systems help us understand when multiplication modulo $n$ behaves nicely.

If $\gcd(a,n)=1$, then multiplying by $a$ permutes the reduced residue system modulo $n$. In simple terms, it shuffles the elements without creating repeats.

Example: modulo $10$

Take the reduced residue system $\{1,3,7,9\}$ and multiply every element by $3$ modulo $10$:

$3 \cdot 1 \equiv 3 \pmod{10}$
$3 \cdot 3 \equiv 9 \pmod{10}$
$3 \cdot 7 \equiv 1 \pmod{10}$
$3 \cdot 9 \equiv 7 \pmod{10}$

The result is still $\{1,3,7,9\}$, just rearranged.

This is important because it shows that multiplying by a unit modulo $n$ preserves the structure of the reduced residue system. That idea supports solving congruences like $ax \equiv b \pmod n$ when $\gcd(a,n)=1$.

A real-world style example

Imagine students is keeping track of repeating schedule cycles, like a task that repeats every $12$ hours ⏰. The numbers $1,5,7,11$ are special modulo $12 because each one can “undo” multiplication under mod $12$ arithmetic. If a time adjustment factor is $5$, then there is an inverse modulo $12$ because $\gcd(5,12)=1$. But if the factor is $6$, there is no inverse modulo $12$ because $\gcd(6,12)=6$.

This matters in systems that rely on reversible steps, such as certain coding and cryptography ideas, where only numbers relatively prime to the modulus can be safely reversed.

Conclusion

Reduced residue systems give a clean way to organize the numbers that are relatively prime to a modulus. They are essential in modular arithmetic because they describe exactly which residue classes have inverses. That makes them a key tool in understanding linear congruences such as $ax \equiv b \pmod n$.

When $\gcd(a,n)=1$, solving the congruence is straightforward because $a$ has an inverse modulo $n$. The reduced residue system tells us which numbers can do this. It also connects to Euler’s totient function $\varphi(n)$, which counts how many such classes exist.

So, students, whenever you see a modulus, ask: which numbers are relatively prime to it, and how do they help with solving congruences? That question is at the heart of reduced residue systems.

Study Notes

A reduced residue system modulo $n$ contains one representative from each residue class modulo $n$ that is relatively prime to $n$.
A number $a$ is included only if $\gcd(a,n)=1$.
The number of elements in a reduced residue system modulo $n$ is $\varphi(n)$.
If $p$ is prime, then $\varphi(p)=p-1$.
Reduced residue systems are not unique; different sets can represent the same residue classes.
If $\gcd(a,n)=1$, then $a$ has an inverse modulo $n$.
Linear congruences of the form $ax \equiv b \pmod n$ are easiest to solve when $a$ is in the reduced residue system modulo $n$.
Example modulo $10$: a reduced residue system is $\{1,3,7,9\}$.
Example modulo $12$: a reduced residue system is $\{1,5,7,11\}$.
Reduced residue systems help show which multiplications modulo $n$ can be reversed 🔄.