2022 AMC 10A Problem 7

P1-10~2 minPrint

GCD & LCM Primes Set up the equation/formula and compute; no special trick needed

The least common multiple of a positive integer $n$ and $18$ is $180$ , and the greatest common divisor of $n$ and $45$ is $15$ . What is the sum of the digits of $n$ ?

Show solution without answering

Key insight

Break every number into primes. The lcm condition says n has two 2s and one 5; the gcd condition says n has exactly one 3.

Solution

The least common multiple and greatest common divisor both work one prime at a time, so break everything into primes first.

1. Prime factors. $18 = 2 \cdot 3^2$ , $\ 180 = 2^2 \cdot 3^2 \cdot 5$ , $\ 45 = 3^2 \cdot 5$ , $\ 15 = 3 \cdot 5$ .
2. What n can contain. $180$ is a multiple of $n$ , so $n$ is built only from $2$ s, $3$ s and $5$ s, and has no more of each than $180$ has.
3. The lcm condition. For each prime, the lcm uses the larger count from $n$ and $18$ .
- Twos: $18$ has one $2$ , but $180$ has two. The extra $2$ must come from $n$ , so $n$ has exactly two $2$ s.
- Fives: $18$ has no $5$ , but $180$ has one, so $n$ has exactly one $5$ .
- Threes: $18$ already has two $3$ s, so this condition tells us nothing about the $3$ s in $n$ .
4. The gcd condition. For each prime, the gcd uses the smaller count. $45$ has two $3$ s, but the gcd $15$ has only one. So $n$ has exactly one $3$ . (With no $3$ s the gcd would have none; with two $3$ s it would have two.)
5. Put it together. $n = 2^2 \cdot 3 \cdot 5 = 60$ . Check: $\operatorname{lcm}(60, 18) = 180$ and $\gcd(60, 45) = 15$ .
6. The digit sum of $60$ is $6 + 0 = 6$ .

The answer is $\boxed{\textbf{(B)}\ 6}$ .

Why this works

The lcm takes the larger power of each prime and the gcd takes the smaller one. So when a problem mixes the two, write every number in primes and settle one prime at a time. Here each condition fixed a different prime, and together they pinned $n$ down.

Alternative approach

List the candidates. Since $\gcd(n, 45) = 15$ , $n$ is a multiple of $15$ but not a multiple of $9$ . The multiples of $15$ that divide $180$ are $15, 30, 45, 60, 90, 180$ ; removing the multiples of $9$ leaves $15, 30, 60$ . For the lcm with $18$ to be $180$ , $n$ must be a multiple of $4$ , and only $60$ is.

Concise solution

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

Factor everything: $18 = 2 \cdot 3^2$ , $180 = 2^2 \cdot 3^2 \cdot 5$ , $45 = 3^2 \cdot 5$ , $15 = 3 \cdot 5$ . Write $n = 2^a 3^b 5^c$ (no other primes can appear, since $n$ divides $180$ ).

From $\operatorname{lcm}(n, 18) = 180$ : the exponent of $2$ in the lcm is $\max(a, 1) = 2$ , so $a = 2$ ; the exponent of $5$ is $\max(c, 0) = 1$ , so $c = 1$ ; and $\max(b, 2) = 2$ , so $b \le 2$ .

From $\gcd(n, 45) = 15$ : the exponent of $3$ is $\min(b, 2) = 1$ , so $b = 1$ (and $\min(c, 1) = 1$ confirms $c = 1$ ).

Therefore $n = 2^2 \cdot 3 \cdot 5 = 60$ , whose digit sum is $6 + 0 = 6$ .

The answer is $\boxed{\textbf{(B)}\ 6}$ .

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 4: Prime Factorization (§4.7)