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$
5
  • 1
    $\begingroup$ Look in internet for diophantine equations $\endgroup$ Jan 15 '15 at 14:48
  • 1
    $\begingroup$ diophantine equations are looking for solutions in $\mathbb{Z}$ $\endgroup$ Jan 15 '15 at 14:49
  • $\begingroup$ So filter non natural solutions out $\endgroup$ Jan 15 '15 at 16:07
  • 1
    $\begingroup$ But how there can be infinitely many solutions in $\mathbb{Z}$ $\endgroup$ 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$
5
  • $\begingroup$ Very nice. Can this be generalized, if you have three terms? $\endgroup$ Jan 15 '15 at 17:48
  • $\begingroup$ I thought a bit about it, yes. I've updated my answer. $\endgroup$ 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$ 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$ 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$ 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.