Mathematical-Reasoning · Unit 27 · Video 5 · Interactive Practice

Congruence Modulo n Means Matching Remainders

IKey Formulas

Result	Statement
Division Algorithm	for $x \in \mathbb{Z}$ , $n \in \mathbb{N}$ : unique $q, r \in \mathbb{Z}$ with $x = nq + r$ and $0 \le r \lt n$
Congruent to the remainder	if $x = nq + r$ with $0 \le r \lt n$ , then $x \equiv r \pmod{n}$
Theorem	$x \equiv y \pmod{n} \iff$ $x$ and $y$ have the same remainder on division by $n$

Key Insight: Same remainder $\Rightarrow$ congruent uses symmetry and transitivity ( $x \equiv r$ , $r \equiv y$ ). Congruent $\Rightarrow$ same remainder uses transitivity and the uniqueness of $r$ in $0 \le r \lt n$ .

IIColumns of Equal Remainder

Both tests, $n \mid (x - y)$ and equal remainders, always give the same verdict.

Modulus n 5

IIIWhy the Range Matters

Many pairs $(q, r)$ satisfy $x = nq + r$ ; only one has $0 \le r \lt n$ .

x n 5 q 2

IVQuiz Questions

Problem 1 · Same Column as 17

Given: $n = 5$ . Which integer is congruent to $17$ modulo $5$ ?

✅ Correct!

17 = 5 \cdot 3 + 2

and

-8 = 5 \cdot (-2) + 2

: both have remainder

2

. Check:

17 - (-8) = 25 = 5 \cdot 5

❌ Not quite.

-2 = 5 \cdot (-1) + 3

, so its remainder is

3

, not

2

; and

17 - (-2) = 19

❌ Not quite.

8 = 5 \cdot 1 + 3

has remainder

3

;

17 - 8 = 9

is not a multiple of

5

❌ Not quite.

13 = 5 \cdot 2 + 3

;

17 - 13 = 4

❌ Not quite. Compare remainders on division by

5

Show solution

$17 = 5 \cdot 3 + 2$ , so $17$ has remainder $2$ . The remainders of the options are:

$-2 = 5 \cdot (-1) + 3$ : remainder $3$ .
$8 = 5 \cdot 1 + 3$ : remainder $3$ .
$-8 = 5 \cdot (-2) + 2$ : remainder $2$ .
$13 = 5 \cdot 2 + 3$ : remainder $3$ .

Only $-8$ matches, and indeed $17 - (-8) = 25 = 5 \cdot 5$ .

Problem 2 · Remainder of a Negative Integer

Given: $x = -13$ and $n = 5$ . What is the remainder $r$ from the Division Algorithm?

✅ Correct!

-13 = 5 \cdot (-3) + 2

with

0 \le 2 \lt 5

❌ Not quite.

-13 = 5 \cdot (-2) + (-3)

is a true equation, but the remainder must satisfy

0 \le r \lt 5

❌ Not quite.

3

is the remainder of

13

. For

-13

5 \cdot (-3) + 3 = -12

❌ Not quite.

-13 = 5 \cdot (-4) + 7

is true, but

7 \ge 5

is outside the range.

❌ Not quite. Find

q

so that

-13 - 5q

lands in

0 \le r \lt 5

Show solution

We need $-13 = 5q + r$ with $0 \le r \lt 5$ . Try values of $q$ :

$q = -2$ : $r = -13 + 10 = -3$ (too small).
$q = -3$ : $r = -13 + 15 = 2$ (in range).
$q = -4$ : $r = -13 + 20 = 7$ (too big).

So $r = 2$ . Consequently $-13 \equiv 2 \pmod{5}$ , and $-13$ is congruent to $17$ modulo $5$ , which also has remainder $2$ .

Problem 3 · The Step That Needs Uniqueness

Given: in proving "if $x \equiv y \pmod{n}$ , then $x$ and $y$ have the same remainder", we reach $x = nq + r$ , where $r$ is the remainder of $y$ . Why does this equation alone not finish the proof?

✅ Correct! For example

17 = 5 \cdot 2 + 7

, yet

7

is not the remainder of

17

. The range and the uniqueness in the Division Algorithm pin

r

down.

❌ Not quite.

q

comes from

n \mid (x - r)

, so it is an integer by the definition of divides.

❌ Not quite. Congruence modulo

n

is symmetric; that was proved earlier in the unit.

❌ Not quite. A remainder can be

0

; the condition is

0 \le r \lt n

❌ Not quite. Think of

17 = 5 \cdot 2 + 7

Show solution

From $x \equiv r \pmod{n}$ we get $x - r = nq$ for an integer $q$ , so $x = nq + r$ . But an equation $x = nq' + r'$ holds for infinitely many integer pairs, for example $17 = 5 \cdot 2 + 7 = 5 \cdot 3 + 2 = 5 \cdot 4 + (-3)$ .

What makes $r$ the remainder of $x$ is that it also satisfies $0 \le r \lt n$ (it is the remainder of $y$ ), and the Division Algorithm says only one pair $(q, r)$ satisfies both the equation and the range. So $x$ and $y$ have the same remainder $r$ .

Problem 4 · Remainders 4 and 1 Modulo 6

Given: integers $a$ and $b$ have remainders $4$ and $1$ on division by $6$ . Which statement must be true?

✅ Correct!

a - b = 6(q_1 - q_2) + 3 = 3(2q_1 - 2q_2 + 1)

, a multiple of

3

❌ Not quite. The remainders on division by

6

differ, so by the theorem

a \not\equiv b \pmod{6}

❌ Not quite.

a - b = 6k + 3

is odd, so

4 \nmid (a - b)

❌ Not quite.

a - b = 6k + 3

is odd:

a = 4

b = 1

give

a - b = 3

❌ Not quite. Write

a = 6q_1 + 4

and

b = 6q_2 + 1

and subtract.

Show solution

Write $a = 6q_1 + 4$ and $b = 6q_2 + 1$ with $q_1, q_2 \in \mathbb{Z}$ . Then

a - b = 6(q_1 - q_2) + 3 = 3\,(2q_1 - 2q_2 + 1),

so $3 \mid (a - b)$ and $a \equiv b \pmod{3}$ . Since $a - b$ is odd, it is not a multiple of $2$ , $4$ or $6$ ; and different remainders on division by $6$ already rule out modulus $6$ by the theorem.

Solved: 0 / 4