Proof of Equivalence Relation $R=\{(a,b)\in\Bbb N^2: 5\mid (2a+3b)\}$

Given a set of natural numbers ($\Bbb N$), and the relation $R=\{(a,b)\in\Bbb N^2: 5\mid (2a+3b)\}$. Is $R$ an equivalent relation?

My answer: Yes, because $2a + 3b$ is divisible by $5$, if and only if, $2a + 3b − 5b$ is divisible by $5$.

Is my reasoning right?

If it is not, then how do I prove that this is an equivalent relation?

Solution 1:

For future reference, you can prove that something is an equivalence relation like this:

Reflexivity: For all $a\in \Bbb N$, $2a+3a = 5a$ is divisible by $5$. Hence, $a\sim a$.

Symmetry: Consider $a,b\in \Bbb N$. If $a\sim b$, then $2a+3b = 5k$ for some $k \in \Bbb N$. Then \begin{align} 3a + 2b &= (5a + 5b) - (2a + 3b)\\ &= 5(a+b) - 5k\\ &= 5(a+b-k) \end{align} So if $a\sim b$, then $b\sim a$.

Transitivity: Consider $a,b,c\in \Bbb N$. If $a\sim b$ and $b\sim c$, then $2a + 3b$ and $2b+3c$ are both divisible by $5$. That is, $\exists k,\ell \in \Bbb N$ such that $2a+3b = 5k$ and $2b + 3c = 5\ell$. Then \begin{align}5k + 5\ell &= (2a+3b) + (2b + 3c)\\ &=2a + 3c + 5b\end{align} So we may write $2a + 3c = 5(k + \ell - b)$. Thus, if $a\sim b$ and $b\sim c$, then $a\sim c$.

Solution 2:

Assuming $0\in\Bbb N$, we can extend your reasoning:

$$a~R~b\iff 5\mid 2a+3b\iff 5\mid 2a+3b-5b=2(a-b)\overset{\gcd(2,5)=1}{\iff} 5\mid a-b$$

and $-$ is an equivalence relation on $\Bbb N$.

Even more, it is a congruence relation which is an equivalence relation satisfying $$a~R~b\quad\textrm{and}\quad c~R~d\implies a+c~R~b+d$$

Solution 3:

We have the well-known modulo 5 equivalence relation defined on $\mathbb N$; denote it by $M$ so that we can compare it with the OP's $R$.

Both the relations $M$ and $R$ are exactly the same when restricted to $C = \{0,1,2,3,4\}$, both being identical to the equality relation, i.e. the diagonal subset of $C \times C$.

Suppose we have $a R b$ is true but $a M b$ is not true for number $a$ and $b$. Then we can select $a$ and $b$ so that the sum is a minimum. But then either $a$ or $b$ must be strictly greater than $4$; suppose $a$ is. Then $(a - 5) R b$ is also true and $(a - 5) M b$ is false, a contradiction. Nothing changes if we assume that $b \gt 4$.

We can argue in the same way when $a R b$ is false and $a M b$ is true.

So both $R$ and $M$ represent the same relation on $\mathbb N$.