Proving that $4 \mid m - n$ is an equivalence relation on $\mathbb{Z}$

Question

I have been able to figure out the the distinct equivalence classes. Now I am having difficulties proving the relation IS an equivalence relation.

$F$ is the relation defined on $\Bbb Z$ as follows:

For all $(m, n) \in \Bbb Z^2,\ m F n \iff 4 | (m-n)$

equivalence classes: $\{-8,-4,0,4,8\}, \{-7,-3,1,5,9\} \{-6,-2,2,6,10\}$ and $\{-5, -1, 3, 7, 11\}$

Answer 1

The partition of a set into its equivalence classes determines an equivalence relation defined on a set. That is, equivalence classes partition a set $\iff \exists$ an equivalence relation determining the partition. In this case, you found the classes (or rather, representatives of those classes)...and hence, the given relation you used which determine those classes must be an equivalence relation.

You can easily confirm that the relation is, indeed, reflexive, symmetric, and transitive on the set of integers:

• reflexive: For all $m \in \mathbb Z$, we have $m\,F\,m $ since $4\mid (m - m) = 0$

• symmetric: For all $m, n \in \mathbb Z$, if $m\,F\,n$ then $4\mid (m-n) \iff 4 \mid (n - m) \iff n\,F\,m$.

• transitive: For $m, n, p \in \mathbb Z$, if $4\mid(m-n)$ and $4\mid(n-p)$ then $4\mid \left((m-n)+(n-p)\right)\iff 4\mid (m-p)$

Your stated equivalence classes are good for integers in $[-8, 11]$ but you want to represent these classes so they encompass ALL integers, and indeed the equivalence classes as represented below partition the integers: every integer belongs to one and only one equivalence class.

Your relation defines congruence modulo $4$ on the set of integers:

Two integers $m, n$ are congruent modulo $4$ if and only if $4\mid (m - n) \iff m \equiv n \pmod 4$.

Congruence modulo $4$ is indeed an equivalence relation. Indeed, the congruence classes corresponding to your given equivalence relation are the equivalence classes determined by your equivalence relation, and they which are sometimes called the residue classes $\pmod 4$:

Class $[0] = \{4k\mid k \in \mathbb Z\}$

Class $[1] = \{4k + 1 \mid k \in \mathbb Z\}$

Class $[2] = \{4k + 2\mid k \in \mathbb Z\}$

Class $[3] = \{4k + 3 \mid k \in \mathbb Z\}$.

Answer 2

1) reflexivity: $mFm $ since $4|0$

2) simmetry: $mFn \Rightarrow nFm$ since $4|\pm (m-n)$

3) transitivity: if $4|(m-n)$ and $4|(n-r)$ then $4|\big((m-n)+(n-r)\big)$ or $4|(m-r)$