Euclidean alg

  • Thread starter soandos
  • Start date
  • #1
166
0
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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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?
 
  • #3
166
0
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:
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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?
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,847
966
If [itex]x_1[/itex] and [itex]y_1[/itex] are integer solutions to ax+ by= c then so are [itex]x_n= x_1+ bn[/itex] and [itex]y_n= y_1- an[/itex], 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
166
0
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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
[tex]
(x, y) = (2, 1/3) + t (1, -5/2)
[/tex]
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
166
0
sorry haven't taken that either.
just seen the algorithm somewhere are started messing with it.
(x,y) means what?
 
  • #9
1
0
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 [Broken]

And I learned a new way to do multiplication : P
 
Last edited by a moderator:

Related Threads on Euclidean alg

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
1
Views
3K
Replies
6
Views
4K
Replies
2
Views
7K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
2K
Top