# Euclidean alg

1. Jan 1, 2009

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

2. Jan 1, 2009

### Hurkyl

Staff Emeritus
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?

3. Jan 1, 2009

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

Last edited: Jan 1, 2009
4. Jan 1, 2009

### Hurkyl

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

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?

5. Jan 1, 2009

### HallsofIvy

Staff Emeritus
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.

6. Jan 1, 2009

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

7. Jan 1, 2009

### Hurkyl

Staff Emeritus
In your linear algebra class, when you solve systems of equations, you often express the general answer in a form like
$$(x, y) = (2, 1/3) + t (1, -5/2)$$
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)

8. Jan 1, 2009

### soandos

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

9. Feb 23, 2009