求解非线性同余式$x^3 - 5x \equiv 340 \pmod{648}$的技术求助

首先，我们利用中国剩余定理，将模数分解为互质的因子：$648=8 \times 81$，原同余式等价于求解以下两个同余式的联立解：

1. $x^3 -5x \equiv 340 \pmod{8}$
2. $x^3 -5x \equiv 340 \pmod{81}$

步骤1：求解模8的同余式 #

先简化右侧：$340 \div 8=42\cdots\cdots4$，即$340 \equiv 4 \pmod{8}$，式子变为：
$$x^3 -5x \equiv 4 \pmod{8}$$

枚举$x=0,1,\dots,7$验证：

• $x=1$：$1-5=-4 \equiv 4 \pmod{8}$ ✔️
• $x=3$：$27-15=12 \equiv 4 \pmod{8}$ ✔️
• $x=4$：$64-20=44 \equiv 4 \pmod{8}$ ✔️
• $x=5$：$125-25=100 \equiv 4 \pmod{8}$ ✔️
• $x=7$：$343-35=308 \equiv 4 \pmod{8}$ ✔️

因此模8的解为：$x \equiv 1,3,4,5,7 \pmod{8}$

步骤2：求解模81的同余式 #

简化右侧：$340 \div 81=4\cdots\cdots16$，即$340 \equiv 16 \pmod{81}$，式子变为：
$$x^3 -5x \equiv 16 \pmod{81}$$

我们用Hensel引理逐步提升解的模数：

子步骤2.1：解模3的同余式 #

利用费马小定理$x^3 \equiv x \pmod{3}$，$-5x \equiv x \pmod{3}$，$16 \equiv 1 \pmod{3}$，式子简化为：
$$x + x \equiv 1 \pmod{3} \implies 2x \equiv 1 \pmod{3} \implies x \equiv 2 \pmod{3}$$

子步骤2.2：提升到模9 #

设$x=3k+2$，代入原式：
$$(3k+2)^3 -5(3k+2) \equiv 8 -15k -10 \equiv -2-15k \equiv 7+3k \pmod{9}$$
令其等于16 mod9（即7）：
$$7+3k \equiv7 \pmod{9} \implies 3k \equiv0 \pmod{9} \implies k \equiv0 \pmod{3}$$
故$k=3m$，$x=9m+2$，即$x \equiv2 \pmod{9}$

子步骤2.3：提升到模27 #

设$x=9m+2$，代入原式：
$$(9m+2)^3 -5(9m+2) \equiv8 -45m -10 \equiv -2-45m \equiv25+9m \pmod{27}$$
令其等于16 mod27：
$$25+9m \equiv16 \pmod{27} \implies9m \equiv-9 \equiv18 \pmod{27}$$
两边除以9得：
$$m \equiv2 \pmod{3}$$
故$m=3n+2$，$x=27n+20$，即$x \equiv20 \pmod{27}$

子步骤2.4：提升到模81 #

设$x=27n+20$，代入原式：
$$(27n+20)^3 -5(27n+20) \equiv20^3 -135n -100 \equiv8000-100-135n \equiv62+62+27n \pmod{81}$$
（注：$20^3=8000 \equiv62 \pmod{81}$，$-135n \equiv27n \pmod{81}$，$-100 \equiv62 \pmod{81}$）
令其等于16 mod81：
$$124+27n \equiv16 \pmod{81} \implies43+27n \equiv16 \pmod{81} \implies27n \equiv-27 \equiv54 \pmod{81}$$
两边除以27得：
$$n \equiv2 \pmod{3}$$
故$n=3p+2$，$x=81p+74$，即模81的解为：$x \equiv74 \pmod{81}$

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

现在需要将$x \equiv74 \pmod{81}$分别与模8的5个解联立求解：

情况1：$x \equiv74 \pmod{81}$且$x \equiv1 \pmod{8}$ #

$74 \equiv2 \pmod{8}$，设$x=81k+74$，则：
$$81k+74 \equivk+2 \equiv1 \pmod{8} \implies k \equiv-1 \equiv7 \pmod{8}$$
取$k=8t+7$，得$x=81(8t+7)+74=648t+641$，即$x \equiv641 \pmod{648}$

情况2：$x \equiv74 \pmod{81}$且$x \equiv3 \pmod{8}$ #

$$k+2 \equiv3 \pmod{8} \implies k \equiv1 \pmod{8}$$
取$k=8t+1$，得$x=81(8t+1)+74=648t+155$，即$x \equiv155 \pmod{648}$

情况3：$x \equiv74 \pmod{81}$且$x \equiv4 \pmod{8}$ #

$$k+2 \equiv4 \pmod{8} \implies k \equiv2 \pmod{8}$$
取$k=8t+2$，得$x=81(8t+2)+74=648t+236$，即$x \equiv236 \pmod{648}$

情况4：$x \equiv74 \pmod{81}$且$x \equiv5 \pmod{8}$ #

$$k+2 \equiv5 \pmod{8} \implies k \equiv3 \pmod{8}$$
取$k=8t+3$，得$x=81(8t+3)+74=648t+317$，即$x \equiv317 \pmod{648}$

情况5：$x \equiv74 \pmod{81}$且$x \equiv7 \pmod{8}$ #

$$k+2 \equiv7 \pmod{8} \implies k \equiv5 \pmod{8}$$
取$k=8t+5$，得$x=81(8t+5)+74=648t+479$，即$x \equiv479 \pmod{648}$

最终解 #

原同余式的所有解为：
$$x \equiv155,236,317,479,641 \pmod{648}$$

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