0
$\begingroup$

$$ a_i * x_i + b_i * x_j = N $$

$\text{given } a_i, b_i, N \in \mathbb{N}$

i want to find a solution where $x_i, x_j \in \mathbb{N}$ or output if there exists none.

What is the fastest way to calculate this?

$\endgroup$
  • 1
    $\begingroup$ Look in internet for diophantine equations $\endgroup$ – Trismegistos Jan 15 '15 at 14:48
  • 1
    $\begingroup$ diophantine equations are looking for solutions in $\mathbb{Z}$ $\endgroup$ – user3613886 Jan 15 '15 at 14:49
  • $\begingroup$ So filter non natural solutions out $\endgroup$ – Trismegistos Jan 15 '15 at 16:07
  • 1
    $\begingroup$ But how there can be infinitely many solutions in $\mathbb{Z}$ $\endgroup$ – user3613886 Jan 15 '15 at 16:09
  • 1
    $\begingroup$ In the future, we expect you to make a serious effort on your own before asking and to tell us in the question what you've tried, any approaches you considered but rejected (e.g., why you rejected the extended Euclidean algorithm, methods for solving diophantine equations, etc.). Anticipate possible questions and address them proactively in the quesiton. $\endgroup$ – D.W. Jan 15 '15 at 20:10
4
$\begingroup$

We can write $N$ as a linear combination of $a$ and $b$ if and only if $N$ is a multiple of $d=\gcd(a,b)$. Using the extended Euclidean algorithm we can find integers $x,y$ such that $ax+by=d$ and this in turn yields a solution of the form $\frac{N}{d}(ax+by)=N$. Now $\frac{Nx}{d}$ and $\frac{Ny}{d}$ will not necessarily be positive.

However, for all integer $k$, $a\frac{Nx+bk}{d}+b\frac{Ny-ak}{d}=N$ will also be a solution. To determine whether the equation has any natural solutions, we must simply determine the range of $k$ for which $Nx+bk$ is positive and the range for which $Nx-ak$ is positive and determine whether the ranges overlap.

In the case with 3 unknowns, $ax_1+bx_2+cx_3=N$, note that $bx_2+cx_3$ will always be a multiple of $\gcd(b,c)$. The problem thus comes down to solving $ax+y\gcd(b,c)=N$, picking an appropriate solution to that problem, and then solving $bx_2+cx_3=y\gcd(b,c)$. However it is not clear to me how to pick $y$ so that the second problem can be solved.

$\endgroup$
  • $\begingroup$ Very nice. Can this be generalized, if you have three terms? $\endgroup$ – user3613886 Jan 15 '15 at 17:48
  • $\begingroup$ I thought a bit about it, yes. I've updated my answer. $\endgroup$ – Tom van der Zanden Jan 15 '15 at 17:59
  • $\begingroup$ This does not work with selecting the maximum. $a_i = [2, 4, 8]$ and $N = 776$ then gcd(4,8) = 4, so it will calculate $2*0+4*194=776$, here y = 194 the one with the highest value. But there is no solution 2*0+4*y+8*z = 194 $\endgroup$ – user3613886 Jan 15 '15 at 21:58
  • $\begingroup$ It does lead to a solution, but there was a typo in my answer. You're supposed to look for a solution with $4y+8z=4*194=776$, not $194$. $\endgroup$ – Tom van der Zanden Jan 16 '15 at 10:29
  • $\begingroup$ Counterexample: $a_i = [1,20,25]$ and $N = 31$. Then $gcd(20,25) = 5$. $1*1+5*6 = 31$. But there is no solution $20*x+25*y = 5*6$. while there exists a solution $x_i = [6,0,1]$ $\endgroup$ – user3613886 Jan 16 '15 at 17:21

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.