求解满足同余式$x^2 \equiv 3 \pmod{2003^2}$的正整数x及适用定理咨询

嘿，我来帮你理清这个问题的解法和核心定理～

首先，咱们得先确认这个同余式有没有解，这一步会用到二次互反律。因为2003是质数，我们可以用二次互反律判断3是不是模2003的二次剩余：

根据二次互反律，$\left(\frac{3}{2003}\right) = \left(\frac{2003}{3}\right) \times (-1)^{\frac{(3-1)(2003-1)}{4}}$。计算一下：

• 2003除以3余2，所以$\left(\frac{2003}{3}\right) = \left(\frac{2}{3}\right) = -1$；
• 指数部分$\frac{2 \times 2002}{4} = 1001$，是奇数，所以$(-1)^{1001} = -1$；
• 两者相乘：$(-1) \times (-1) = 1$，说明3是模2003的二次剩余，存在解$x_0$满足$x_0^2 \equiv 3 \pmod{2003}$。

接下来，要把模2003的解提升到模$2003^2$的解，这时候就得用**亨泽尔引理（Hensel's Lemma）**了，这是处理这种高次幂模同余的核心定理。具体步骤如下：

假设$x_0$是模2003的一个解，我们设$x = x_0 + k \times 2003$（k是整数），把它代入同余式$x^2 \equiv 3 \pmod{2003^2}$：
展开得：$(x_0 + 2003k)^2 = x_0^2 + 2x_0 \times 2003k + (2003k)^2$。
因为$(2003k)^2$是$20032$的倍数，模$2003^{2$等于0，所以式子简化为：$x_0}2 + 2x_0 \times 2003k \equiv 3 \pmod{2003^2}$。

又因为$x_0^2 \equiv 3 \pmod{2003}$，所以$x_0^2 = 3 + m \times 2003$（m是整数），代入上式：
$3 + m \times 2003 + 2x_0 \times 2003k \equiv 3 \pmod{2003^2}$。
两边减3，再除以2003，得到：$m + 2x_0k \equiv 0 \pmod{2003}$。

解这个关于k的同余式：$k \equiv -m \times (2x_0)^{-1} \pmod{2003}$，这里$(2x_0)^{-1}$是$2x_0$在模2003下的逆元。

至于怎么找$x_0$，因为2003≡3 mod4，对于这种形式的质数，二次剩余a的平方根可以用公式$x_0 \equiv \pm a^{\frac{p+1}{4}} \pmod{p}$计算，也就是$x_0 \equiv \pm 3^{501} \pmod{2003}$，你可以用快速幂算法算出具体数值。

得到k之后，代入$x = x_0 + k \times 2003$，就能得到模$2003^2$的一个解，另一个解就是它的相反数$-x \pmod{2003^2}$。

总结一下，整个过程用到两个关键定理：二次互反律（判断解的存在性）和亨泽尔引理（将低次模的解提升到高次模）。

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