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