Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Back Substitution (Euclidean)

  • 01-05-2019 4:34pm
    #1
    Registered Users Posts: 13,385 ✭✭✭✭


    Hi All,

    I'm having some difficulty in wrapping my head around using the extended euclidean algorithm. In following this video I've gotten to the back substitution without issue but, perhaps it's because I'm using 4-digit numbers for P & Q instead of this, more simplified version, I'm struggling to comprehend how the back substitution section works exactly.

    I'm aware of the rules so it's worth pointing out I'm looking for a better example or a pointer on this, where possible & it would be much appreciated!


Comments

  • Registered Users Posts: 1,595 ✭✭✭MathsManiac


    The video looks fairly clear, so I'm not sure what the trouble is.
    Are there steps you don't follow? If so, which line is the first one you don't follow?
    Or is it the whole thrust of what you're trying to do here that you're not clear about?
    The point of the back-substitution step is to express the gcd (1 in this cae) as a linear combination of the two original numbers. The idea is that you're working your way backwards through the steps of the original algorithm, as each step allows you to write the gcd as a linear combination of the two numbers in play at that stage.

    If you're still stuck, try posting the example yuo're trying to do, and show us how far you got.


  • Registered Users Posts: 13,385 ✭✭✭✭D'Agger


    Appreciate the response

    In my example for step one I have a large number for X which I think is throwing me off a bit:

    Step 1 is fine, I believe this is correct.

    24591840 x + 31 y = 1
    24591840 = 793285 (31) + 5
    31 = 6(5) + 1


    When attempting to work back I'm just unsure if the below is correct, as per your definition of it. Am I to sub out the 5 in this instance with the remainder of the equation from the line above? As in:

    1 = 31 - 6(5)
    1 = 31 - 6(24591840 - 793285(31))


  • Registered Users Posts: 1,595 ✭✭✭MathsManiac


    Yes.

    And then you use the distributive law to gather together the 31s. If you write it out really fully, it's this:

    1 = 31 - 6(24591840 - 793285(31))
    = 31 - 6(24591840) + 6(793285)(31)
    = (1+6(793285))(31) - 6(24591840)
    = 4759711(31) - 6(24591840)


  • Registered Users Posts: 13,385 ✭✭✭✭D'Agger


    Yes.

    And then you use the distributive law to gather together the 31s. If you write it out really fully, it's this:

    1 = 31 - 6(24591840 - 793285(31))
    = 31 - 6(24591840) + 6(793285)(31)
    = (1+6(793285))(31) - 6(24591840)
    = 4759711(31) - 6(24591840)
    Ah okay I did have that in my workings I just really didn't think it was correct so ended up going over it a few times and confusing myself further with some different computations

    Appreciate the responses thanks very much MathsManiac!

    *Edit:

    Just to confirm what was confusing me and if you wouldn't mind confirming why I might have been confused about this - why are you employing 6 twice in the below equation:

    = (1+6(793285))(31) - 6(24591840)


  • Registered Users Posts: 1,595 ✭✭✭MathsManiac


    Well the 6 is already there twice in the preceding line, so maybe I should step back to there to explain.

    It's just the distributive law, otherwise referred to as expanding the brackets: a(b+c) = ab + ac.

    In this case, 31 - 6(a - b) = 31 - 6a + 6b.
    Since I'm removing the brackets that the -6 is in front of, I have to multiply both of the terms that were inside the brackets by -6.

    In the next line, the one you have highlighted, I just gathered the terms that have the 31 in them and factored out the 31 (also an application of the distributive law - just the other way around).


  • Advertisement
  • Registered Users Posts: 13,385 ✭✭✭✭D'Agger


    Well the 6 is already there twice in the preceding line, so maybe I should step back to there to explain.

    It's just the distributive law, otherwise referred to as expanding the brackets: a(b+c) = ab + ac.

    In this case, 31 - 6(a - b) = 31 - 6a + 6b.
    Since I'm removing the brackets that the -6 is in front of, I have to multiply both of the terms that were inside the brackets by -6.

    In the next line, the one you have highlighted, I just gathered the terms that have the 31 in them and factored out the 31 (also an application of the distributive law - just the other way around).
    I have you - thanks for clarifying!


Advertisement