Question

恰有 $77{,}000$ 个有序四元组 $(a,b,c,d)$ 满足 $\gcd(a,b,c,d)=77$ 且 $\text{lcm}(a,b,c,d)=n$ 。 $n$ 的最小可能值是多少？

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$

答案：D

知识点：最大公约数最小公倍数质因数分解

难度评级：2550

小提示：

全部除以 $77$ 。令 $m=\frac{n}{77}$ ，需要约化后的四元组最大公约数为 $1$ 、最小公倍数为 $m$ ，并逐质数分析。

Divide everything by $77.$ With $m=\frac{n}{77},$ you need reduced quadruples of gcd $1$ and lcm $m,$ analyzed one prime at a time

大提示：

对最大指数为 $M$ 的质数，指数四元组的数量为 $2(6M^2+1)$ 。分解 $77000$ ，确定有多少个质数整除 $m$ ，以及 $M$ 可以取哪些值

For a prime with maximum exponent $M,$ the count of exponent quadruples is $2(6M^2+1).$ Use the factorization of $77000$ to determine how many primes divide $m$ and which values of $M$ can occur

解答：

将每个数写成 $77$ 乘以一个约化值，我们需要 $\gcd=1$ 且 $\text{lcm}=m=\frac{n}{77}$ 。对每个整除 $m$ 且最大指数为 $M$ 的质数 $p$ ，有效指数四元组的个数为 $(M+1)^4-2M^4$ $+(M-1)^4$ $=2(6M^2+1)$ 。所有质数的贡献乘积必须等于 $77{,}000=2^3\cdot5^3\cdot7\cdot11$ 。当 $M=1,2,3$ 时， $2(6M^2+1)$ 分别等于 $14$ 、 $50$ 和 $110$ ，并且 $14\cdot50\cdot110=77{,}000$ ，所以指数 $1,2,3$ 给出一个候选分解。

每个质数恰好贡献一个因数 $2$ ，所以 $m$ 恰好有三个质因数。它们的奇数因子 $6M^2+1$ 必须整除 $\frac{77{,}000}{2^3}=9625$ 。检查这些因数得到 $M=1,2,3,8$ ，相应的奇数因子为 $7,25,55,385$ 。若取 $M=8$ ，其余两个奇数因子的乘积只能为 $25$ ，但每个至少为 $7$ ，不可能。因此最大指数恰为 $1,2,3$ 。为使 $m=\frac{n}{77}$ 最小，把最大指数分配给最小质数： $m=2^3\cdot3^2\cdot5=360$ ，所以 $n=77\cdot360=27{,}720$ 。

因此，正确答案是 D。

Writing each entry as $77$ times a reduced value, we need $\gcd=1$ and $\text{lcm}=m=\frac{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,$ the exponents $1,2,3$ give one candidate factorization.

Every prime contributes exactly one factor of $2,$ so exactly three primes divide $m.$ Their odd factors $6M^2+1$ must divide $\frac{77{,}000}{2^3}=9625.$ Checking the divisors gives $M=1,2,3,8,$ with odd factors $7,25,55,385.$ The choice $M=8$ leaves only $25$ for the product of the other two odd factors, but each is at least $7,$ so this is impossible. Therefore the maximum exponents are exactly $1,2,3.$ To minimize $m=\frac{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 第 24 题

答案：D

难度评级：2550

小提示：

大提示：

解答：

其他年份的第 24 题