# General solution using Euclidean Algorithm

I was able to come up with the integer solution that they also have in the textbook using the same method they used but I am really puzzled how they come up with a solution for all the possible integer combinations...how do they come up with that notation/equation that represents all the integer solutions ? I am talking about the very last line.

-
This illustrates the applicability of Number Theory to real life. Not. –  André Nicolas Feb 12 '12 at 19:11
@AndréNicolas Your Comment illustrates the applicability of Borat to the daily life. :P –  user21436 Feb 12 '12 at 19:24

A different way to write what they have in your book is the Euclid-Wallis Algorithm. $$\begin{array}{r} &&1&1&1&3\\ \hline 1&0&1&-1&2&-7\\ 0&1&-1&2&-3&11\\ 957&609&348&261&87&0 \end{array}$$ which says that $87=(2-7n)\cdot957+(-3+11n)\cdot609$.

To scale the result ($87$), scale the particular solution ($2$ and $-3$), but not the coefficients of $n$ ($-7$ and $11$). That is, to get the general solution for $15921$, scale by $183$ (since $15921=87\cdot183$): $$15921=(366-7n)\cdot957+(-549+11n)\cdot609$$ Get a smaller particular solution using $n=50$, and the general solution with $m=n-50$: $$15921=(16-7m)\cdot957+(1+11m)\cdot609$$

-

Since $\def\lcm{\operatorname{lcm}}\gcd(957,609)=87$, with $\gcd(a,b)\lcm(a,b)=ab$ we have

$$7\cdot957=\frac{609}{87}\cdot957=\lcm(957,609)=\frac{957}{87}\cdot609=11\cdot609\;.$$

Thus starting with any solution you can subtract $7$ from $x$ and add $11$ to $y$ to get another solution.

-

A general rule in life: When you have a linear equation(s) of the form $f(x_1,x_2,\dots, x_n)=c$, find one solution to the equation and then find a general solution to $f(x_1,\dots,x_n)=0$ and now you can obtain the general solution for the initial equation by adding the special solution you found with the general solution of the second, homogeneous, equation.

In our case the homogeneous equation is $957x+609y=0$. Divide by the gcd 87 to obtain $11x=-7y$. So the general solution for this equation is $(-7n,11n)$ for integer $n$ (you must multiply both sides by something that will give you the LCM times an integer).

-

I solved the problem...joriki your solution is correct but I found out what I didnt know after reading some text in book.... it basically says that if you want the complete solution of an equation, you first solve for a unique solution so find an x and y that works....then take the x and add to it the integer coefficient of y/GCD *n. Take your y solution you found and subtract from it integer coefficient of x/GCD *n. That is your complete solution for all integers n

-

It's a special case of the following ubiquitous principle: the general solution of a nonhomogeneous linear equation is given by adding any particular solution to the general solution of the associated homogeneous equation. Namely, if $\rm\:L\:$ is a linear map then one easily proves

Lemma $\ \$ If $\rm\ L\:v\ =\ n\$ then $\rm\ L\:u\ =\ n\ \iff\ 0\ =\ L\:v - L\:u\ =\ L\:(v-u)$

Therefore $\rm\ L^{-1}(n)\ =\ v\ +\ ker\ L\ =\:\:$ particular + homogeneous solutions.

In your case $\rm\ L\:v\: =\: L(x,y)\: =\: 957\:x + 609\:y$ is linear, being the sum of linear functions.

A well-known example from calculus is when $\rm\: L = D\:$ is the derivative. The general solution of $\rm\:D\:f = g\:$ is the sum of a particular solution, i.e. an antiderivative $f = \int g,\:$ plus an integration constant, i.e. a solution of the homogeneous equation $\rm\:D\:f = 0\:$. For more see these answers.

-