If $x \equiv a \pmod {p_1}$ and $x\equiv a \pmod{p_2}$, then is it true that $x\equiv a \pmod{p_1p_2} ?$
$p_1, p_2$ are distinct prime numbers
I have just observed this pattern when solving this problem. Is there a simple way to prove/disprove it ?
Solution 1:
More generally, if $x\equiv a\pmod m$ and $x\equiv a\pmod n$ then $x\equiv a\pmod{\mathrm{lcm}(m,n)}$.
This is true because $x-a$ is a multiple of $m$ and a multiple of $n$, so must be a multiple of the least common multiple of $m,n$.
If $\gcd(m,n)=1$ then $\mathrm{lcm}(m.n)=mn$.
And if $p_1,p_2$ are distinct primes, then $\gcd(p_1,p_2)=1$.