Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
A. R is symmetric and reflexive but not transitive
B. R is reflexive but not symmetric and not transitive
C. R is transitive but not symmetric
D. R is symmetric but neither reflexive nor transitive
GATE 2015 · Discrete Mathematics · Relations · medium
Answer: R is symmetric but neither reflexive nor transitive. Answer: D. R is symmetric but neither reflexive nor transitive.
Test reflexivity: For aRa to hold, a must be distinct from a, which is never true. So aRa NEVER holds for any positive integer a. R is NOT reflexive.
Test symmetry: If aRb then a != b and gcd(a,b) > 1. Since gcd(a,b) = gcd(b,a) and b != a, we have bRa. So R IS symmetric.
Test transitivity with counterexample: Take a=2, b=6, c=9. gcd(2,6)=2>1 and 2!=6, so 2R6. gcd(6,9)=3>1 and 6!=9, so 6R9. But gcd(2,9)=1, so 2 NOT R 9. Transitivity FAILS.