Suppose you are given a circle that is subdivided into N parts. Two bugs race around the circle at distinct, discrete speeds that are less than N parts per time increment. They start at any position on the circle. Prove one of the cases to be true:
- For any speeds, given infinite time, the bugs will eventually end up on the same part of the circle at the same time.
- There are a set of speeds that the bugs will never reach the same spot, given infinite time.
I've written out the relation:
$(n_i + s_i*t) \mod(N) = (n_j + s_j*t) \mod(N)$
but haven't gotten much further than this.
Although the question doesn't explicitly say it's only dealing with integer quantities, it's implicitly specified by the question text talking about "N distinct parts", "distinct, discrete speeds", and "time increment". Also, the initial relation using modulos implies this as normally they're only used in this way with integers. However, if time is allowed to be any real value, then for any different speed, the $2$ bugs will always eventually cross paths when the faster one overtakes the slower one. The rest of this answer assumes only integers are involved.
Your stated relation is the right way to start the solution. Using slightly different variables, let $n_1, n_2$ be the starting positions, and $s_1, s_2$ be the speeds of the $2$ bugs. Then for them to meet up at some time $t$ requires that
$$n_1 + s_1 \times t \equiv n_2 + s_2 \times t \pmod N \implies n_1 - n_2 + (s_1 - s_2) \times t \equiv 0 \pmod N \tag{1}\label{eq1}$$
In particular, this means that for some $k \in \mathbb{Z}$
$$n_1 - n_2 + (s_1 - s_2) \times t = kN \tag{2}\label{eq2}$$
Let $d = \gcd(s_1 - s_2, N)$. Since $d \mid kN$ and $d \mid (s_1 - s_2) \times t$, this means $d \mid n_1 - n_2$ also. If this is not true, then the bugs will never be at the same place at the same time. Thus, the given case $2$ is the one which is true.
An example of this is if $N = 10, n_1 = 4, n_2 = 1, s_1 = 3, s_2 = 1$. Then, $d = 2 = \gcd(3 - 1, 100)$ and $n_1 - n_2 = 4 - 1 = 3$, with $2 \not\mid 3$ (in particular, the LHS will always be odd and the RHS always even).