求解大指数同余方程：模97下x^1477≡54的后续解法

既然你已经通过欧拉-费马定理把原方程简化到这一步，接下来我们可以利用模素数乘法群的循环性来拆解问题——97是素数，它的乘法群(\mathbb{Z}_{97}^*)是阶为(97-1=96)的循环群，这意味着所有非零模97的数都可以表示为某个"原根"的幂次，从而把幂次方程转化为更易求解的线性同余方程。

步骤1：找到模97的一个原根 #

原根g是满足以下条件的数：它的幂次能生成(\mathbb{Z}_{97}^{*)的所有元素，也就是g的阶恰好是96。验证方法是：对于96的所有素因子（2和3），检查(g}{96/2} \not\equiv 1 \pmod{97})且(g^{96/3} \not\equiv 1 \pmod{97})。

• 试g=5：
  • 计算(5^{48} \equiv (5^{24})2)，先算(5^{24} = (5^{12})2 = 64^2 = 4096 \equiv 4096 - 42\times97 = 22 \pmod{97})，所以(5^{48} = 22^2 = 484 \equiv 484 - 4\times97 = 96 \equiv -1 \not\equiv 1 \pmod{97})
  • 计算(5^{32} = (5^{16})2 = 36^2 = 1296 \equiv 1296 - 13\times97 = 35 \not\equiv 1 \pmod{97})
  • 两个条件都满足，所以5是模97的一个原根。

步骤2：将54表示为原根的幂次 #

我们需要找到整数k，使得(5^k \equiv 54 \pmod{97})。可以用二进制分解的方法逐步计算：

• (5^1 = 5), (5^2 = 25), (5^4 = 25^2 = 625 \equiv 43 \pmod{97})
• (5^8 = 43^2 = 1849 \equiv 6 \pmod{97}), (5^{16} = 6^2 = 36 \pmod{97}), (5^{32} = 36^2 = 1296 \equiv 35 \pmod{97})
• 实际计算可得(5^{52} = 5^{32} \times 5^{16} \times 5^4 = 35\times36\times43 = 35\times(-4) = -140 \equiv 54 \pmod{97})，所以**(5^{52} \equiv 54 \pmod{97})**，即k=52。

步骤3：将x表示为原根的幂次，转化为线性同余方程 #

设(x = 5^m)（因为5是原根，所有非零x都可以写成这种形式），代入原方程：
[
(5^m){37} = 5^{37m} \equiv 5^{52} \pmod{97}
]
由于5是原根，指数在模96下相等（因为乘法群的阶是96），所以得到线性同余方程：
[
37m \equiv 52 \pmod{96}
]

步骤4：求解线性同余方程 #

首先求37在模96下的逆元——也就是找整数t，使得(37t \equiv 1 \pmod{96})。用扩展欧几里得算法计算：
[
\begin{align*}
96 &= 2\times37 + 22 \
37 &= 1\times22 + 15 \
22 &= 1\times15 + 7 \
15 &= 2\times7 + 1 \
\end{align*}
]
回代得到：
[
1 = 15 - 2\times7 = 3\times37 - 5\times22 = 13\times37 - 5\times96
]
所以37的逆元是13（因为(13\times37 \equiv 1 \pmod{96})）。

两边乘以13：
[
m \equiv 52\times13 \pmod{96}
]
计算(52\times13=676)，(676 \mod 96 = 676 - 7\times96 = 4)，所以(m \equiv 4 \pmod{96})。

步骤5：还原x的值 #

因为(x=5^m)，且(m\equiv4\pmod{96})，所以：
[
x = 5^4 = 625 \equiv 625 - 6\times97 = 43 \pmod{97}
]

验证 #

计算(43^{37} \pmod{97})：因为(43=5^{4)，所以(43}{37}=5^{148}=5{96+52}=5^{96}\times5{52} \equiv 1\times54=54 \pmod{97})，符合原方程，解正确。

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