2018 AMC 10A Problem 22

P21-25~6 minPrint

GCD & LCM Divisibility & Factors Primes Use the answer choices (mod checks, size, form) to eliminate or select Bound the quantity above/below or estimate to pin it down

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

Show solution without answering

Key insight

Follow the 2s and 3s along the chain. The gcd of d and a has exactly one 2 and one 3, which forces it to be 78.

Solution

The greatest common divisor (gcd) of two numbers takes each prime as many times as the number with fewer copies of it has. So follow the primes $2$ and $3$ around the chain $a, b, c, d$ .

1. Break the gcds into primes.
$24 = 2^3 \cdot 3, \qquad 36 = 2^2 \cdot 3^2, \qquad 54 = 2 \cdot 3^3.$
2. Follow the $2$ s.
- $\gcd(a, b) = 24$ has three $2$ s, so $a$ and $b$ each have at least three $2$ s.
- $\gcd(b, c) = 36$ has only two $2$ s. Since $b$ has at least three, $c$ must have exactly two.
- $\gcd(c, d) = 54$ has only one $2$ . Since $c$ has two, $d$ must have exactly one.
- So $d$ has exactly one $2$ and $a$ has at least three. Their gcd has exactly one $2$ .
3. Follow the $3$ s.
- $\gcd(b, c) = 36$ has two $3$ s, so $b$ has at least two.
- $\gcd(a, b) = 24$ has only one $3$ . Since $b$ has at least two, $a$ must have exactly one.
- $\gcd(c, d) = 54$ has three $3$ s, so $d$ has at least three.
- So $a$ has exactly one $3$ and $d$ has at least three. Their gcd has exactly one $3$ .
4. So $\gcd(d, a) = 6 \times (\text{a number with no factor } 2 \text{ or } 3)$ . Check the multiples of $6$ between $70$ and $100$ :

$\gcd(d,a)$	$72$	$78$	$84$	$90$	$96$
divided by $6$	$12$	$13$	$14$	$15$	$16$
has a $2$ or $3$ ?	yes	no	yes	yes	yes

Only $78 = 6 \cdot 13$ is allowed.
5. Conclude. $\gcd(d, a) = 78$ divides $a$ , so $13$ divides $a$ .

Such numbers really exist, for example $a = 312$ , $b = 72$ , $c = 108$ , $d = 702$ .

The answer is $\boxed{\textbf{(D)}\ 13}$ .

Why this works

A gcd works one prime at a time: it keeps the smaller count of each prime. When two gcds next to each other in the chain disagree about how many $2$ s (or $3$ s) there are, the number they share has the larger count and the other number is pinned down exactly. Once the counts of $2$ and $3$ are fixed, the range $70$ to $100$ leaves only one choice.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Factor the given gcds: $24 = 2^3 \cdot 3$ , $36 = 2^2 \cdot 3^2$ , $54 = 2 \cdot 3^3$ . The gcd's exponent of a prime is the smaller of the two exponents, so track $2$ and $3$ through the chain $a, b, c, d$ .

Powers of $2.$ $\gcd(a,b)$ has $2^3$ but $\gcd(b,c)$ has only $2^2$ , so $b$ has at least $2^3$ and $c$ has exactly $2^2$ . Then $\gcd(c,d)$ having $2^1$ forces $d$ to have exactly $2^1$ . Meanwhile $a$ has at least $2^3$ . So $\gcd(d,a)$ has exactly $2^1$ .

Powers of $3.$ $\gcd(b,c)$ has $3^2$ but $\gcd(a,b)$ has only $3^1$ , so $b$ has at least $3^2$ and $a$ has exactly $3^1$ . Also $\gcd(c,d) = 3^3$ means $d$ has at least $3^3$ . So $\gcd(d,a)$ has exactly $3^1$ .

Hence $\gcd(d,a) = 6k$ with $k$ coprime to $6$ . The multiples of $6$ strictly between $70$ and $100$ are $72, 78, 84, 90, 96$ , and dividing by $6$ gives $12, 13, 14, 15, 16$ . Only $13$ is coprime to $6$ , so $\gcd(d,a) = 78 = 2 \cdot 3 \cdot 13$ , and $13$ divides $a$ .

(Such numbers exist, e.g. $a = 2^3 \cdot 3 \cdot 13$ , $b = 2^3 \cdot 3^2$ , $c = 2^2 \cdot 3^3$ , $d = 2 \cdot 3^3 \cdot 13$ .)

The answer is $\boxed{\textbf{(D)}\ 13}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 3: Multiples and Divisors (§3.3, §3.4, §3.7)
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.7)