[proofplan] We use the definition of congruence modulo $n$: for integers $x,y \in \mathbb{Z}$, the assertion $x \equiv y \pmod{n}$ means that $n \mid (x-y)$. Each [equivalence relation](/page/Equivalence%20Relation) property is then a direct divisibility calculation in $\mathbb{Z}$. Reflexivity comes from $a-a=0$, symmetry from negating an integer multiple of $n$, and transitivity from adding two integer multiples of $n$. [/proofplan] [step:Translate congruence into divisibility] For integers $x,y \in \mathbb{Z}$, we will use the defining equivalence \begin{align*} x \equiv y \pmod{n} \quad \text{if and only if} \quad n \mid (x-y). \end{align*} Here $n \mid (x-y)$ means that there exists an integer $k \in \mathbb{Z}$ such that \begin{align*} x-y = nk. \end{align*} Thus proving that two integers are congruent modulo $n$ is exactly proving that their difference is an integer multiple of $n$. [/step] [step:Prove reflexivity by writing every difference $a-a$ as a multiple of $n$] Let $a \in \mathbb{Z}$. Since $0 \in \mathbb{Z}$ and \begin{align*} a-a = 0 = n \cdot 0, \end{align*} we have $n \mid (a-a)$. Therefore \begin{align*} a \equiv a \pmod{n}. \end{align*} So $\sim_n$ is reflexive. [/step] [step:Prove symmetry by negating the integer multiple] Let $a,b \in \mathbb{Z}$ and assume \begin{align*} a \equiv b \pmod{n}. \end{align*} By the definition of congruence modulo $n$, there exists an integer $k \in \mathbb{Z}$ such that \begin{align*} a-b = nk. \end{align*} Multiplying both sides by $-1$ gives \begin{align*} b-a = n(-k). \end{align*} Since $-k \in \mathbb{Z}$, this shows that $n \mid (b-a)$. Hence \begin{align*} b \equiv a \pmod{n}. \end{align*} Therefore $\sim_n$ is symmetric. [guided] Let $a,b \in \mathbb{Z}$ and suppose that $a$ is congruent to $b$ modulo $n$. The definition of congruence says that this is not a new algebraic operation; it is a divisibility statement: \begin{align*} a \equiv b \pmod{n} \quad \text{means} \quad n \mid (a-b). \end{align*} By the definition of divisibility in $\mathbb{Z}$, there is an integer $k \in \mathbb{Z}$ such that \begin{align*} a-b = nk. \end{align*} To prove symmetry, we must prove $b \equiv a \pmod{n}$, which means we must show that $b-a$ is also an integer multiple of $n$. Since $b-a$ is the negative of $a-b$, we multiply the displayed equality by $-1$: \begin{align*} b-a = -(a-b) = -nk = n(-k). \end{align*} Because $k \in \mathbb{Z}$ and $\mathbb{Z}$ is closed under additive inverses, we have $-k \in \mathbb{Z}$. Therefore $b-a$ is an integer multiple of $n$, so $n \mid (b-a)$, and hence \begin{align*} b \equiv a \pmod{n}. \end{align*} This proves symmetry of $\sim_n$. [/guided] [/step] [step:Prove transitivity by adding the two integer multiples] Let $a,b,c \in \mathbb{Z}$ and assume \begin{align*} a \equiv b \pmod{n} \end{align*} and \begin{align*} b \equiv c \pmod{n}. \end{align*} By the definition of congruence modulo $n$, there exist integers $k,\ell \in \mathbb{Z}$ such that \begin{align*} a-b = nk \end{align*} and \begin{align*} b-c = n\ell. \end{align*} Adding these two equalities gives \begin{align*} a-c = (a-b)+(b-c) = nk+n\ell = n(k+\ell). \end{align*} Since $k+\ell \in \mathbb{Z}$, we have $n \mid (a-c)$. Therefore \begin{align*} a \equiv c \pmod{n}. \end{align*} So $\sim_n$ is transitive. [/step] [step:Conclude that congruence modulo $n$ is an equivalence relation] We have shown that for all $a,b,c \in \mathbb{Z}$, the relation $\sim_n$ is reflexive, symmetric, and transitive. Therefore $\sim_n$, equivalently congruence modulo $n$, is an equivalence relation on $\mathbb{Z}$. [/step]