Residue Systems and Their Uses

Try this

$m = 7$ : drag $a$ from $1$ to $6$ . Do any arrows ever collide?
$m = 12$ : compare $a = 5$ with $a = 8$ . Then try every $a$ from $1$ to $11$ and write down all the $a$ with no collisions.
When there are collisions, look at “Places reached”: with $m = 12$ , $a = 8$ only $3$ places are reached. How many for $a = 9$ ? How is that related to $g cd (a, m)$ ?
When there are collisions, what do the numbers at the places that get hit have in common? ( $m = 12$ , $a = 8$ : $0, 4, 8$ .)

Take one number from each residue class mod $m$ . The $m$ numbers you get form a complete residue system mod $m$ . In other words: $m$ integers that are pairwise incongruent.

A complete residue system mod $5$ can be $0, 1, 2, 3, 4$ , or $- 2, - 1, 0, 1, 2$ , or even $5, 11, 17, 23, 29$ . Any $m$ consecutive integers form a complete residue system.

Predict first

Write down any $8$ integers. Which statement below is always true?

Two of them differ by a multiple of

7

Two of them add up to a multiple of

7

One of them is a multiple of

7

None of these is guaranteed

Choose an answer first; then you can see the result.

Why

When (a, m) = 1, multiplying by a just reorders

Step 1 / 6

What we want to prove
Mod $7$ , multiply by $3$ : each of the seven remainders $0, 1, \dots, 6$ sends out one arrow. We want to prove that as long as $(a, m) = 1$ , the $m$ arrows all land in different places.

$x ⟼ a x mod m$
Suppose two collide
Use coprimality
But the difference is too small
No collisions means every place is filled
A “reciprocal” for free

What it is good for: check just one period

In an expression that only uses addition, subtraction and multiplication, replacing $n$ by a congruent number does not change the remainder of the result. So to find every possible value mod $m$ , you only need to put in the $m$ numbers of one complete residue system for $n$ , one at a time.

For example, what remainders can $n^{2}$ leave when divided by $5$ ? Just check $n = 0, 1, 2, 3, 4$ :

Five numbers stand in for all the integers. A square divided by

5

can only leave

0, 1, 4

. Drag the modulus m to see others.

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: when $x$ runs through a complete residue system mod $m$ , so does $a x$

$m = 9$ , $a = 4$ . Nine arrows, nine landing places: no repeats, none missed.

Practice

Exercise 1Basic

Find the $x$ with $0 \leq x \leq 8$ such that $7 x \equiv 1 (mod 9)$ .

Exercise 2Basic

For which $a$ among $1, 2, \dots, 11$ is $0, a, 2 a, \dots, 11 a$ a complete residue system mod $12$ ?

Exercise 3Advanced

What is the smallest number of integers you must pick to be sure that two of them differ by a multiple of $10$ ?

Exercise 4Challenge

Prove that from any $5$ integers you can always choose $3$ whose sum is divisible by $3$ .

Try this

Why

When (a, m) = 1, multiplying by a just reorders

What it is good for: check just one period

Remove one condition

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Taking any m numbers as a complete residue system

Saying “ax also runs through all of them” without checking coprimality