# How to solve these system of linear equations?

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.

• Are all the variables $k_i$ required to be integers? Dec 30, 2015 at 5:31
• yes, all $k_i$ are integers.
– Daga
Dec 30, 2015 at 5:33
• Find all pairwise GCDs $(b_i,b_j)$. For those pairs where the GCD is not 1, find also the corresponding $|a_i-a_j|$. If it is not a multiple of the said GCD, stop right there, because there would be no solutions anyway. Dec 30, 2015 at 6:23
• what if all pairs have gcd=1?
– Daga
Dec 30, 2015 at 6:39
• Forget that, I have a better idea. Dec 30, 2015 at 6:39

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.
• i can't understand how u reached to LCM, also how to get individual values of $k_i$?
• Why, $k_i={m-a_i\over b_i}$. As for LCM, well, you may prove that: (1) for any solution $m=a_1-k_1b_1=a_2-k_2b_2$, the number $m-LCM(b_1,b_2)$ is also a solution (i.e. you may find such $k_1,\,k_2$ that....), and (2) for any two solutions $m_1,\;m_2$ their difference is a multiple of $b_1$ and also of $b_2$, and hence of LCM thereof. Dec 30, 2015 at 6:53
• what is $a_{combined}$?
• $a_{combined}$ is any such solution. Well, the other answer points to the Chinese remainder theorem, where this all is explained in much greater detail. Dec 30, 2015 at 8:04