Results are out! Find what you need...fast. Get quick advice or join the chat
x

Unlock these great extras with your FREE membership

  • One-on-one advice about results day and Clearing
  • Free access to our personal statement wizard
  • Customise TSR to suit how you want to use it

Euclidean Algorithm

Announcements Posted on
Rate your uni — help us build a league table based on real student views 19-08-2015
  1. 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
  2. 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
  3. 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
  4. Offline

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

    If it doesn't post and I'll show you
  5. Offline

    ReputationRep:
    I don't get what you mean
  6. 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
  7. 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
  8. Offline

    ReputationRep:
    Thats fine, but how would you find the answer if it was much larger?
  9. 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)...
  10. 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?
  11. 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...
  12. 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.
  13. 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?
  14. 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.
  15. 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
  16. 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.
  17. 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
  18. 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
  19. 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
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

New on TSR

Rate your uni

Help build a new league table

Poll
How do you read?
Study resources
Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.