Skip to main content

2020 AMC 12A Problem 21

Problem 21 of 25HarderNumber Theory

How many positive integers nn are there such that nn is a multiple of 5,5, and the least common multiple of 5!5! and nn equals 55 times the greatest common divisor of 10!10! and n?n?

Answer choices

Show solution

Solution

Write n=2a3b5c7d.n = 2^a 3^b 5^c 7^d \cdots. Since 5!=23355! = 2^3 \cdot 3 \cdot 5 has no other primes, nn can only involve 2,3,5,7.2, 3, 5, 7. Matching exponents in lcm(5!,n)=5gcd(10!,n):\operatorname{lcm}(5!, n) = 5 \cdot \gcd(10!, n): For 2:2: max(3,a)=min(8,a),\max(3, a) = \min(8, a), so 3a83 \le a \le 8 gives 66 values. For 3:3: max(1,b)=min(4,b),\max(1, b) = \min(4, b), so 1b41 \le b \le 4 gives 44 values. For 5:5: max(1,c)=1+min(2,c)\max(1, c) = 1 + \min(2, c) with c1,c \ge 1, which forces c=3,c = 3, giving 11 value. For 7:7: max(0,d)=min(1,d),\max(0, d) = \min(1, d), so d=0d = 0 or 1,1, giving 22 values. The total is 6412=48.6 \cdot 4 \cdot 1 \cdot 2 = 48. Thus, D is the correct answer.

More practice

Concepts: least common multiple · greatest common divisor · prime factorization

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.