Find every K such that arr[i]%K is equal for each arr[i] 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$.

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$.