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

Congruence Is Reflexive, Symmetric and Transitive

IKey Formulas

Property	Statement	Why it holds
Definition	$a \equiv b \pmod{n}$	$n \mid (a - b)$ , so $a - b = nk$ for some $k \in \mathbb{Z}$
Reflexive	$a \equiv a \pmod{n}$	$a - a = 0 = n \cdot 0$
Symmetric	If $a \equiv b \pmod{n}$ , then $b \equiv a \pmod{n}$	$a - b = nk \;\Rightarrow\; b - a = n(-k)$
Transitive	If $a \equiv b$ and $b \equiv c \pmod{n}$ , then $a \equiv c \pmod{n}$	$a - c = (a - b) + (b - c) = n(k + q)$

Key Insight: Congruent numbers need not be equal ( $23 \equiv 8 \pmod{5}$ ), so equality's three properties must each be proved from the definition. Each proof exhibits the integer multiplier: $0$ , then $-k$ , then $k + q$ .

IIReflexive and Symmetric — Reversing the Difference

Swapping $a$ and $b$ negates the difference, so the multiplier $k$ becomes $-k$ , still an integer.

n 5 a 17 b 2

💡 The reflexive case is legitimate: $n \mid 0$ because $0 = n \cdot 0$ . What is undefined is division by zero, which the proof never uses.

IIITransitive — Two Differences Add Up

Because $a - c = (a - b) + (b - c)$ , the multipliers add: $a - c = n(k + q)$ .

n 5 a 23 b 8 c 3

💡 Challenge: find values with $a \equiv c \pmod{n}$ even though $a \not\equiv b \pmod{n}$ . The theorem does not forbid this; it only says nothing when its hypothesis fails.

IVPlanning the Transitive Proof with a Know-Show Table

The table fills backward from the goal $Q$ and forward from the hypothesis $P$ until the rows meet.

Step 1 Example

Step	Know	Reason
$P$	$a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$	Hypothesis
$P1$	$n \mid (a - b)$ and $n \mid (b - c)$	Definition of congruence
$P2$	$a - b = nk$ and $b - c = nq$ , with $k, q \in \mathbb{Z}$	Definition of divides
$P3$	$(a - b) + (b - c) = nk + nq$	Add the equations in $P2$
$\vdots$	$\vdots$	$\vdots$
$Q1$	$a - c = n \cdot (\text{some integer})$	?
$Q$	$a \equiv c \pmod{n}$	?
Step	Show	Reason

💡 The written proof presents the finished rows as one paragraph in forward order: $P$ , $P1$ , $P2$ , $P3$ , $Q1$ , $Q$ .

VQuiz Questions

Problem 1 · Reversing a Congruence

Given: $41 \equiv 6 \pmod{7}$ because $41 - 6 = 35 = 7 \cdot 5$ . Which line is the step that, as in the symmetric-property proof, shows $6 \equiv 41 \pmod{7}$ ?

✅ Correct! Reversing the order negates the difference, and the multiplier

-5

is still an integer.

❌ Check the sign.

6 - 41 = -35

, but

7 \cdot 5 = 35

; the multiplier must change sign along with the difference.

❌ Not quite.

41 - 6 = 35

, not

-35

. To show

6 \equiv 41 \pmod{7}

you need the difference

6 - 41

in that order.

❌ Not quite. A negative number can be a multiple of

7

-35 = 7 \cdot (-5)

with

-5 \in \mathbb{Z}

, so

7 \mid -35

Show solution

By definition, $6 \equiv 41 \pmod{7}$ means $7 \mid (6 - 41)$ . Multiply $41 - 6 = 7 \cdot 5$ by $-1$ :

6 - 41 = -(41 - 6) = -(7 \cdot 5) = 7 \cdot (-5).

Since $-5$ is an integer, $7 \mid (6 - 41)$ , so $6 \equiv 41 \pmod{7}$ . This is the symmetric proof with $n = 7$ and $k = 5$ .

