2018 AMC 10A Problems/Problem 22

Revision as of 17:07, 8 February 2018 by Johnhankock (talk | contribs) (Solution)

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$?

$\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}$

Solution

We can say that a and b 'have' 2^3 * 3, that b and c have 2^2 * 3^2, and that c and d have 3^3 * 2. Combining 1 and 2 yields b has (at a minimum) 2^3 * 3^2, and thus a has 2^3 * 3 (and no more powers of 3 because otherwise the gcd(a,b) would be different). In addition, c has 3^3 * 2^2, and thus d has 3^3 * 2 (similar to a, we see that d cannot have any other powers of 2). We now assume 'worst case scenario', where a = 2^3 * 3 and d = 3^3 * 2. According to this base case, we have gcd(a, d) = 2 * 3 => 6. We want an extra factor between the two such that this number necessarily becomes between 70 and 100. Checking through, we see that 6 * 13 -> D is the only one that works.

Solution by JohnHankock