模1643下7次根求解咨询：已知c≡169 mod1643等同余条件

要解决这个同余方程，我们可以利用中国剩余定理，先将大模数分解为小质数模数，分别求解后再合并结果，具体步骤如下：

步骤1：分解模数1643 #

首先，我们可以将1643分解为两个互质的质数乘积：
1643 = 31 × 53
根据中国剩余定理，原方程 (m^7 ≡ 169 \pmod{1643}) 等价于以下两个同余方程的组合：

• (m^7 ≡ 169 \pmod{31})
• (m^7 ≡ 169 \pmod{53})

步骤2：求解模31的同余方程 #

先简化169模31的结果：
169 ÷ 31 = 5余14，即 (169 ≡ 14 \pmod{31})
方程变为：(m^7 ≡ 14 \pmod{31})

根据费马小定理，对于质数p，有 (m^{p-1} ≡ 1 \pmod{p})（当m不被p整除时）。这里p=31，所以 (m^{30} ≡ 1 \pmod{31})。我们需要找到7在模30下的逆元——也就是找一个数x，使得 (7x ≡ 1 \pmod{30})。计算可得 (7×13=91≡1 \pmod{30})，所以逆元是13。

因此，方程的解为：
(m ≡ 14^{13} \pmod{31})

逐步计算幂次简化：

• (14^2 = 196 ≡ 196 - 6×31 = 10 \pmod{31})
• (14^4 = (14²⁾2 = 10^2 = 100 ≡ 100 - 3×31 = 7 \pmod{31})
• (14^8 = (14⁴⁾2 = 7^2 = 49 ≡ 49 - 31 = 18 \pmod{31})
• (14^{13} = 14^8 × 14^4 × 14^1 = 18×7×14 = 2×14 = 28 \pmod{31})

所以模31的解是：(m ≡ 28 \pmod{31})

步骤3：求解模53的同余方程 #

同样简化169模53的结果：
169 ÷ 53 = 3余10，即 (169 ≡ 10 \pmod{53})
方程变为：(m^7 ≡ 10 \pmod{53})

用费马小定理，p=53，所以 (m^{52} ≡ 1 \pmod{53})。找7在模52下的逆元：(7×15=105≡105-2×52=1 \pmod{52})，逆元是15。

方程的解为：
(m ≡ 10^{15} \pmod{53})

逐步计算幂次简化：

• (10^2 = 100 ≡ 100 - 53 = 47 \pmod{53})
• (10^4 = (10²⁾2 = 47^2 = 2209 ≡ 2209 - 41×53 = 36 \pmod{53})
• (10^8 = (10⁴⁾2 = 36^2 = 1296 ≡ 1296 - 24×53 = 24 \pmod{53})
• (10^{15} = 10^8 × 10^4 × 10^2 × 10^1 = 24×36×47×10 = 16×47×10 = 10×10 = 47 \pmod{53})

所以模53的解是：(m ≡ 47 \pmod{53})

步骤4：用中国剩余定理合并解 #

现在我们有两个同余式：

1. (m ≡ 28 \pmod{31})
2. (m ≡ 47 \pmod{53})

设 (m = 31k + 28)，代入第二个式子：
(31k + 28 ≡ 47 \pmod{53})
化简得：(31k ≡ 19 \pmod{53})

接下来求31在模53下的逆元，用扩展欧几里得算法可得：(12×31 ≡ 1 \pmod{53})，所以逆元是12。

两边乘以12：
(k ≡ 19×12 ≡ 228 ≡ 228 - 4×53 = 16 \pmod{53})

即 (k = 53t + 16)，代入m的表达式：
(m = 31(53t + 16) + 28 = 1643t + 496 + 28 = 1643t + 524)

因此，原方程的解为：
(m ≡ 524 \pmod{1643})

你可以验证一下：(524^7 \pmod{1643}) 确实等于169，符合原方程的要求。

内容的提问来源于stack exchange，提问作者Elena