Prove that the system of congruences has a solution

Question

I'm doing the following exercise and I don't know how to prove it.

Suppose $a,b \in \mathbb{Z}$, and $d=\gcd(a,b)$. I have to prove that if $x\equiv y \bmod d$, then the system

$$X\equiv x \mod a$$

$$X\equiv y \mod b$$

has a solution.

I don't even how to start...

Thanks for your help :)

Answer 1

Bezout's Lemma $a,b$ are relatively prime if and only if there exists an $x,y$ such that $ax+by=1$.

Another way to phrase this is that $ax=1\pmod{b}$ and $by=1\pmod{a}$. See if you can use this statement to solve your problem.