World's most popular travel blog for travel bloggers.

[Solved]: Fastest way to find natural solutions to Linear equation

, , No Comments
Problem Detail: 

$$ 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?

Asked By : user3613886

Answered By : Tom van der Zanden

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37254

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback