关于同余方程组y≡a/d (mod m/d)与y≡b/d (mod n/d)存在唯一解的疑问

嘿，我来帮你理清这个困惑的核心点——你忽略了题目给出的$\gcd(m,n)=d$这个条件能推导出一个关键结论：$\gcd(m/d, n/d)=1$，这正是我们能用中国剩余定理（CRT）得出唯一解的依据！

让我一步步拆解：

1. 从最大公约数的性质出发
   已知$\gcd(m,n)=d$，我们可以把$m$和$n$分别写成$m = d \cdot m'$、$n = d \cdot n'$的形式。根据最大公约数的基本性质：$\gcd(kd, ld) = d \cdot \gcd(k,l)$，反过来如果$\gcd(m,n)=d$，那就意味着$\gcd(m', n') = \gcd(m/d, n/d) = 1$。也就是说，提取完最大公约数$d$之后，剩下的$m/d$和$n/d$是互质的——不可能再有大于1的公因数，否则那个公因数乘以$d$就会成为$m$和$n$的更大公约数，这和$d$是最大公约数的定义矛盾。

2. 验证y的方程组满足CRT的条件
   再看y的方程组：y ≡ a/d (mod m/d) 和 y ≡ b/d (mod n/d)。首先要确认这个方程组是有解的：

   • 题目里给出$\gcd(a,m)=d$和$\gcd(b,n)=d$，说明$a$是$d$的倍数（$a = d \cdot a'$），$b$也是$d$的倍数（$b = d \cdot b'$），所以$a/d$和$b/d$都是整数。
   • 原方程组$x ≡ a \pmod{m}$和$x ≡ b \pmod{n}$有解的前提是$a ≡ b \pmod{d}$，而因为$a$和$b$都是$d$的倍数，这个条件自动满足（$d \cdot a' ≡ d \cdot b' \pmod{d}$等价于$0 ≡ 0 \pmod{d}$），所以y的两个同余式是兼容的。

   现在，既然$m/d$和$n/d$互质，且方程组有解，根据中国剩余定理，这个方程组在模$(m/d) \cdot (n/d)$的范围内有唯一解。

3. 回到原问题的解结构
   一旦我们找到这个唯一的$y_0$满足y的方程组，那么原方程组的解就可以表示为$x = d \cdot y_0 + i \cdot (m n / d)$，其中$i \in {0, ..., d-1}$。这是因为$m n / d$是$m$和$n$的最小公倍数（$\text{lcm}(m,n) = m n / \gcd(m,n)$），所以加上它的倍数不会改变$x$模$m$和模$n$的结果，这样就得到了原方程组的$d$个不同解（模$mn$）。

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