I am having a problem to solve the following set of n equations:
$$a_1 - k_1*b_1 = a_2 - k_2*b_2 = a_3 - k_3*b_3 = \dots = a_n - k_n*b_n$$
Given all the values of $a_i \ and \ b_i$, the question is to solve for the values of $k_i$. The values of $a_i, \ b_i \ and \ k_i$ are integers.
I have tried solving it by taking two consecutive pairs of equation, which is the same as Diophantine equation but I am not able to proceed further. I tried to think solving it by using greatest common divisor, but didn't get any further. The idea of gcd struck because the equations look like Diophantine equations.
Any hints solving the equations.
P.S. This was a programming question which I reduced to the above equations, so an efficient method is required.
Edit1: Since there can be many values of $k_is$, the values of $k_i$ that gives the minimum sum of all $k_i$ is to be returned.
Look at it this way. What are the possible values of $m=a_1-k_1b_1$ for various integer $k_1$? That's an arithmetic progression. OK, now what are the possible values of $m=a_1-k_1b_1=a_2-k_2b_2$, given that the equation $a_1-k_1b_1=a_2-k_2b_2$ has any solutions at all for integer $k_1,\,k_2$? That's an arithmetic progression too, so it can be represented as $m=a_{combined}-k\cdot b_{combined}$, where $b_{combined}=LCM(b_1,b_2)$. Thus we've just reduced two expressions to one expression of the same form. In the similar manner one may reduce $n$ of them to $n-1$, then to $n-2$ and so on, all the way down to one. And of course, all $k_i$ are linear functions of $m$, so the rest is simple.