# proving that a relation is Equivalence relation

I am new user here and I have tried to put my question at the right topic as it says in the rules, so let's get started.

I am required to prove the following: the relation is defined on the $\mathbb{Z}$.

$R = \{(x,y) \in \mathbb{R} \mid k|(ax+by)\}$

$a,b,k \in \mathbb{Z}$.

The question is what $k$ is needed to be for the relation to be an equivalence relation.

So after long thought I have come to the conclusion that $k$ should be the $\gcd(a,b)$ for this to be an equivalence relation.

I am trying to show reflexive, let's say $a = 3$, $b = 5$, $\gcd(3,5) = 1$: $(x,x) \in \mathbb{R}$ $\ \leadsto \$ $3x+5x = \gcd(3,5)\cdot n$ $\ \leadsto \$ $8x = 1 \cdot n$.

Now how can I show that the relation is reflexive? (the rest of the properties I want to try myself)

From the definition of $a|b$ $\ \leadsto \$ $b = a \cdot c$.

• All kind of things can be pointed to as being needed. For example, $k$ needs to be an integer. Likewise, I don't think that $k$ 'should be' or needs to be $gcd(a,b)$. For example, $k=1$ will work just fine – Bram28 Mar 20 '18 at 17:20
• If you choose $k = gcd(a,b)$ doesn't that imply that $k | (ax + by), \forall x,y \in \mathbb{Z}$? Since $k | a$ and $k | b$? – TrostAft Mar 20 '18 at 17:23
• It seems to me that what you want to be asking is, "Given $a$ and $b,$ what are necessary and sufficient conditions on $k$ so that $R$ is an equivalence relation." If this is so, then $k=\gcd(a,b)$ is incorrect, as Bram28's comment shows. – saulspatz Mar 20 '18 at 17:30

As I said in a comment, I think the question you're trying to ask is "Given $a$ and $b$, what are necessary and sufficient conditions on $k$ so that $R$ is an equivalence relation."
On this understanding, let me get you started. For reflexivity we need $\forall x(k|(ax+bx)).$ Now for any $k,$ we can choose an $x$ coprime to $k,$ say $x=k+1,$ and in order for $k|(a+b)(k+1)$ we need $k|(a+b).$ On the other hand if $k|(a+b)$ then surely $k|(a+b)x$ so $k|(a+b)$ is a necessary and sufficient condition for $R$ to be reflexive.
Now you have to check symmetry and transitivity. Is $k|(a+b)$ sufficient, or do we need stronger conditions? Notice that sufficiency, if true, is enough. We don't have to worry about necessity in that case, because we already know that $k|(a+b)$ is necessary for reflexivity, so it's necessary for $R$ to be an equivalence relation. On the other hand, if $k|(a+b)$ is not sufficient to infer symmetry and reflexivity, then you have to worry about necessity again.