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

How to do the extended euclidean algorithm

  1. Jan 29, 2012 #1
    Here's the definition I have:
    Extended Euclidean algorithm
    Takes a and b
    Computes r, s, t such that
    r=gcd(a, b) and, sa + tb = r
    (only the last two terms in each of these sequences at any point in the algorithm)
    Corollary. Suppose gcd(r0, r1)=1. Then
    r_1-1 mod r_0=t_m mod r_0.

    The example is in the attached image.

    I don't understand the steps used to obtain all the values in the table or how to get the inverse which i'm assuming is -8 in that example?
    If someone could guide me though it that would be very helpful, I've been struggling with it for hours now.

    Thank you!
     

    Attached Files:

  2. jcsd
  3. Jan 30, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    The goal here is to find the multiplicative inverse of 28, (1/28), modulo 75 so that

    (t x 28) mod (75) = 1

    it will also turn out that

    (s x 75) mod (28) = 1

    The algorithm iterates until it finds

    (s x 75) + (t x 28) = 1

    where s and t will have opposite signs. This only works if a and b are coprime, gcd(a,b) = 1. (Otherwise the algorithm iterates to 0 and the previous remainder will not be 1). Note that there is no inverse for 15 mod (75), since gcd(15, 75) = 5. For finite field math modulo(a), a should be a prime number.

    Wiki article:

    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

    Modulo(x) should have the same sign as x, in this case the range of (...) mod (75) are positive integers in the set {0 ... 74}.

    (-8) mod (75) = 67, resulting in

    (67 x 28) mod (75) = 1
     
    Last edited: Jan 30, 2012
  4. Jan 30, 2012 #3
    I still don't understand it. I need someone to literally walk me through it so that I understand each step. I get what the algorithm is for but I don't understand that example I posted.

    So the inverse is 67 in this case?
     
  5. Jan 30, 2012 #4

    rcgldr

    User Avatar
    Homework Helper

    Yes 67 x 28 = 1876, and the nearest multiple of 75 less than 1876 is 25 x 75 = 1875, so (67 x 28) mod (75) = 1. Divide (67 x 28) / 75 = 1876/75, quotient = 25, remainder = 1. You could also use (-8 x 28) / 75, = -224/75, quotient = -3, remainder = 1.

    The article linked to below includes a better explanation of the extended euclidean algorithm, but without the requirement that the gcd(a,b) = 1.

    extended-euclidean.html

    It would help me to futher explain extended euclid algorithm if I knew what class your are taking, a math class, a programming class, something related to finite field math? If this is for finite field math, then 75 was a bad example because it's not a prime number. If a prime number was used instead, such as 79, then all integers from 1 to 78 would have an inverse modulo 79. This isn't true for 75, since any number that is a multiple of 3 or 5 will not have an inverse modulo 75.
     
    Last edited: Jan 30, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to do the extended euclidean algorithm
Loading...