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

Congruence Modulo n as a Symmetric Relation

IKey Formulas

Statement	Equivalent forms
$x \equiv y \pmod{n}$	$n \mid (x - y)$ $\iff$ $x - y = nk$ for some $k \in \mathbb{Z}$ $\iff$ $x = y + nk$ for some $k \in \mathbb{Z}$
Congruence modulo $n$ as a set	$\{ (x, y) \in \mathbb{Z} \times \mathbb{Z} \mid x \equiv y \pmod{n} \} \subseteq \mathbb{Z} \times \mathbb{Z}$ , a relation on $\mathbb{Z}$
Properties theorem	reflexive on $\mathbb{Z}$ , symmetric and transitive
Remainder fact	if $x = nq + r$ with $0 \le r \lt n$ , then $x \equiv r \pmod{n}$

Key Insight: Symmetry takes one move: multiply $x - y = nk$ by $-1$ to get $y - x = n(-k)$ , and $-k$ is an integer.

IIThe Relation as a Set of Pairs

Each pair $(x, y)$ with $n \mid (x - y)$ is a filled cell; symmetry is the mirror across the diagonal.

Modulus n 5

IIIThe Know-Show Table for Symmetry

Work backward from the goal, forward from the hypothesis, and the integer $m = -k$ connects them.

Example Step 1

Step	Know	Reason
$P$	$x \equiv y \pmod{n}$	hypothesis
$P1$	$n \mid (x - y)$	definition of congruence
$P2$	$x - y = nk$ for some $k \in \mathbb{Z}$	definition of divides
$P3$	$y - x = n(-k)$ , and $-k \in \mathbb{Z}$	multiply $P2$ by $-1$
$Q2$	$y - x = nm$ for some $m \in \mathbb{Z}$	take $m = -k$
$Q1$	$n \mid (y - x)$	definition of divides
$Q$	$y \equiv x \pmod{n}$	definition of congruence

IVQuiz Questions

Problem 1 · Which Pair Is in the Relation?

Given: congruence modulo $6$ as a relation on $\mathbb{Z}$ . Which pair belongs to it?

✅ Correct!

20 - 2 = 18 = 6 \cdot 3

, so

20 \equiv 2 \pmod{6}

❌ Not quite.

20 - 4 = 16

, and

16

is not a multiple of

6

❌ Not quite.

9 - (-4) = 13

, not a multiple of

6

. (The sum

9 + (-4) = 5

is not what congruence tests.)

❌ Not quite.

6

is divisible by

6

, but congruence tests the difference:

6 - 1 = 5

❌ Not quite. Test whether

6

divides

x - y

Show solution

A pair $(x, y)$ is in the relation exactly when $6 \mid (x - y)$ :

$(20, 4)$ : $20 - 4 = 16$ , not a multiple of $6$ .
$(20, 2)$ : $20 - 2 = 18 = 6 \cdot 3$ , so it is in the relation.
$(9, -4)$ : $9 - (-4) = 13$ , not a multiple of $6$ .
$(6, 1)$ : $6 - 1 = 5$ , not a multiple of $6$ .

Problem 2 · Same Pair, Different Moduli

Given: the pair $(23, 8)$ . Which statement is true?

✅ Correct!

23 - 8 = 15 = 3 \cdot 5

. The pair is in congruence modulo

n

exactly for the divisors

n = 1, 3, 5, 15

15

❌ Not quite.

15

is not a multiple of

4

, so

(23, 8)

drops out of congruence modulo

4

❌ Not quite.

15

is odd, so

2 \nmid 15

❌ Not quite.

15 = 6 \cdot 2 + 3

, so

6 \nmid 15

❌ Not quite. Compute

23 - 8

and test each modulus.

Show solution

$23 \equiv 8 \pmod{n}$ means $n \mid (23 - 8) = 15$ . The natural numbers dividing $15$ are $1, 3, 5, 15$ . Of the four moduli offered, only $3$ divides $15$ : $15 = 3 \cdot 5$ .

So each natural number $n$ gives its own relation, and the same pair can belong to one and not to another.

Problem 3 · The Missing Integer

Given: in the proof that congruence modulo $n$ is symmetric, we know $x - y = nk$ for an integer $k$ , and we must find an integer $m$ with $y - x = nm$ . Which $m$ works?

✅ Correct!

y - x = -(x - y) = -(nk) = n(-k)

, and

-k \in \mathbb{Z}

❌ Not quite.

y - x

is the negative of

x - y

, so

m = k

works only when

k = 0

❌ Not quite.

\tfrac{1}{k}

is usually not an integer (and is undefined for

k = 0

); the definition of divides needs an integer.

❌ Not quite.

n(k - n) = nk - n^2

, which is not

-(nk)

in general.

❌ Not quite. Multiply

x - y = nk

-1

Show solution

Multiply both sides of $x - y = nk$ by $-1$ :

y - x = -(x - y) = -nk = n(-k).

Since $k$ is an integer, so is $-k$ . Taking $m = -k$ gives $y - x = nm$ with $m \in \mathbb{Z}$ , so $n \mid (y - x)$ and $y \equiv x \pmod{n}$ .

Problem 4 · A New Relation, the Same Plan

Given: the relation $R$ on $\mathbb{Z}$ with $x \mathrel{R} y$ if and only if $3 \mid (2x + y)$ . Is $R$ symmetric?

✅ Correct!

2y + x = 3x + 3y - (2x + y) = 3(x + y) - 3k

, and

x + y - k

is an integer.

❌ Not quite. The conclusion is right but the reason is false: with

x = 1

y = 0

the two expressions are

2

and

1

❌ Not quite. Two different expressions can both be multiples of

3

. Symmetry needs

3 \mid (2y + x)

, not

2y + x = 2x + y

❌ Not quite.

2 \cdot 3 + 0 = 6 = 3 \cdot 2

, so

(3, 0) \in R

as well.

❌ Not quite. Assume

2x + y = 3k

and look for an integer

m

with

2y + x = 3m

Show solution

Know: $x \mathrel{R} y$ , so $2x + y = 3k$ for some $k \in \mathbb{Z}$ . Show: $y \mathrel{R} x$ , that is, $2y + x = 3m$ for some $m \in \mathbb{Z}$ .

Write $2y + x$ in terms of $2x + y$ :

2y + x = 3x + 3y - (2x + y) = 3x + 3y - 3k = 3(x + y - k).

Since $x + y - k$ is an integer, $3 \mid (2y + x)$ and $y \mathrel{R} x$ . So $R$ is symmetric.

Solved: 0 / 4