- #1

steenis

- 312

- 18

(i) The system:

$x \equiv b (mod \ m)$

$x \equiv b' (mod \ m')$

has a solution if and only if $b \equiv b' (mod \ d)$

(ii) two solutions of the system are congruent $mod \ l$, where $l = lcm(m,m')$.

I can prove part (i), but can anyone help me with part (ii) ?

Remember $gcd(a,b) \cdot lcm(a,b) = a \cdot b$

See, for instance: "Cuoco - Learning Modern Algebra (2013)", p.145 and p.148

Example:

$x \equiv 1 (mod \ 6)$ and $x \equiv 4 (mod \ 15)$

Then $m=6$, $m'=15$, $d=3$, $b=1$, $b'=4$, and $1 \equiv 4 (mod \ 3)$, so (i) applies:

$19 \equiv 1 (mod \ 6)$ and $19 \equiv 4 (mod \ 15)$.

$lcm(6,15)=30$ and all the solutions are: $\cdots \ -41,-11,19,49,79 \ \cdots$.