Traverse an array with step k The original problem is to move each element of an array k step to the right. That is to say, for an array A[i] (i=1,...,n), make B[(i+k)%n]=A[i].
Now my question here is, consider this shifting problem from a k step adjacent swapping problem. ith element goes to (i+k)%nth, and so forth. Do these trajectories overlap? If not, how many cycles do we have to do?
For $k| n$, this is trivial. We have k cycles each with $\frac{n}{k}$ length. But what about $ k \nmid n$? In this case, $n=ak+b$, where $b\in {1,2...,k-1}$. 
I cannot tell whether $i_1+s_1k \equiv i_2+s_2k\ (\textrm{mod}\ n)$
 A: When you ask about the trajectories overlapping, I believe you mean when all of the elements of $A[i]$ return to their original positions (and values). Let $c$ be the minimum number of cycles for this to happen. Then you have
$$ck \equiv 0 \pmod n \implies ck = en, \; e \in \mathbb{N} \tag{1}\label{eq1A}$$
Also, let
$$d = \gcd(k,n) \implies k = fd, \; n = gd, \; \gcd(f,g) = 1 \tag{2}\label{eq2A}$$
Substituting \eqref{eq2A} into \eqref{eq1A} gives
$$cfd = egd \implies cf = eg \tag{3}\label{eq3A}$$
Since $g \mid cf$ but $\gcd(f,g) = 1$, the smallest $c$ would be where $c = g$ (with this giving $e = f$). Thus, the minimum # of cycles required is
$$c = g = \frac{n}{\gcd(k,n)} \tag{4}\label{eq4A}$$
In your question, you seem to have a few values mixed around, e.g, if $n \mid k$, i.e., $k$ is an integral multiple of $n$, then actually $c = 1$ since $(i+k)\;\%\;n = i$ for all $i$, but note \eqref{eq4A} still works since $\gcd(k,n) = n$ giving $c = 1$. However, as I believe you intended, if $k \mid n$, then $\gcd(k,n) = k$ so $c = \frac{n}{k}$.
Update:
As pointed out by the OP in this comment, I misunderstood the question. As explained, instead of looking for when all elements would return to their original values, the question was about two different elements would "collide" at the same position later. In particular, the question asks under what conditions does this happen and, if it does, how many cycles is required for it to happen.
I'm leaving the initial part of my answer as I think it's interesting & possibly useful for other people, plus I'm reusing some of it. As for the solution to the actual question, using some of my notation & equations above, let $1 \le i_1,i_2 \le n, \; i_1 \neq i_2$ be two indices, and let $s_1$, $s_2$ be number of cycles such that you have
$$i_1 + s_1 k \equiv i_2 + s_2 k \pmod n \implies i_1 - i_2 = en + (s_2 - s_1)k, \; e \in \mathbb{N} \tag{5}\label{eq5A}$$
Using \eqref{eq2A} in \eqref{eq5A} gives
$$i_1 - i_2 = d(eg + (s_2 - s_1)f) \tag{6}\label{eq6A}$$
In particular, this means
$$d \mid i_1 - i_2 \implies i_1 - i_2 = hd, \; h \in \mathbb{Z} \tag{7}\label{eq7A}$$
This can always be done for $i_1 \neq i_2$ except when $d = n$, so this is the only condition for when \eqref{eq5A} cannot possibly hold for $i_1 \neq i_2$. Otherwise, substitute \eqref{eq7A} into \eqref{eq6A} and divide by $d$ to get
$$h = ge + f(s_2 - s_1) \tag{8}\label{eq8A}$$
Since $\gcd(f,g) = 1$, then Bézout's identity guarantees there exists integers $x$ and $y$ such that
$$1 = gx + fy \tag{9}\label{eq9A}$$
As mentioned in the article, the Extended Euclidean algorithm can be used to determine such a pair of $x,y$. Multiplying both sides of \eqref{eq9A} by $h$ gives
$$h = g(hx) + f(hy) \tag{10}\label{eq10A}$$
Comparing with \eqref{eq8A} shows $e = hx$ and
$$s_2 - s_1 = hy \tag{11}\label{eq11A}$$
Thus, the minimum # of cycles would occur for the smallest possible positive value of $y$. As the Bézout's lemma Wikipedia page indicates, if $y_0$ is any solution for $y$ in \eqref{eq9A}, then the full set of possible solutions would be $y = y_0 - mg, \; m \in \mathbb{Z}$. Thus, the smallest positive $y$ would be the remainder of $y_0$ when divided by $g$, except if this remainder is $0$, in which case you need to use $g$.
