Computing the intersection of two arithmetic sequences $(a\mathbb{Z} + b) \cap (c \mathbb{Z} + d)$ I am getting stuck writing a general formula for the intersection of two arithmetic sequences.  
$$ (a\mathbb{Z} + b) \cap (c \mathbb{Z} + d) = \begin{cases} 
\varnothing & \text{if ???} \\
?\mathbb{Z} + ? & \text{otherwise}\end{cases} $$
For any two arithmetic sequences, I would know how to compute their (possibly null) intersection, but I don't know how to write a formula in general.
 A: You are effectively asking for solutions to the equation: 
$$aX - c Y = d -b$$ 
this has solutions if and only if $\gcd(a,c)\mid d-b$. 
If it has a solution you can find it using the Euclidean Algorithm. 
Once you have one solution $(x_0,y_0)$, then the intersection is $(ax_0 + b)+ \operatorname{lcm}(a,c) \mathbb{Z}$. 
There is no very direct way to "write down" a solution $(x_0,y_0)$; but using modular inverses you could come close. 
A: This is like solving the Diophantine equation
$$ax+b=cy+d$$
which is
$$ax-cy=d-b$$
This equation has solutions if and only if $\gcd(a,c)$ divides $d-b$. If this condition holds, there are infinitely many solutions. The intersection of the arithmetic progressions is empty or infinite, and if it is infinite it is also an arithmetic progression.
See this.
A: Two arithmetic sequences $a\mathbb{Z}+b$ and $c\mathbb{Z}+d$ with $a,b,c,d\in\mathbb{Z}$ such that $a\neq 0$ and $c\neq 0$ intersect nontrivially if and only if $\gcd(a,c)$ divides $b-d$, in which case $$(a\mathbb{Z}+b)\cap(c\mathbb{Z}+d)=\text{lcm}(a,c)\mathbb{Z}+r\,,$$
where $r$ is the unique solution modulo $\text{lcm}(a,c)$ to the system of congruence $r\equiv b\pmod{a}$ and $r\equiv d\pmod{c}$.  To be fair, this is precisely a rephrasing of the Chinese Remainder Theorem.
To prove the first claim, let $t:=\gcd(a,c)$.  If $(a\mathbb{Z}+b)\cap (c\mathbb{Z}+d)\neq \emptyset$, then suppose $s$ is in the intersection.  Therefore, $ax+b=s=cy+d$ for some $x,y\in\mathbb{Z}$.    Thus, $-ax+cy=b-d$, so $t\mid (b-d)$, as $t\mid a$ and $t\mid c$.
Conversely, suppose $t\mid b-d$.  Then, there exist $x,y\in\mathbb{Z}$ such that $b-d=-ax+cy$, so $ax+b=cy+d$.  Hence, $a\mathbb{Z}+b$ and $c\mathbb{Z}+d$ have a common element.
Now, we shall prove the second claim.  Let $m:=\text{lcm}(a,c)$.  Clearly, every element of $P:=(a\mathbb{Z}+b)\cap(c\mathbb{Z}+d)$ is congruent to $r$ modulo $m$ by the Chinese Remainder Theorem.  We claim that every such number is indeed in $P$.  Let $k\in\mathbb{Z}$.  Since $r\equiv b\pmod{a}$ and $r\equiv d\pmod{c}$, we have $r=ax+b$ and $r=cy+d$ for some $x,y\in\mathbb{Z}$.  Now, $km+r=a\left(x+k\frac{m}{a}\right)+b$ and $km+r=c\left(y+k\frac{m}{c}\right)+d$ with $x+k\frac{m}{a},y+k\frac{m}{c}\in\mathbb{Z}$.  Therefore, $km+r\in P$, and the conclusion follows.
A: It amounts to solving the system of simultaneous congruences:
$$\begin{cases}
x\equiv b\mod a\\x\equiv d\mod c
\end{cases}$$
This system has a solution idf and only if $b\equiv d\mod  \gcd(a,c)$, and it is unique modulo $\operatorname{lcm}(a,c)$.
