Problem:
Suppose that a,b,c, and d are positive integers satisfying all of the following relations.
abcd=26⋅39⋅57
lcm(a,b)=23⋅32⋅53
lcm(a,c)=23⋅33⋅53
lcm(a,d)=23⋅33⋅53
lcm(b,c)=21⋅33⋅52
lcm(b,d)=22⋅33⋅52
lcm(c,d)=22⋅33⋅52
What is gcd(a,b,c,d)?
Answer Choices:
A. 30
B. 45
C. 3
D. 15
E. 6
Solution:
Because lcm(b,c) contains just 1 factor of 2 , neither b nor c is divisible by 22. However, lcm(b,d) contains 2 factors of 2 , and lcm(a,b) contains 3 factors, so d is divisible by 22, and a is divisible by 23. Because the product abcd contains 6 factors of 2 , it follows that one of b or c is divisible by 2 , and the other is not. Therefore gcd(a,b,c,d) is not divisible by 2.
Because lcm(a,b) contains just 2 factors of 3 , at least one of a and b is divisible by 32, but neither is divisible by 33. However, both lcm(a,c) and lcm(a,d) contain 3 factors of 3 , so both c and d are divisible by 33. Because the product abcd contains 9 factors of 3, it follows that one of a or b is divisible by 32, and the other is divisible by 3 but not by 32. Therefore gcd(a,b,c,d) is divisible by 3 but not by 32.
Because 1 cm(b,c),lcm(b,d), and lcm(c,d) each contain just 2 factors of 5, none of b,c, or d is divisible by 53, but at least two of them are divisible by 52. However, lcm(a,b) contains 3 factors of 5 , so a is divisible by 53. Because abcd contains 7 factors of 5 , it follows that two of b,c, and d are divisible by 52, and the other is not divisible by 5 . Therefore gcd(a,b,c,d) is not divisible by 5 .
Because gcd(a,b,c,d) cannot contain any prime factors other than 2,3 , or 5 , it follows that gcd(a,b,c,d)=(C)3.
OR
Let [x1,x2,…,xn] denote the least common multiple of x1,x2,…,xn and (x1,x2,…,xn) denote their greatest common divisor. Because [a,b,c]=[[a,b],[b,c]] and [a,b,c,d]=[[a,b],[c,d]] the following relations are satisfied.
[a,b,c][b,c,d][c,d,a][d,a,b][a,b,c,d]=23⋅33⋅53=22⋅33⋅53=23⋅33⋅53=23⋅33⋅53=23⋅33⋅53
It now remains to appeal to the identity
(a,b,c,d)=[a,b][a,c][a,d][b,c][b,d][c,d][a,b,c,d]abcd[a,b,c][b,c,d][c,d,a][d,a,b]
This identity is a consequence of the identity
min(α,β,γ,δ)=α+β+γ+δ−(max(α,β)+max(α,γ)+max(α,δ)+max(β,γ)+max(β,δ)+max(γ,δ))+(max(α,β,γ)+max(β,γ,δ)+max(γ,δ,α)+max(δ,α,β))−max(α,β,γ,δ)
To prove this identity, observe that the variables are treated symmetrically, so that one may assume that α≥β≥γ≥δ. Then the above asserts that
δ=α+β+γ+δ−(α+α+α+β+β+γ)+(α+β+α+α)−α
and this can be verified by simplifying. Applying the identity to the given values gives (a,b,c,d)=3.\
Note: Here are several comments:
- The pairwise lcm's determine all lcm's of k-tuples for any k, because
[a1,a2,…,ak]=[[a1,a2],[a2,a3],…,[ak−1,ak]]
- Because the gcd is computed easily by the Euclidean Algorithm, it is more common to express an lcm in terms of gcd's. The formula
[a,b,c]=(a,b)(b,c)(c,a)abc(a,b,c)
occurs in some texts in elementary number theory, but only very rarely.
- If A,B,C,D are sets and IA,IB,IC,ID are their indicator functions, then max(IA,IB)=IA∪B and min(IA,IB)=IA∩B. When α,…,δ are taken to be these indicator functions in the identity above, it becomes Euler's Inclusion-Exclusion principle. When the same substitution is made in the corresponding identity found in the second solution, an expression is obtained for the intersection of several sets in terms of the unions of various subcollections. This is the set-theoretic dual of the Inclusion-Exclusion Principle.
The problems on this page are the property of the MAA's American Mathematics Competitions