Congruences: Definitions and Basic Properties

In the Chinese book: 同余的概念与基本性质

On an m-hour clock, numbers that differ by a multiple of m are congruent.

📖 §2.1 of 《整除、同余与不定方程》M14 Choosing a Good Modulus line

Try this

Each time $n$ goes up by $1$ , the hand moves one mark. Add $7$ times in a row and the hand is back where it started. In the table it has moved down one row, but it is still in the same column.
Pick any two numbers in the same column and subtract. What is the difference always a multiple of?
Drag $n$ to $- 3$ . Which column does it land in? Is that the remainder you expected?
Switch to “Add”. Press $a + 7$ , $a - 7$ and $b + 7$ a few times. Which of the three readouts never moves?
Switch to “Multiply” and repeat step 4.

Definition Let $m$ be a positive integer. If $m ∣ (a - b)$ , we say that $a$ is congruent to $b$ modulo $m$ and write $a \equiv b (mod m)$ .

Being congruent means “leaving the same remainder when divided by $m$ ”, which is the same as “being in the same column of the table”. Each column is called a residue class, and there are $m$ of them modulo $m$ .

Predict first

Today is Wednesday. What day of the week will it be $100$ days from now?

WednesdayThursdayFridaySaturday

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

Why

Steps 4 and 5 say that before you add or multiply, you can replace each number by any other number in its column. Why does swapping change nothing?

Congruent numbers can replace each other

Step 1 / 5

Work it out once
Mod $7$ : $9 + 5 = 14$ , which lands in the “≡0” column.

$9 + 5 = 14 \equiv 0 (mod 7)$
Replace a by a number in its column
Now multiply
Replace a again
So compute with the smallest one

If you can swap in multiplication, you can swap in powers (repeated multiplication) too: if $a \equiv b$ , then $a^{n} \equiv b^{n}$ . So you can find the remainder of a number even when it is far too big to write down.

Example Find the remainder when $2^{100}$ is divided by $7$ . $2^{3} = 8 \equiv 1 (mod 7)$ and $100 = 3 \times 33 + 1$ , so

2^{100} = (2^{3})^{33} \times 2 \equiv 1^{33} \times 2 = 2 (mod 7) .

Remove one condition

Adding, subtracting and multiplying are all safe. Dividing (cancelling) is not, unless one extra condition holds.

Break it

Counterexample lab: remove one condition

Conclusion: if $c a \equiv c b (mod m)$ , you can cancel $c$ and get $a \equiv b (mod m)$

Mod $7$ , multiply by $3$ . Each $x$ gets an arrow pointing to the remainder of $3 x$ . The seven arrows land in seven different places: if $3 a$ and $3 b$ land in the same place, then $a$ and $b$ must have started in the same place. So you can cancel.

Practice

Exercise 1Basic

Find the remainder when $2024$ is divided by $9$ .

Exercise 2Basic

Find the remainder when $37 \times 58 + 46$ is divided by $7$ .

Exercise 3Advanced

Find the remainder when $3^{100}$ is divided by $13$ .

Exercise 4Challenge

Prove that for every positive integer $n$ , $3^{2 n + 1} + 2^{n + 2}$ is divisible by $7$ .

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Cancelling on both sides of a congruence without thinking

4 \times 6 \equiv 4 \times 1 (mod 10)

. Cancel the

4

on both sides to get

6 \equiv 1 (mod 10)

What went wrong? Think first, then open

Diagnosis $24 \equiv 4 (mod 10)$ is true, but $6 - 1 = 5$ is not a multiple of $10$ . $4$ and $10$ share the factor $2$ : in $10 ∣ 4 \times 5$ , part of the $10$ is “eaten” by the $4$ .

When you cancel

c

, divide the modulus by

(c, m)

at the same time: from

4 \times 6 \equiv 4 \times 1 (mod 10)

you only get

6 \equiv 1 (mod 5)

. Only when

(c, m) = 1

can you cancel and keep the modulus.

“Add, subtract and multiply freely; before cancelling, check coprimality”

Exhibit

Giving a negative number a negative remainder

- 3

divided by

7

leaves remainder

- 3

(or

3

What went wrong? Think first, then open

Diagnosis A remainder must be between $0$ and $m - 1$ . $- 3$ means going back $3$ marks from $0$ , which lands on mark $4$ . And $3$ and $- 3$ differ by $6$ , not a multiple of $7$ , so they are not even in the same column.

- 3 = (- 1) \times 7 + 4

, so the remainder is

4

, that is,

- 3 \equiv 4 (mod 7)

“Negative numbers go backwards round the clock”

Exhibit

Reducing the exponent mod m as well

10 \equiv 3 (mod 7)

, so

2^{10} \equiv 2^{3} (mod 7)

What went wrong? Think first, then open

Diagnosis Congruent numbers can be swapped in the base. The exponent is not a number being added or multiplied, and there is no such rule for it. In fact $2^{10} = 1024 \equiv 2$ , while $2^{3} = 8 \equiv 1$ .

First find the period of the powers:

2^{3} \equiv 1 (mod 7)

, so the exponent should be reduced mod

3

10 = 3 \times 3 + 1

, so

2^{10} \equiv 2^{1} = 2

“Reduce the base mod m and the exponent mod the period”