Find every K such that arr[i]%K is equal for each arr[i]

Question

I came across a problem where i have list $arr[]$ of $M$ integers. I have to find all integers K (given there is at least 1 K)such that :

1) K > 1
2) arr[1]%K = arr[2]%K = arr[3]%K = ... = arr[M]%K 

Now in one of the solutions given, the algo was

1. p = abs(arr[0]-arr[1]);
2. Find all divisors of p
3. All the values of K must be among one of the divisors of p

I am not able to understand why the value of $K$ must be within one of the divisors of $p$.

Answer 1

If $$a_1 \bmod K = a_2 \bmod K$$ then $(a_1 - a_2) \bmod K = 0$, which means that $a_1 - a_2$ is a multiple of $K$, i.e. $K$ is a divisor of $a_1 - a_2$.

Or more explicitly:

$$ a_1 = k_1 K + l_1 \\ a_2 = k_2 K + l_2 $$ implies $$ p = |a_1 - a_2| = |k_1 - k_2| \, K $$

Of course, for each divisor of $K$ of $p$, you still have to check if $a_j \bmod K = a_1 \bmod K$ holds for $j = 3, \ldots, M$. (Equivalently: $a_j - a_1$ is divisible by $K$ for $j = 3, \ldots, M$.)

So the proposed algorithm is just a method to find a set of candidates for possible solutions $K$.