Skip to main content

2018 AMC 10A Problem 22

Problem 22 of 25HarderAlgebraNumber Theory

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=233\gcd(a,b)=24=2^3\cdot3 and gcd(b,c)=36=2232\gcd(b,c)=36=2^2\cdot3^2, the number aa is divisible by 2332^3\cdot3 but not by 323^2. From gcd(b,c)=36\gcd(b,c)=36 and gcd(c,d)=54=233\gcd(c,d)=54=2\cdot3^3, the number dd is divisible by 2332\cdot3^3 but not by 222^2. Therefore gcd(d,a)=23n\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 12n16.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.

More practice

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

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.