Congruences · Definition

Complete residue system

elementary number theorycongruences

Before you start you need to know

Residues are the tool for counting congruence classes without repeating or missing any. They appear in proofs about powers, arithmetic functions, and primality.

Definition

A complete residue system modulo \(m\) is a set of \(m\) integers that contains exactly one representative from each congruence class modulo \(m\).

\[\{r_1,\dots,r_m\}\ \text{with}\ r_i\not\equiv r_j\ (\bmod\ m)\ \forall i\neq j\]

If \(\{r_1,\dots,r_m\}\) is a complete residue system modulo \(m\), then every integer is congruent modulo \(m\) to exactly one of the \(r_i\). Moreover, if \(\gcd(a,m)=1\), the image \(\{ar_1,\dots,ar_m\}\) is also complete, since multiplication by \(a\) permutes the classes. For example, \(\{0,1,2,3\}\) is complete modulo \(4\), and so is \(\{0,5,6,3\}\), because \(5\equiv1\), \(6\equiv2\) and \(3\equiv3\) (mod 4).

To show that \(\{0,5,6,3\}\) is complete modulo \(4\), it suffices to check that its four elements give distinct remainders upon division by \(4\): \(0,1,2,3\). Since there are four distinct remainders and exactly four classes, the set is complete. This counting argument avoids checking every pair of congruences.

A typical mistake is to think that any set of \(m\) integers is a complete system. For instance, \(\{0,1,5,9\}\) has four elements, but \(1,5\) and \(9\) are all congruent to \(1\) modulo \(4\), so it is not complete. One must check that the classes are all distinct.

Think about it

What must you check to claim that a set of \(m\) integers is complete modulo \(m\)?

That its elements give distinct remainders upon division by \(m\), so each class appears exactly once.

Exercises 10

  1. How many elements must a complete residue system modulo \(7\) have?
  2. Which of these sets is a complete residue system modulo \(5\)?
  3. How many congruence classes are there modulo \(9\)?
  4. If \(\{0,1,2,3\}\) is complete modulo \(4\), what is the remainder of \(7\) divided by \(4\)?
  5. Which of these integers belongs to the class of \(2\) modulo \(6\)?
  6. Determine whether \(\{0,1,7,3,4,5,6\}\) is a complete residue system modulo \(7\) and explain why.
  7. If \(\{1,2,3,4,5,6\}\) is complete modulo \(6\), which of these sets is also complete modulo \(6\)?
  8. Let \(m=8\) and consider \(\{1,3,5,7\}\) as a set of residues. How many integers are needed to complete a complete residue system?
  9. Prove that if \(\gcd(a,7)=1\) and \(\{r_1,\dots,r_7\}\) is complete modulo \(7\), then \(\{ar_1,\dots,ar_7\}\) is also complete. State the key idea.
  10. Let \(m=6\). What is the result of multiplying the system \(\{0,1,2,3,4,5\}\) by \(a=5\) and reducing modulo \(6\)?

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 4
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2