Using two congruences and gcd

Question

Prove that if $b_1, b_2 \in \mathbb Z$ and $d_1, d_2 \in \mathbb Z^+$, then there exists at least one solution $x \in \mathbb Z$ satisfying simultaneously:

$x \equiv b_1 ($mod $d_1)$

$x \equiv b_2 ($mod $d_2)$

if and only if gcd$(d_1,d_2)|(b_1-b_2)$.

So, so far what I have done is the following:

$x \equiv b_1 ($mod $d_1) \Rightarrow x = b_1 + k_1d_1$, some $k_1 \in \mathbb Z$

$x \equiv b_2 ($mod $d_2) \Rightarrow x = b_2 + k_2d_2$, some $k_2 \in \mathbb Z$

Rearrange to get: $(b_1 - b_2) + k_1d_1 = k_2d_2$

But now I'm stuck.

Answer 1

You are almost there. In general, the equation $ax+by=c$ has a solution $(x,y)$ if and only if $\gcd(a,b)\mid c$. (It is called 'Bézouts identity/lemma' or is an immediate consequence of it.)
Applying this to the equation $d_1k_1-d_2k_2=b_2-b_1$ gives the desired necessary and sufficient condition.