---
tag: 0E22JKS4W4
kind: definition
name: Complete residue system
aliases: [complete-system-of-residues]
msc: [11A07]
defines: 0GPBVKE31D
uses: [0QRV8FPK5M]
sources:
  - url: https://en.wikipedia.org/wiki/Modular_arithmetic
    locator: Residue systems
---

## Definition

Let $n$ be a positive integer.
A complete residue system modulo $n$ is a set $S$ of integers that contains exactly one element of each [[residue class|0QRV8FPK5M]] modulo $n$.

## Remarks

Equivalently, $S$ has exactly $n$ elements, and no two distinct elements of $S$ are congruent modulo $n$.
The set $\{0, 1, \dots, n - 1\}$ is the set of the least nonnegative residues. It is a complete residue system modulo $n$.
For odd $n$, the set $\{ -\tfrac{n-1}{2}, \dots, -1, 0, 1, \dots, \tfrac{n-1}{2} \}$ of the least absolute residues is also a complete residue system.
If $S$ is a complete residue system modulo $n$ and $\gcd(a, n) = 1$, then $\{ a s + b : s \in S \}$ is also a complete residue system for each integer $b$.

## Explanations

### L1 human

A complete residue system picks one representative from each box of the integers modulo $n$.
For $n = 4$, both $\{0, 1, 2, 3\}$ and $\{4, -3, 10, 7\}$ are complete residue systems.