Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

enter image description here

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 do they come up with that notation/equation that represents all the integer solutions ? I am talking about the very last line.

share|cite|improve this question
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 $$

share|cite|improve this answer

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


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

share|cite|improve this answer

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).

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.