Chinese remainder theorem, how to get a ≡ b (mod pq) from a ≡ b (mod p) and a ≡ b (mod q)?

966 Views Asked by At

a ≡ b (mod p)
a ≡ b (mod q)
Then : a ≡ b (mod pq)

Can someone explain this to me ? I was told it was from Chinese Remainder Theorem.
Is there an easy way to get the third line, given the first two lines ?

Note that I read this answer to an other post and didn't understand anything, so please provide an easily understandable answer.

2

There are 2 best solutions below

3
On

Hint: If $p$ divides $c$ and $q$ divides $c$, then $pq=lcm(p,q)$ divides $c$.

(This assumes that $p$ and $q$ are distinct primes or at least are coprime.)

0
On

Definition of lcm$(x,y)$.

$\qquad (1.) \quad x \mid \operatorname{lcm}(x,y).$

$\qquad (2.) \quad y \mid \operatorname{lcm}(x,y).$

$\qquad (3.) \quad \text{If $x \mid z$ and $y \mid z$ then $\operatorname{lcm}(x,y) \mid z.$}$


Theorem. $\operatorname{lcm}(x,y) = \dfrac{xy}{\gcd(x,y)}$.


Theorem. Suppose $p$ and $q$ are relatively prime. Then $p \mid n$ and $q \mid n$ implies $pq \mid n$.

Proof. If $p \mid n$ and $q \mid n$, then $\operatorname{lcm}(p,q) \mid n$. Since $p$ and $q$ are relatively prime, $\operatorname{lcm}(p,q) = \dfrac{pq}{\gcd(p,q)} = pq$. Hence $pq \mid n$.


Suppose that $p$ and $q$ are relative prime.

If $a \equiv b \pmod p$ and $a \equiv b \pmod q$, then $p \mid (b-a)$ and $q \mid (b-a)$. Since $p$ and $q$ are relative prime, then $pq \mid (b-a)$. Hence $a \equiv b \pmod{pq}$.