0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are all the variables $k_i$ required to be integers? $\endgroup$ – JimmyK4542 Dec 30 '15 at 5:31
  • $\begingroup$ yes, all $k_i$ are integers. $\endgroup$ – Daga Dec 30 '15 at 5:33
  • $\begingroup$ 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. $\endgroup$ – Ivan Neretin Dec 30 '15 at 6:23
  • $\begingroup$ what if all pairs have gcd=1? $\endgroup$ – Daga Dec 30 '15 at 6:39
  • $\begingroup$ Forget that, I have a better idea. $\endgroup$ – Ivan Neretin Dec 30 '15 at 6:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i can't understand how u reached to LCM, also how to get individual values of $k_i$? $\endgroup$ – Daga Dec 30 '15 at 6:47
  • $\begingroup$ 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. $\endgroup$ – Ivan Neretin Dec 30 '15 at 6:53
  • $\begingroup$ what is $a_{combined}$? $\endgroup$ – Daga Dec 30 '15 at 7:15
  • $\begingroup$ $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. $\endgroup$ – Ivan Neretin Dec 30 '15 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.