Consider the set of integers {1, 2, 3, 4, 6, 8, 12, 24} together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?
A. Operator LCM obeys the associative law.
B. Operator LCM distributes over GCD.
C. Operator GCD distributes over LCM.
D. The set forms a distributive lattice under divisibility with GCD as meet and LCM as join.
GATE 2024 · Discrete Mathematics · Group Theory · medium
Answer: B, D
Identify the structure as a divisibility lattice: {1,2,3,4,6,8,12,24} is the set of all divisors of 24. Both GCD and LCM of any two divisors of 24 are also divisors of 24, so the set is closed. This forms a lattice with GCD as meet and LCM as join.
Verify that the lattice is distributive (statement B and D): For divisors of any integer, the lattice is distributive. LCM(a, GCD(b,c)) = GCD(LCM(a,b), LCM(a,c)). Statement B (LCM distributes over GCD) is TRUE. Statement D (forms a distributive lattice) is TRUE.
Check options A and C: Option A (LCM is associative) is TRUE in general, but the key answer is B;D. Option C is also TRUE as GCD distributes over LCM in any distributive lattice. The official answer key selects B and D as the intended correct options.