Find all $k$ such that $X_1+kY_1,\ldots,X_n+kY_n$ are all equivalent modulo $M$

Let $n, M$ be integers. Given two arrays $X$ and $Y$ of $n$ elements.

For each $i \leq n$, we define arithmetic progression $X[i] + kY[i] \pmod M$, where $0 \leq k \leq M$.

Find all $k$ such that for all $i$, $X[i] + kY[i]$ has the same value.

Example

Let $n = 3$ and $M=6$.

Let $X=\{1,3,5\}$ and $Y=\{2,1,0\}$.

Then,

$$k = 2, X[0]+2Y[0] = X[1] + 2Y[1] = X[2]+2Y[2] = 5 \pmod 6. $$
$$k = 5, X[0] + 5Y[0] = X[1]+5Y[1] = X[2] + 5Y[2] = 5 \pmod 6. $$

So we have two values $k$.

My thoughts.

We can check the modulo equation of pair of elements $(0,1)$.

$$X[0] + kY[0] = X[1] + kY[1] \pmod M$$
or $$k(Y[0]-Y[1]) = X[1] - X[0].$$

Solve this equation we can get value $k$.

Similarly, we can get $k$ with pairs $(0,2), \dots, (0,n-1)$.

But I get stuck with this brute force way:

-
When $n$ becomes large (more than 50000), the run time is slow.

-
With the case $0k = 0 \pmod M$, it means that all $k$ of $[0,M)$ satisfy. So, it does not reduce ranges in the equations.

How do I solve this problem efficiently?

Edit: change to base-0 as suggestion.

You've made a good start. Here is an algorithm that is quite efficient (I used more variables and equations than really needed for even somewhat greater efficiency), even for relatively large $n$ (e.g., more than $50000$ you mention) and large $M$. First, if $n = 1$, then all $k$ work. Otherwise, using $0$-based indices, set up an array or list of objects, with each object containing the $2$ values

$$(Y[0] - Y[i]) \bmod{M} \tag{1}\label{eq1A}$$

$$(X[i] - X[0]) \bmod{M} \tag{2}\label{eq2A}$$

for $1 \le i \le n - 1$. Note $a \bmod{M} = b$ means $M \mid a - b$ and $0 \le b \lt M$.

Next, sort this array or list into increasing values of \eqref{eq1A}. Now, I'll use $1$-based indices. Have $C[i]$ refer to the $i$'th object element of the sorted array or list, with $C[i].y$ being the value from \eqref{eq1A} and $C[i].x$ being the value from \eqref{eq2A}. Thus, as you've indicated, the modular equation to solve for each $i$ is

$$k(C[i].y) \equiv C[i].x \pmod{M} \tag{3}\label{eq3A}$$

Next, set up an initially empty set, call it $D$, to contain the currently possible values of $k$ going from $0$ to $M - 1$ (note since $0 \equiv M \pmod{M}$, the $M$ value is equivalent to $0$) once the first non-$0$ $C[i].y$ value (if any) is handled. Initialize $p \leftarrow -1$ (i.e., previous congruence is not yet set). Start with $i \leftarrow 1$ and follow these steps:

• If $C[i].y \neq 0$, then go to step #2. Otherwise, if $C[i].x \neq 0$, then there are no values of $k$ which work, so exit these steps. Increment $i$. If $i = n$, then all values of $k$ work, so also exit these steps. Otherwise, repeat this step.

• If $p = C[i].y$, then go to step #$3$. Otherwise, set $p \leftarrow C[i].y$. Use the Extended Euclidean algorithm to compute values of $c$, $d$ and $g = \gcd(p, M)$ which satisfy $$cp + dM = g \tag{4}\label{eq4A}$$ Next, define $$e = (c \bmod{M}), \; \; h = \frac{p}{g}, \; \; s = \frac{M}{g} \tag{5}\label{eq5A}$$ Dividing both sides of \eqref{eq4A} by $g$ gives $$ch + ds = 1 \; \; \to \; \; eh \equiv 1 \pmod{s} \tag{6}\label{eq6A}$$ Go to step #$3$.

• If $g \not\mid C[i].x$, then there are no $k$ which work, so exit these steps. Otherwise, set $$f = \frac{C[i].x}{g} \tag{7}\label{eq7A}$$ Dividing both sides of \eqref{eq3A} by $g$, plus using \eqref{eq5A}, \eqref{eq6A} and \eqref{eq7A}, gives $$kh \equiv f \pmod{s} \; \; \to \; \; k(he) \equiv fe \pmod{s} \; \; \to \; \; k \equiv fe \pmod{s} \tag{8}\label{eq8A}$$ Next, define $$r = (fe \bmod s) \tag{9}\label{eq9A}$$ This then gives that the set of valid values of $k$ which work are $$E = \{r + ts, \; 0 \le t \le g - 1\} \tag{10}\label{eq10A}$$ If $D$ is the empty set, then have $D \leftarrow E$, else have $D \leftarrow (D \cap E)$. If $D$ is now an empty set, then there are no values of $k$ which work, so exit these steps. Otherwise, increment $i$. If $i \lt n$, then go to step #$2$. Otherwise, exit these steps, with the values in $D$ being those $k$ which work.

StackExchange Computer Science Q#142353, answer score: 2