给定素数p和q，同余等价式$b\equiv a\mod pq\Leftrightarrow b\equiv a\mod p且b\equiv a\mod q$是否成立？

嘿，咱们来一步步拆解这个问题，其实这个等价关系的两个方向都是成立的，我来给你捋得明明白白～

先看“⇒”方向（从左推右） #

这个方向其实是整除的基本性质，完全不用绕弯子。如果 b ≡ a mod pq，意思就是 pq 能整除 b - a，也就是存在某个整数k，使得 b - a = k * pq。

你想啊，k * pq 里既包含因子p，又包含因子q，那 b - a 自然既是p的倍数，也是q的倍数。这就直接推出了 b ≡ a mod p 且 b ≡ a mod q，是不是超直观？

再看“⇐”方向（从右推左） #

你提到用中国剩余定理（CRT）是完全找对路子了，咱们结合CRT来理清楚逻辑：

• 首先，因为p和q是不同的素数，它们的最大公约数gcd(p,q)=1，也就是互质，这刚好满足CRT的适用条件。
• CRT的核心结论是：对于任意给定的整数x、y，同余方程组 {z ≡ x mod p; z ≡ y mod q} 在模pq的范围内有唯一解。
• 回到咱们的问题，b和a同时满足这个方程组（因为b ≡ a mod p且b ≡ a mod q，相当于x=y=a，z可以取a也可以取b）。根据CRT的唯一性，这两个解在模pq下必须相等，也就是 b ≡ a mod pq。

当然，不用CRT也能直接推导：既然p整除b - a，q也整除b - a，而且p和q互质，那它们的乘积pq也必然整除b - a，这是数论里的经典结论——两个互质的数都整除同一个数时，它们的乘积也能整除这个数。

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