题解：P10414 [蓝桥杯 2023 国 A] 2023 次方

· · 题解

题目回顾

我们需要计算的是：

也就是从2开始，每个数字作为前一个数字的指数，直到2023，然后对整个数取模2023。 ### 解决思路 对于这种超大指数的模运算，直接计算显然不可行。我们需要利用**欧拉定理**和**中国剩余定理**来简化计算。 #### 第一步：分解模数2023 首先，我们将2023分解质因数： $$ 2023 = 7 \times 17 \times 17 = 7 \times 289 $$ 因此，我们可以分别计算： 1. $2^{(3^{(4^{(\ldots ^{2023})})})} \bmod 7
  1. 2^{(3^{(4^{(\ldots ^{2023})})})} \bmod 289

然后利用中国剩余定理合并结果。

第二步：计算 x \mod 7

我们需要计算 2^{k} \mod 7 ，其中 k = 3^{4^{\cdot^{\cdot^{\cdot^{2023}}}}} 。

根据欧拉定理，因为 \gcd(2, 7) = 1 ，且 \phi(7) = 6 ，所以：

2^6 \equiv 1 \mod 7

因此， 2^{k} \mod 7 取决于 k \mod 6 。

接下来计算 k \mod 6 ：

k = 3^{4^{\cdot^{\cdot^{\cdot^{2023}}}}}

观察 3 \mod 6 ：

因此：

k \equiv 3 \mod 6

所以：

2^{k} \equiv 2^3 \equiv 8 \equiv 1 \mod 7

第三步：计算 x \mod 289

我们需要计算 2^{k} \mod 289 ，其中 k = 3^{4^{\cdot^{\cdot^{\cdot^{2023}}}}} 。

首先， \phi(289) ： 因为 289 = 17^2 ，所以：

\phi(289) = 289 - 17 = 272

根据欧拉定理，因为 \gcd(2, 289) = 1 ，所以：

2^{272} \equiv 1 \mod 289

因此， 2^{k} \mod 289 取决于 k \mod 272 。

接下来计算 k \mod 272 ：

k = 3^{4^{\cdot^{\cdot^{\cdot^{2023}}}}}

我们需要计算 3^{m} \mod 272 ，其中 m = 4^{\cdot^{\cdot^{\cdot^{2023}}}} 。

首先分解 272 ：

272 = 16 \times 17

计算 \phi(272) ：

\phi(272) = \phi(16) \times \phi(17) = 8 \times 16 = 128

根据欧拉定理：

3^{128} \equiv 1 \mod 272

因此， 3^{m} \mod 272 取决于 m \mod 128 。

接下来计算 m \mod 128 ：

m = 4^{\cdot^{\cdot^{\cdot^{2023}}}}

因为 4 的幂次增长非常快，且 \phi(128) = 64 ，但对于 n \geq 2 ， 4^n \mod 128 很快就会变成 0（因为 4^3 = 64 , 4^4 = 256 \equiv 0 \mod 128 ）。因此：

因此：

k = 3^{m} \equiv 3^{0} \equiv 1 \mod 272

所以：

2^{k} \equiv 2^1 \equiv 2 \mod 289

第四步：合并结果

现在我们有：

  1. x \equiv 1 \mod 7
  2. x \equiv 2 \mod 289

我们需要找到一个数 x 同时满足这两个同余式。

设 x = 289k + 2 ，代入第一个同余式：

289k + 2 \equiv 1 \mod 7

计算 289 \mod 7 ：

289 \div 7 = 41 \times 7 = 287 289 - 287 = 2

所以：

2k + 2 \equiv 1 \mod 7 2k \equiv -1 \equiv 6 \mod 7 因此，$ k = 7m + 3 $，代入 $ x $： $$ x = 289(7m + 3) + 2 = 2023m + 867 + 2 = 2023m + 869

最小的正整数解是 m = 0 时：

x \equiv 869 \mod 2023

验证

最终答案

\boxed{869}