# Showing an equivalence relation on $\mathbb Z$

Using the fact that \begin{align*}(a|b \ \land \ a|c) &\implies a|(b+c) \\ a|b &\implies a| bc \\ (a|b \ \land \ b|c) &\implies a|c \end{align*}

then I want to prove $$\equiv_d$$ is an equivalence relation on $$\mathbb Z$$ for every positive integer $$d$$

I'm pretty confused on this, but so far what I have done is attempt to show reflexivity and symmetry, but not yet transitivity and I don't know how to apply the predicates above. For reflexivity I said $$dRd \implies d-d \in \mathbb Z, d\in \mathbb Z^+$$, and since $$0\in \mathbb Z$$ then there is a reflexive relation. For symmetry I said if we take any $$k\in \mathbb Z$$, then $$dRk \implies kRd$$. So then $$d-k \in \mathbb Z, k-d \in \mathbb Z$$. Since $$d-k=c, k-d=-c$$ then symmetry is satisfied. And it is this point I don't know how to continue further.

• Are you asking about $\mathbf Z / d\mathbf Z$? Nov 1 '20 at 16:42
• I'm not sure, my prof. notes don't specify Nov 1 '20 at 16:43
• "Using only the fact that" are you sure you can only use the fact. I don't see any way to prove $a|a$ using only those facts, and we have no way of knowing whether $a|b$ in the first place for any $a|b$. For example, how can you prove $1|1$ or $2|4$ or $5\not \mid 7$ using "only" those facts? Nov 1 '20 at 16:53
• Well not "only", but as long as I use it then it works Nov 1 '20 at 16:54
• $(a-b) + (b-c) = a-c$. Nov 1 '20 at 17:11

Reflexive: For every $$a \in \mathbb Z$$, $$a\equiv a\pmod d$$.

Pf: $$d= 1\cdot d$$ so $$d|d$$. So $$d|d\times 0 = 0=a -a$$ for any $$a\in \mathbb Z$$. So $$a\equiv a \pmod d$$.

Definition of $$a\equiv a \pmod d$$ is that $$d|(a-a)$$ or in other words $$d|0$$. Does $$d|0$$?

Well $$d|d$$ so $$d|d\cdot 0=0=a-a$$. So yes it does. So $$d|a-a$$ so $$a \equiv a \pmod d$$ for all $$a\in \mathbb Z$$. So $$\equiv_d$$ is reflexive.

Symmetric: For every $$a,b \in \mathbb Z$$ where $$a\equiv b\pmod d$$ then $$b \equiv a \pmod d$$.

Proof: $$a\equiv b\pmod p$$ means $$d|a-b$$. So $$d|-1(a-b) = b-a$$. So that means $$b\equiv \pmod d$$. SO if $$a \equiv b \pmod d$$ then $$b\equiv a \pmod d$$. So $$\equiv_d$$ is symmetric.

Transitive. If $$a \equiv b\pmod d$$ and $$b\equiv c \pmod d$$ then $$a\equiv c\pmod d$$.

Proof. If $$a \equiv b \pmod d$$ then $$d|(a-b)$$. And if $$b\equiv c\pmod d$$ then $$d|(b-c)$$.

So $$d|(a-b) + (b-c) = a-c$$.

So $$a\equiv c \pmod d$$. So $$\equiv_d$$ is transitive.