# Difference between revisions of "2018 AMC 10A Problems/Problem 22"

Ishankhare (talk | contribs) (Created page with "Let <math>a, b, c,</math> and <math>d</math> be positive integers such that <math>\gcd(a, b)=24</math>, <math>\gcd(b, c)=36</math>, <math>\gcd(c, d)=54</math>, and <math>70<\g...") |
Johnhankock (talk | contribs) |
||

Line 2: | Line 2: | ||

<math>\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}</math> | <math>\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}</math> | ||

+ | |||

+ | == 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 -> B is the only one that works. | ||

+ | |||

+ | Solution by JohnHankock |

## Revision as of 16:49, 8 February 2018

Let and be positive integers such that , , , and . Which of the following must be a divisor of ?

## 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 -> B is the only one that works.

Solution by JohnHankock