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.

  • $\begingroup$ Are you asking about $\mathbf Z / d\mathbf Z$? $\endgroup$ Nov 1 '20 at 16:42
  • $\begingroup$ I'm not sure, my prof. notes don't specify $\endgroup$
    – Lex_i
    Nov 1 '20 at 16:43
  • $\begingroup$ "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? $\endgroup$
    – fleablood
    Nov 1 '20 at 16:53
  • $\begingroup$ Well not "only", but as long as I use it then it works $\endgroup$
    – Lex_i
    Nov 1 '20 at 16:54
  • $\begingroup$ $(a-b) + (b-c) = a-c$. $\endgroup$
    – fleablood
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.