Question

There are exactly $77{,}000$ ordered quadruples $(a,b,c,d)$ such that $\gcd(a,b,c,d)=77$ and $\text{lcm}(a,b,c,d)=n.$ What is the smallest possible value of $n?$

$13{,}860$

$20{,}790$

$21{,}560$

$27{,}720$

$41{,}580$

Solution:

Writing each entry as $77$ times a reduced value, we need $\gcd=1$ and $\text{lcm}=m=n/77.$ For each prime $p$ dividing $m$ with maximum exponent $M,$ the number of valid exponent quadruples is $(M+1)^4-2M^4+(M-1)^4=2(6M^2+1).$ The total over all primes must equal $77{,}000=2^3\cdot5^3\cdot7\cdot11.$ Since $2(6M^2+1)$ equals $14,$ $50,$ and $110$ for $M=1,2,3,$ and $14\cdot50\cdot110=77{,}000,$ exactly three primes divide $m,$ with maximum exponents $1,2,3.$ To minimize $m=n/77,$ assign the largest exponent to the smallest prime: $m=2^3\cdot3^2\cdot5=360,$ so $n=77\cdot360=27{,}720.$

Thus, the correct answer is D.

2016 AMC 12B Problem 24

Solution:

Problem 24 in Other Years