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!=23⋅3⋅55! = 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)=5⋅gcd⁡(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 3≤a≤83 \le a \le 8 gives 66 values. For 3:3: max⁡(1,b)=min⁡(4,b),\max(1, b) = \min(4, b), so 1≤b≤41 \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 c≥1,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 6⋅4⋅1⋅2=48.6 \cdot 4 \cdot 1 \cdot 2 = 48. Thus, D is the correct answer.
AoPS wiki

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

More practice