Solving Equations of the Form Ax - By = 1

[soandos]

I know how the algorithm can be used to find a solution to an equation of the form
Ax - By = 1 where A and B are given.
I also know that there is more than one solution to this. how are the others found.
for example:
for 17x-11y=1
17=11+6
11=6+5
6=5+1
then reversing to get the coefficients (find how many times each one appears)
17-11-(11-(17-11))
yielding 2*17-3*11.
there are infinitely many more solutions to this.
Anyone know how they are found?
when i plotted the first hundred solutions they seemed linear, but that might be wrong.

 

[Hurkyl]

there are infinitely many more solutions to this.
Anyone know how they are found?
when i plotted the first hundred solutions they seemed linear, but that might be wrong.

Well, it is a linear system of equations consisting of one equation and two variables... Sure, only wanting the integer solutions is a wrinke, but are there any others?

 

[soandos]

yes for example
{244,377}
{1201,1856}
{1630,2519}
{3511,5426}
{5876,9081}

to the best of my knowledge they all lie on a line with a slope of 19/17

EDIT: also, does anyone know how to solve ax-by-cz...==1 for integer solutions only?
EDIT: While all of the solutions are on the line, they are not evenly spaced
EDIT: While they are not evenly spaced, the equation for the difference between spaces is
y=17/11x+0.

 

[Hurkyl]

EDIT: also, does anyone know how to solve ax-by-cz...==1 for integer solutions only?

Well, it's a linear equation in three variables... What do the ideas behind the Euclidean algorithm give you?

While all of the solutions are on the line, they are not evenly spaced

You sure about that?

While they are not evenly spaced, the equation for the difference between spaces is
y=17/11x+0.

Right. And for what values of x will y be an integer? Can you write the general solution in the usual form

(x, y) = (a, b) + t (c, d)​

with the twist that a, b, c, d, t are all integers?

 

[HallsofIvy]

If x_1 and y_1 are integer solutions to ax+ by= c then so are x_n= x_1+ bn and y_n= y_1- an, for n any integer, because a(x_1+ bn)+ b(y_1- an)= ax_1+ by_1+ abn- abn= ax_1+ by_1= c. It's only slightly harder to show that any integer solutions to that equation must be of that form.

 

[soandos]

thanks.
hurkyl:
ax-by-cz = d
I am not sure. i know that i can find the gcd of all three (just have to do it two at a time), and i know that i can find solutions with any two of the variables, but that does not get me the third.
is it possible to solve for any any two (make z zero), then solve it again for z = 1, and since it is linear in three variables can i just plot the line, and all solutions will be on that line?

with respect to the last part, i am not sure what you mean (i have never taken number theory)

 

[Hurkyl]

with respect to the last part, i am not sure what you mean (i have never taken number theory)

In your linear algebra class, when you solve systems of equations, you often express the general answer in a form like
<br /> (x, y) = (2, 1/3) + t (1, -5/2)<br />
You can do the same thing with integer systems of equations, but with the added feature that everything in sight is an integer. (And done to ensure that no solutions would be missed)

 

[soandos]

sorry haven't taken that either.
just seen the algorithm somewhere are started messing with it.
(x,y) means what?

 

[blakem]

A little bit after half-way through this video, the prof. explains how to get all solutions. http://cmes.uccs.edu/Spring2008/Math311/Videos/Math311Lecture5.mov

And I learned a new way to do multiplication : P