Logical proof for a value derivable by a linear combination

Is there a logical basis to finding values provided possibly by a linear combination of integers. As the integers are closed under addition and hence their linear combination should be also. Hence, the integer points generated by two integers can be plotted on a lattice grid, extending infinitely. There can be multiple linear combinations, in other words, for two integer quantities. These two quantities can be, in the case of gcd computation, the divisor ($a$) and dividend ($d$).

If I want to dis-prove that a given linear combination can exist, then the approach is:

Say, the linear combination of two 'not' co-prime integers can never be $1$, as there will be no lattice point(s) generated as for : $2x + 4y = 1$. There will always be non-integral solutions, and any integer (lattice point) value of $x$ and $y$ will not work.

But, will the dis-proof above will work generally, i.e. if I want to prove that a given value can be generated or not by a linear combination. I request some better sort of way that will work generally for proving and disproving the feasibility of a given value for a given linear combination.

• I can't really understand what you're aiming at, but the integer combinations of $a$ and $b$ are exactly the multiples of $\operatorname{gcd}(a,b)$. This goes by the name of Bézout's lemma. – user228113 Nov 24 '17 at 4:57
• I hope my edit to OP makes it clear that similar to the dis-proof for the possibility of not co-prime integers having a value (for their linear combination) of 1, I want a similar proof for the opposite case. – jiten Nov 24 '17 at 5:17
• @DavidReed I have edited the OP to make it most clear. I would request some details on the feasible way to show existence of a linear combination, and for an efficient algorithm to find a given integer combination. – jiten Nov 24 '17 at 5:37

1 Answer

Let $d = gcd(a,b)$. Then there exists $x,y$ such that $ax+by=n$ if and only if $d|n$

The extended Euclidean algorithm is the algorithm one would use to find $x$ and $y$.

To prove no such integer combination exists, one would again use the euclidean algorithm to find the gcd, and then simply show that n is not a multiple of the gcd.

EDIT-

Heres how you would prove an integer combination exists. Say you want to know if there are integers $x$ and $y$ such that $ax+by = n$. Let $d = gcd(a,b)$ You can always find integers $u$ and $v$ such that $au + bv = d.$ You can find $u$ and $v$ via the extended Euclidean algorithm, which also, as an added benefit, will compute $d$. If n is not a multiple of $d$, then no integer combination is possible.

Otherwise, let $k = n/d$ so that $n = kd$. Set $x= ku$ and $y = kv$, then

$$ax+by= aku+bkv = k(au+bv) = kd = n$$

$\\$

Here is an example. Lets say I want to find solutions to $$135x+48y = 3375$$

I use the Euclidean Algorithm as follows:

\begin{align} &(135,48) \to 135= 2*48 + 39 \to \quad 39 = 135 - (2)(48) \\ &(48,39) \to \quad 48 = 1*39 + 9 \to \quad 9 = 48 - (1)(39)\\ &(39,9) \to \quad 39 = 4*9+ 3 \to \quad 3 = 39 - (4)(9) \\ &(9,3) \to \quad 9 = 3*3 + 0 \\ &(3,0) \to \quad \text{done} \end{align}

So $3$ is the gcd. $3375/3 = 1125$ which is a whole number. Therefore a solution exists. Now to find it:

We now work backwards:

\begin{align} 3 =& \ 39-(4)(9) \\ =& \ 39 - (4)(48-(1)(39)) \\ =& \ 135 - (2)(48) - (4)(48-(1)(135-(2)(48))) \\ =& \ 135 - (2)(48) - (4)(48-135+(2)(48)) \\ =& \ 135 -(2)(48) - (4)(48) +(4)(135)-(8)(48) \\ =& \ (5)(135) + (-14)(48) \end{align}

Thus

$$(135)(5)+ (48)(-14) = 3$$

Now since $3375/3 = 1125$, we multiply the whole equation by $1125$ and get

$$(135)(5)(1125) + (48)(-14)(1125) = (3)(1125)$$

$$\\$$ $$\implies (135)(5625)+(48)(-15750) = 3375$$

• @jiten I meant to change that. It should be 135x+48y and not 135x+6y. I first used six but the Euclidean alg was too short (like 1 step) so I changed it to one that provided a better example. Its fixed now. – David Reed Nov 24 '17 at 9:11
• Thanks for removing confusion. – jiten Nov 24 '17 at 9:14
• @jiten The Euclidean algorithm is a good algorithm to know. Its used in several other places in algebra and number theory. Equations like this, $ax+by = n$ are called "linear Diophantine equations.", in case you have any interest in researching further. – David Reed Nov 24 '17 at 9:17