Question

定义有理数列 $x_1$ 、 $x_2$ 、 $\ldots$ ，其中 $x_1 = \frac{25}{11}$ ，且 $x_{k+1} = \frac{1}{3}\left(x_k + \frac{1}{x_k} - 1\right)$ 对所有 $k \ge 1$ 成立。则 $x_{2025}$ 可表示为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $m + n$ 除以 $1000$ 的余数。

Let the sequence of rationals $x_1,$ $x_2,$ $\ldots$ be defined such that $x_1 = \frac{25}{11}$ and $x_{k+1} = \frac{1}{3}\left(x_k + \frac{1}{x_k} - 1\right)$ for all $k \ge 1.$ Then $x_{2025}$ can be expressed as $\frac{m}{n}$ for relatively prime positive integers $m$ and $n.$ Find the remainder when $m + n$ is divided by $1000.$

答案

答案：248

知识点：递推换元法中国剩余定理模幂运算

难度评级：3370

小提示：

代换 $y_k = \frac{2x_k - 1}{x_k + 1}$ 会把递推变成 $y_{k+1} = y_k^2 - y_k$ ，且 $y_1 = \frac{13}{12}$

The substitution $y_k = \frac{2x_k - 1}{x_k + 1}$ turns the recurrence into $y_{k+1} = y_k^2 - y_k,$ with $y_1 = \frac{13}{12}$

大提示：

写 $y_k = \frac{c_k}{12^{2^{k-1}}}$ ，证明 $x_k = \frac{d + c}{2d - c}$ 已经是最简分数，所以 $m + n = 3d$

Writing $y_k = \frac{c_k}{12^{2^{k-1}}},$ show $x_k = \frac{d + c}{2d - c}$ is already in lowest terms, so $m + n = 3d$

解答：

令 $y_k = \frac{2x_k - 1}{x_k + 1}$ 。由递推式， $2x_{k+1} - 1 = \frac{(2x_k - 1)(x_k - 2)}{3x_k}$ ，并且 $x_{k+1} + 1 = \frac{(x_k + 1)^2}{3x_k}$ ，所以 $\begin{gathered} y_{k+1} = \frac{(2x_k - 1)(x_k - 2)}{(x_k + 1)^2} \\ = y_k(y_k - 1) = y_k^2 - y_k \end{gathered}\text{，}$ 因为 $y_k - 1 = \frac{x_k - 2}{x_k + 1}$ 。这里 $y_1 = \frac{\frac{39}{11}}{\frac{36}{11}} = \frac{13}{12}$ 。归纳可得 $y_k = \frac{c_k}{12^{2^{k-1}}}$ ，其中 $c_1 = 13$ 且 $c_{k+1} = c_k\bigl(c_k - 12^{2^{k-1}}\bigr)$ ；由于 $12^{2^{k-1}}$ 可被 $6$ 整除，每个 $c_k$ 都与 $6$ 互质。

反解代换， $x_k = \frac{1 + y_k}{2 - y_k} = \frac{d + c}{2d - c}$ ，其中 $d = 12^{2^{k-1}}$ 且 $c = c_k$ 。所有 $x_k$ 都为正（当 $x \gt 0$ 时， $x + \frac{1}{x} - 1 \ge 1$ ），所以 $y_k = \frac{2x_k - 1}{x_k + 1} \in (-1, 2)$ ，使得 $d + c$ 和 $2d - c$ 均为正。 $d + c$ 与 $2d - c$ 的任何公因数都整除它们的线性组合 $3d$ 和 $3c$ ；由于 $\gcd(c, d) = 1$ ，它只可能整除 $3$ ，但 $d$ 是 $3$ 的倍数，而 $c$ 不是，所以 $d + c$ 不是 $3$ 的倍数。因此该分数已经最简，且 $m + n = 3d = 3 \cdot 12^{2^{2024}}$ 。

模 $8$ 时， $12^{2^{2024}} \equiv 0$ 。模 $125$ 时， $12$ 的乘法阶整除 $\lambda(125) = 100$ ，且 $2^{2024} \equiv 16 \pmod{100}$ （它模 $4$ 为 $0$ ，并且 $2^{20} \equiv 1$ 模 $25$ ，而 $2024 \equiv 4$ 模 $20$ ），所以 $12^{2^{2024}} \equiv 12^{16} \equiv 41 \pmod{125}$ 。中国剩余定理给出 $12^{2^{2024}} \equiv 416 \pmod{1000}$ ，因此 $m + n \equiv 3 \cdot 416$ $= 1248 \equiv 248 \pmod{1000}$ 。

Let $y_k = \frac{2x_k - 1}{x_k + 1}.$ From the recurrence, $2x_{k+1} - 1 = \frac{(2x_k - 1)(x_k - 2)}{3x_k}$ and $x_{k+1} + 1 = \frac{(x_k + 1)^2}{3x_k},$ so $\begin{gathered} y_{k+1} = \frac{(2x_k - 1)(x_k - 2)}{(x_k + 1)^2} \\ = y_k(y_k - 1) = y_k^2 - y_k, \end{gathered}$ since $y_k - 1 = \frac{x_k - 2}{x_k + 1}.$ Here $y_1 = \frac{\frac{39}{11}}{\frac{36}{11}} = \frac{13}{12}.$ By induction $y_k = \frac{c_k}{12^{2^{k-1}}}$ where $c_1 = 13$ and $c_{k+1} = c_k\bigl(c_k - 12^{2^{k-1}}\bigr);$ since $12^{2^{k-1}}$ is divisible by $6,$ every $c_k$ stays coprime to $6.$

Inverting the substitution, $x_k = \frac{1 + y_k}{2 - y_k} = \frac{d + c}{2d - c}$ with $d = 12^{2^{k-1}}$ and $c = c_k.$ All $x_k$ are positive (for $x \gt 0,$ $x + \frac{1}{x} - 1 \ge 1$ ), so $y_k = \frac{2x_k - 1}{x_k + 1} \in (-1, 2),$ making both $d + c$ and $2d - c$ positive. Any common divisor of $d + c$ and $2d - c$ divides their combinations $3d$ and $3c;$ as $\gcd(c, d) = 1,$ it divides $3,$ but $d$ is divisible by $3$ while $c$ is not, so $d + c$ is not divisible by $3.$ Hence the fraction is in lowest terms and $m + n = 3d = 3 \cdot 12^{2^{2024}}.$

Modulo $8,$ $12^{2^{2024}} \equiv 0.$ Modulo $125,$ the multiplicative order of $12$ divides $\lambda(125) = 100,$ and $2^{2024} \equiv 16 \pmod{100}$ (it is $0$ mod $4,$ and $2^{20} \equiv 1$ mod $25$ with $2024 \equiv 4$ mod $20$ ), so $12^{2^{2024}} \equiv 12^{16} \equiv 41 \pmod{125}.$ The Chinese remainder theorem gives $12^{2^{2024}} \equiv 416 \pmod{1000},$ so $m + n \equiv 3 \cdot 416$ $= 1248 \equiv 248 \pmod{1000}.$

2025 AIME II 第 13 题

答案：248

难度评级：3370

小提示：

大提示：

解答：

其他年份的第 13 题