Problem 2 · One Letter Too Few

Given: a proof of the transitive property begins: "Assume $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$ . Then $a - b = nk$ and $b - c = nk$ for some integer $k$ ." What is wrong with this start?

✅ Correct! The two congruences are separate facts, so their multipliers get separate letters, such as

k

and

q

❌ Not quite. With

23 \equiv 8

and

8 \equiv 3 \pmod{5}

, the multipliers are

3

and

1

; a single

k

cannot be both.

❌ Not quite. The definition of divides allows any integer multiplier, negative or zero included; the real problem is the repeated letter.

❌ Not quite. Assuming

a \equiv c \pmod{n}

would assume the conclusion. A direct proof starts from the hypothesis, as this one does.

Show solution

From $n \mid (a - b)$ we get some integer $k$ with $a - b = nk$ , and from $n \mid (b - c)$ we get some integer $q$ with $b - c = nq$ . Nothing says $k = q$ . Writing the same letter twice adds the extra assumption $a - b = b - c$ , so the proof would only cover that special case.

For example, $23 - 8 = 5 \cdot 3$ and $8 - 3 = 5 \cdot 1$ , so $k = 3$ and $q = 1$ . The correct proof continues to $a - c = n(k + q)$ .

Problem 3 · Following the Transitive Proof

Given: $47 \equiv 12 \pmod{7}$ and $12 \equiv -2 \pmod{7}$ . Write $47 - 12 = 7k$ and $12 - (-2) = 7q$ . The proof concludes $47 - (-2) = 7(k + q)$ . What is $k + q$ ?

✅ Correct!

k = 5

and

q = 2

, and

47 - (-2) = 49 = 7 \cdot 7

❌ Not quite.

5

k

alone, from

47 - 12 = 35

. Add

q

, from

12 - (-2) = 14

❌ Check the operation. The proof adds the two equations, so the multipliers add:

k + q

, not

k - q

❌ Not quite.

49

is the difference

a - c

itself;

k + q

is the multiplier with

49 = 7(k + q)

Show solution

From the hypotheses: $47 - 12 = 35 = 7 \cdot 5$ , so $k = 5$ ; and $12 - (-2) = 14 = 7 \cdot 2$ , so $q = 2$ .

Adding the equations:

(47 - 12) + (12 - (-2)) = 7 \cdot 5 + 7 \cdot 2 \quad\Longrightarrow\quad 47 - (-2) = 7(5 + 2) = 7 \cdot 7.

So $k + q = 7$ , and indeed $47 + 2 = 49 = 7 \cdot 7$ . Hence $47 \equiv -2 \pmod{7}$ .

Problem 4 · A Look-Alike That Breaks

Given: for integers $a$ and $b$ , say " $a$ is near $b$ " when $|a - b| \le 2$ . Which of the three properties fails for "is near"?

✅ Correct!

0

is near

2

and

2

is near

4

, but

|0 - 4| = 4 > 2

, so

0

is not near

4

❌ Not quite.

|a - a| = 0 \le 2

, so every integer is near itself.

❌ Not quite.

|b - a| = |a - b|

, so if

a

is near

b

then

b

is near

a

❌ Not quite. Try chaining:

0

is near

2

and

2

is near

4

. Is

0

near

4

Show solution

Reflexive holds: $|a - a| = 0 \le 2$ .

Symmetric holds: $|b - a| = |-(a - b)| = |a - b|$ .

Transitive fails: one counterexample suffices. Take $a = 0$ , $b = 2$ , $c = 4$ : $|0 - 2| = 2 \le 2$ and $|2 - 4| = 2 \le 2$ , but $|0 - 4| = 4 > 2$ .

Congruence escapes this because two multiples of $n$ add to a multiple of $n$ , whereas two distances of at most $2$ can add to more than $2$ . That is why each property of congruence had to be proved, not assumed.

Solved: 0 / 4