GATE CS 2015 Set 2 — Question 13

Let $S$ be the set of positive integers.
$R$ is a relation on $S$ such that $aRb$ if and only if $a$ and $b$ are distinct and have a common divisor other than 1.Let's check the properties of $R$: Consider $a=2$, $b=4$, $c=6$.
$aRb$: $2$ and $4$ are distinct, and have a common divisor $2 > 1$. So, $2R4$ is true.
$bRc$: $4$ and $6$ are distinct, and have a common divisor $2 > 1$. So, $4R6$ is true.
Now, let's check $aRc$: $2$ and $6$ are distinct, and have a common divisor $2 > 1$. So, $2R6$ is true.
This example suggests transitivity might hold. However, we need to be careful with the 'distinct' condition. Let's try another example:
Consider $a=2$, $b=4$, $c=8$.
$aRb$: $2$ and $4$ are distinct, common divisor $2 > 1$. True.
$bRc$: $4$ and $8$ are distinct, common divisor $4 > 1$. True.
$aRc$: $2$ and $8$ are distinct, common divisor $2 > 1$. True. Let's try to find a counterexample for transitivity.
Suppose $aRb$ and $bRc$.
This means $a \neq b$, $b \neq c$.
There exists $d_1 > 1$ such that $d_1 | a$ and $d_1 | b$.
There exists $d_2 > 1$ such that $d_2 | b$ and $d_2 | c$. We need to check if $aRc$ is true, i.e., $a \neq c$ and there exists $d_3 > 1$ such that $d_3 | a$ and $d_3 | c$. Consider $a=2$, $b=6$, $c=3$.
$aRb$: $2$ and $6$ are distinct, common divisor $2 > 1$. True.
$bRc$: $6$ and $3$ are distinct, common divisor $3 > 1$. True.
Now, check $aRc$: $2$ and $3$ are distinct. Do they have a common divisor greater than 1? No, their only common divisor is 1. So, $2R3$ is false.
Therefore, $R$ is not transitive.Combining these findings:

• $R$ is not reflexive.
• $R$ is symmetric.
• $R$ is not transitive.

This matches option (D).