Problem:
Let a,b,c, and d be positive integers such that gcd(a,b)=24, gcd(b,c)=36,gcd(c,d)=54, and 70<gcd(d,a)<100. Which of the following must be a divisor of a?
Answer Choices:
A. 5
B. 7
C. 11
D. 13
E. 17
Solution:
Because gcd(a,b)=24=23⋅3 and gcd(b,c)=36= 22⋅32, it follows that a is divisible by 2 and 3 but not by 32. Similarly, because gcd(b,c)=22⋅32 and gcd(c,d)=54=2⋅33, it follows that d is divisible by 2 and 3 but not by 22. Therefore gcd(d,a)=2⋅3⋅n, where n is a product of primes that do not include 2 or 3. Because 70<gcd(d,a)<100 and n is an integer, it must be that 12≤n≤16, so n=13, and (D)13 must also be a divisor of a. The conditions are satisfied if a=23⋅3⋅13=312,b=23⋅32=72,c=22⋅33=108, and d=2⋅33⋅13=702.
The problems on this page are the property of the MAA's American Mathematics Competitions