0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Bram28 Mar 20 '18 at 17:20
  • 2
    $\begingroup$ 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$? $\endgroup$ – TrostAft Mar 20 '18 at 17:23
  • $\begingroup$ 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. $\endgroup$ – saulspatz Mar 20 '18 at 17:30
1
$\begingroup$

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.

$\endgroup$

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.