Skip to main content

2018 AMC 10A Problem 22

Problem 22 of 25HarderNumber TheoryProblem-Solving Techniques

Let a,a, b,b, c,c, and dd be positive integers such that gcd⁡(a,b)=24,\gcd(a, b)=24, gcd⁡(b,c)=36,\gcd(b, c)=36, gcd⁡(c,d)=54,\gcd(c, d)=54, and 70<gcd⁡(d,a)<100.70 < \gcd(d, a) < 100. Which of the following must be a divisor of a?a?

Answer choices

Show solution

Solution

From gcd⁡(a,b)=24=23⋅3\gcd(a,b)=24=2^3\cdot3 and gcd⁡(b,c)=36=22⋅32\gcd(b,c)=36=2^2\cdot3^2, the number aa is divisible by 23⋅32^3\cdot3 but not by 323^2. From gcd⁡(b,c)=36\gcd(b,c)=36 and gcd⁡(c,d)=54=2⋅33\gcd(c,d)=54=2\cdot3^3, the number dd is divisible by 2⋅332\cdot3^3 but not by 222^2. Therefore gcd⁡(d,a)=2⋅3⋅n\gcd(d,a)=2\cdot3\cdot n, where nn has no factor 22 or 33. Since 70<6n<100,70<6n<100, the integer nn satisfies 12≤n≤16.12\le n\le16. The only value in this range with no factor 22 or 33 is 13,13, so 1313 must divide a.a. Thus, D is the correct answer.
AoPS wiki

Tagged: greatest common divisor · prime factorization · bounding to limit cases

More practice