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

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .