关于用逆元方法证明同余式$x \equiv 1 \pmod{pq}$的困惑

嘿，我懂你卡在这儿的点了——想用逆元构造的方式直接证明这个同余式，结果推导到一半卡壳了对吧？咱们一步步理清楚问题出在哪，顺便把这个证明捋顺。

首先先明确几个关键定义，避免混淆：

• $p^{-1}$是**$p$在模$q$下的逆元**，也就是说它满足 $p \cdot p^{-1} \equiv 1 \pmod{q}$；
• $q^{-1}$是**$q$在模$p$下的逆元**，满足 $q \cdot q^{-1} \equiv 1 \pmod{p}$。

你之前的推导里有个小小的笔误：$p^{-1}$的表达式写错了，应该是 $p \cdot p^{-1} = qk' + 1$，所以 $p^{-1} = \frac{qk' + 1}{p}$（不是分母为$q$），这个小错误可能是导致你后续推导混乱的原因之一。

方法一：分模验证 + 中国剩余定理（最直接的思路） #

其实不用拆成分数形式，我们可以分别在模$p$和模$q$下验证你构造的 $x = p \cdot p^{-1} + q \cdot q^{-1}$ 满足同余条件，再利用中国剩余定理直接得出模$pq$的结论：

1. 模$p$下验证：
   因为$p$是$p$的倍数，所以 $p \cdot p^{-1} \equiv 0 \pmod{p}$；而根据$q^{-1}$的定义，$q \cdot q^{-1} \equiv 1 \pmod{p}$。两者相加得：
   $$x \equiv 0 + 1 = 1 \pmod{p}$$
2. 模$q$下验证：
   同理，$q \cdot q^{-1} \equiv 0 \pmod{q}$，$p \cdot p^{-1} \equiv 1 \pmod{q}$，相加得：
   $$x \equiv 1 + 0 = 1 \pmod{q}$$

现在，因为$p$和$q$是互质的不同奇素数，根据中国剩余定理，满足$x \equiv 1 \pmod{p}$且$x \equiv 1 \pmod{q}$的解在模$pq$下是唯一的。而我们知道$x=1$本身就是一个解，所以必然有：
$$x \equiv 1 \pmod{pq}$$

方法二：直接展开推导（顺着你的思路修正） #

如果你非要顺着你之前的展开思路来证明，咱们修正笔误后继续：
设 $p \cdot p^{-1} = qk' + 1$，$q \cdot q^{-1} = pk + 1$（这里$k$和$k'$都是整数），那么：
$$x = p \cdot p^{-1} + q \cdot q^{-1} = (qk' + 1) + (pk + 1) = pk + qk' + 2$$

现在要证明 $pk + qk' + 2 \equiv 1 \pmod{pq}$，等价于证明 $pk + qk' \equiv -1 \pmod{pq}$，也就是证明 $pk + qk' + 1$ 是$pq$的倍数。

我们可以用逆元的定义代入：
由 $q \cdot q^{-1} = pk + 1$ 可得 $pk = q \cdot q^{-1} - 1$；同理，由 $p \cdot p^{-1} = qk' + 1$ 可得 $qk' = p \cdot p^{-1} - 1$。

把这两个式子代入 $pk + qk'$：
$$pk + qk' = (q q^{-1} - 1) + (p p^{-1} - 1) = q q^{-1} + p p^{-1} - 2$$

哎，看起来又绕回去了？其实这说明直接展开的路径反而绕远路了——毕竟我们已经通过分模验证+中国剩余定理，非常简洁地得出了结论，这也是中国剩余定理构造解的标准思路，你构造的$x$本身就是满足两个同余式的解，而唯一解就是$1 \pmod{pq}$，所以自然相等。

总的来说，你之前的问题主要是笔误导致推导跑偏，换个角度从分模验证入手，结合互质条件下的解的唯一性，就能轻松解决这个困惑啦。

备注：内容来源于stack exchange，提问作者Josh