Results are out! Find what you need...fast. Get quick advice or join the chat
Hey! Sign in to get help with your study questionsNew here? Join for free to post

Euclidean Algorithm

Announcements Posted on
Applying to uni this year? Check out our new personal statement advice hub 28-11-2014
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    Find integers m and n such that 7m + 55n = 1

    Haven't been taught this yet but have been expected to do it for homework, can someone tell me how I go about doing it please
    • 7 followers
    Offline

    ReputationRep:
    Do you know how to use the Euclidean Algorithm to find the highest common factor?

    You could always guess. Try n = 1 as a starting point
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    55 = 7 x 7 + 6 --> (55,7) = (7,6)

    7 = 6 x 1 + 1 --> (7,6) = (6,1)

    6 = 1 x 6 + 0 --> (6,1) = (1,0)

    Therefore the hcf = 1
    • 7 followers
    Offline

    ReputationRep:
    Now work that backwards (if that makes sense)

    If it doesn't post and I'll show you
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    I don't get what you mean
    • 7 followers
    Offline

    ReputationRep:
    (Original post by bekahchu)
    55 = 7 x 7 + 6 --> (55,7) = (7,6)

    7 = 6 x 1 + 1 --> (7,6) = (6,1)

    6 = 1 x 6 + 0 --> (6,1) = (1,0)

    Therefore the hcf = 1
    Going backwards

    7 = 6 \times 1 + 1
    7 - 6 \times 1 = 1
    7 - (55 - 7 \times 7 ) \times 1 = 1

    Unfortunately its not very clear when the gcd of the numbers is 1, the method used is slightly more obvious when you have a larger number as the gcd
    • 0 followers
    Offline

    ReputationRep:
    Okay I don't know what way you people have gone about solving it, I haven't done questions like this either, hence why I am posting my solution, as I'm not sure if its the correct approach.

    But I solved it like this... (Not sure if this is ideal, but it gave me a solution)

    7 = 7 x 1, -7 x -1
    55 = 5 x 11, -5 x -11, 55 x 1, -55 x -1

    Common factors are 1 and -1

    Since the coefficents of m and n are so large and we are looking for integers of m and n...

    |m,n| greater than and equal to 1...

    from this we know that if +/- m, then -/+ n to be possible to get a end value of 1 (Basically if one is positive the other is negative).

    Test m = 1
    7 + 55n = 1
    55n = -6
    n = -6/55

    Test m = -1
    -7 + 55n = 1
    55n = 8
    n = 8/55

    Test n = 1
    7m + 55 = 1
    7m = -54
    m = -54/7

    Test n = -1
    7m -55 = 1
    7m = 56
    m = 8

    Solution found... n = -1 and m = 8
    • 7 followers
    Offline

    ReputationRep:
    Thats fine, but how would you find the answer if it was much larger?
    • 0 followers
    Offline

    ReputationRep:
    (Original post by SimonM)
    Thats fine, but how would you find the answer if it was much larger?
    Well I haven't really done these questions before, but I suppose I would test the values that had priority first i.e. the highest modulus common factor...

    So I should find the answer after the first 4 tests... (- value of the common factor the then + value, on both n and m)...
    • 7 followers
    Offline

    ReputationRep:
    (Original post by Koudoo)
    So I should find the answer after the first 4 tests... (- value of the common factor the then + value, on both n and m)...

    Wha?
    • 0 followers
    Offline

    ReputationRep:
    Im sorry my explanation isn't too good, I am basically saying that I should be able to solve it in 4 tests, if there are 2 integer values to be found, and the rest known...

    As I would test the right values first, the highest modulus common factors...
    • 7 followers
    Offline

    ReputationRep:
    (Original post by Koudoo)
    Im sorry my explanation isn't too good, I am basically saying that I should be able to solve it in 4 tests, if there are 2 integer values to be found, and the rest known...

    As I would test the right values first, the highest modulus common factors...
    Really? Could you write out your method in a way that I can understand then?

    Could you demonstrate with

    2322m + 654n = 6.
    • 0 followers
    Offline

    ReputationRep:
    Okay, I will try, Im not sure if it works well, hence why I posted my solution lol...

    m and n are integers right?
    • 0 followers
    Offline

    ReputationRep:
    You could have a look here:
    http://mathworld.wolfram.com/DiophantineEquation.html

    I seem to remember that we had three different techniques for solving simple linear diophantine equations at school (one of which was the extended Euclidean algorithm), but it's been years since I've done that and I can't really remember it properly.
    • 7 followers
    Offline

    ReputationRep:
    (Original post by Sinuhe)
    You could have a look here:
    http://mathworld.wolfram.com/DiophantineEquation.html

    I seem to remember that we had three different techniques for solving simple linear diophantine equations at school (one of which was the extended Euclidean algorithm), but it's been years since I've done that and I can't really remember it properly.
    I can only think of two, but if you think of the third, please enlighten me
    • 0 followers
    Offline

    ReputationRep:
    (Original post by SimonM)
    I can only think of two, but if you think of the third, please enlighten me
    I'll have a look at my number theory notes when I get back home (in late December, unfortunately) and I'll let you know if there really are three that we used (see, my memory sometimes plays games with me ... :p: ).
    It's been four years since we did that, but I think one was using congruence modulo something to simplify the equation, one was this Euclidean algorithm, and one was using some sort of weird tabulation; I'm not really sure though. In the end they're probably all the same method in different disguises anyway.
    • 0 followers
    Offline

    ReputationRep:
    (Original post by SimonM)
    Going backwards

    7 = 6 \times 1 + 1
    7 - 6 \times 1 = 1
    7 - (55 - 7 \times 7 ) \times 1 = 1

    Unfortunately its not very clear when the gcd of the numbers is 1, the method used is slightly more obvious when you have a larger number as the gcd
    When working backwards shouldn't it be...

    1 = 0 x 6 + 1 x 1
    1 = 1 x 7 - 1 x 6
    1 = 1 x 55 + -8 x 7

    Giving the solutions of 1 and -8...

    (Original post by SimonM)
    Really? Could you write out your method in a way that I can understand then?

    Could you demonstrate with

    2322m + 654n = 6.
    Okay yeah, I can't use it with too large numbers which is a shame :woo:

    But I still sloved your question anways...

    I had to use the a variation of the Euclidean Algorithm

    2322m + 654n = 6
    387m + 109n = 1

    387 = 109 x 3 + 66
    109 = 60 x 1 + 49
    60 = 49 x 1 + 11
    49 = 11 x 4 + 5
    11 = 5 x 2 + 1

    Then...

    1 = 0 x 5 + 1 + 1
    1 = 1 x 11 - 2 x 5
    1 = -2 x 49 + 9 x 11
    1 = 9 x 60 - 11 x 49
    1 = -11 x 109 + 20 x 60
    1 = 20 x 387 - 71 x 109

    So the solutions are m = 20 and n = -71
    • 7 followers
    Offline

    ReputationRep:
    (Original post by Koudoo)
    I had to use the a variation of the Euclidean Algorithm
    Yeah, thats called the extended Euclidean Algorithm and is the one I demonstrated earlier in the thread
    • 0 followers
    Offline

    ReputationRep:
    Oh, my bad, I should have read everything more thoroughly...

    I wonder where the thread starter has gone, since her question has been answered, but we got no reply :< …

Reply

Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  3. this can't be left blank

    6 characters or longer with both numbers and letters is safer

  4. this can't be left empty
    your full birthday is required
  1. By joining you agree to our Ts and Cs, privacy policy and site rules

  2. Slide to join now Processing…

Updated: September 28, 2008
New on TSR

Vote for your favourite Christmas film

Win a bundle of Xmas DVDs

Article updates
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.