Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euclidean alg

  1. Jan 1, 2009 #1
    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
    then reversing to get the coefficients (find how many times each one appears)
    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. jcsd
  3. Jan 1, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
  4. Jan 1, 2009 #3
    yes for example

    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
    Last edited: Jan 1, 2009
  5. Jan 1, 2009 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    You sure about that?

    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?
  6. Jan 1, 2009 #5


    User Avatar
    Science Advisor

    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.
  7. Jan 1, 2009 #6
    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)
  8. Jan 1, 2009 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
  9. Jan 1, 2009 #8
    sorry haven't taken that either.
    just seen the algorithm somewhere are started messing with it.
    (x,y) means what?
  10. Feb 23, 2009 #9
    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: May 4, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook