, 2006

Let $[d_1, d_2]$ denote the least common multiple of $d_1$ and $d_2$. Let $P_j$ denote the union of all arithmetic progressions with common difference $d_j$, $j = 1, 2$, and let $S = P_1 \cap P_2$. Then $S$ is an arithmetic progression with common difference $[d_1, d_2]$. Let $y$ be the least element of $P_1$ and $x$ the least element of $S$.
Since any two arithmetic progressions with common difference $d_1$ have at least two common elements $b \le k-1$. If $\frac{d_2}{\text{gcd}(d_1, d_2)} \le \frac{k}{2}$, then the result follows from $b \le k-1$. Suppose $\frac{d_2}{\text{gcd}(d_1, d_2)} > \frac{k}{2}$. Let
$$m_0 = 2 \frac{d_2}{\text{gcd}(d_1, d_2)} - k.$$
Each arithmetic progression with common difference $d_1$ contains at least 2 elements of $S$ and starts at one of the points $y+md_1$, $0 \le m \le k-2$. However an arithmetic progression with common difference $d_1$ starting at one of the points $x+d_1, x+2d_1, \dots, x+m_0d_1$ contains only one point of $S$ namely $x+[d_1, d_2]$. Hence
$$b \le k-1 - m_0 = 2 \left( k - \frac{d_2}{\text{gcd}(d_1, d_2)} \right) - 1.$$