2020 AMC 12A Problem 21

Question

How many positive integers

n

are there such that

n

is a multiple of

5,

and the least common multiple of

5!

and

n

equals

5

times the greatest common divisor of

10!

and

n?

12

24

36

48

72

Answer: D

Concepts:least common multiple greatest common divisor prime factorization

Difficulty rating: 2080

Small hint:

5! = 2^3 \cdot 3 \cdot 5

and

10! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7;

compare exponents of each prime

Big hint:

Multiplying the gcd by

5

raises the power of

5

by one; work out the allowed exponent of each prime in

n

Solution:

Write

n = 2^a 3^b 5^c 7^d \cdots.

Since

5! = 2^3 \cdot 3 \cdot 5

has no other primes,

n

can only involve

2, 3, 5, 7.

Matching exponents in

\operatorname{lcm}(5!, n) = 5 \cdot \gcd(10!, n):

For

2:

\max(3, a) = \min(8, a),

so

3 \le a \le 8

gives

6

values. For

3:

\max(1, b) = \min(4, b),

so

1 \le b \le 4

gives

4

values.

For

5:

\max(1, c) = 1 + \min(2, c)

with

c \ge 1,

which forces

c = 3,

giving

1

value. For

7:

\max(0, d) = \min(1, d),

so

d = 0

or

1,