Finding if the intersection of two infinite sets of a certain form is empty or not We have two sets of natural numbers, where each set is the union of contiguous sets of the same size $d$, spaced at regular intervals.
Formally, the sets take the form:
$S_A = \{0, 1, \ldots, d - 1\} \cup \{T_A, T_A + 1, \ldots, T_A + d - 1\} \cup \ldots \cup \{nT_A, nT_A + 1, \ldots, nT_A + d - 1\} \cup \ldots$
$S_B = \{d, d+1\, \ldots, 2d - 1\} \cup \{d + T_B, d + T_B + 1, \ldots, d + T_B + d - 1\} \cup \ldots \{d + nT_B, d + nT_B + 1, \ldots, d + nT_B + d - 1\} \cup \ldots$
I am looking for an efficient way of finding out if the two sets intersect or not, or at least some insight into the problem (and bar anything concrete, at least some pointers to relevant areas of mathematics which could help).
The algorithm I have so far is just taking $d + T_B \mod T_A$, testing if it's less than or equal to $d$, taking $d + T_B + d \mod T_A$ and seeing if that is less than or equal to $d$ and doing this for $nT_B$ until $d + nT_B \mod T_A = d$.
 A: The question boils down to whether there are positive integers $n,i,j$ with $0 \leq i,j \leq d-1$ such that:
\begin{equation}
n \cdot T_A + i = d + j \mod T_B
\end{equation}
Because then $n \cdot T_A + i = d + j + m \cdot T_B$ for some integer $m$, as desired.
Now, if $\gcd(T_A,T_B) = 1$, then we can take $i = j = 0$ and solve $n \cdot T_A  = d \mod T_B$ for $n$. To find this $n$, see here.
So in this case the intersection is always non-empty.
If $\gcd(T_A,T_B) = g > 1$, then it is slightly more complicated.
Now $n \cdot T_A \mod T_B$ takes on the values $0,g,2g,\dots,(T_B-1)g \mod T_B$.
We want to know whether
\begin{equation}
n \cdot T_A = d + j - i\mod T_B
\end{equation}
has a solution for some $n,i,j$.
This happens when $d+j-i = 0 \mod g$, where $0 \leq i,j \leq d-1$. In other words, the interval of integers $1,2,\dots ,2d-1$ contains a multiple of $g$.
This happens if and only if $2d-1 \leq g$.
Try some examples (one with $\gcd(T_A,T_B) = 1$ and some with $\gcd(T_A,T_B) > 1$) to see what is going on.
