Results 1 to 4 of 4

Math Help - Implementation of Euclid's Algorithm

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    Implementation of Euclid's Algorithm

    I'm trying to understand this implementation of Euclid Algorithm.

    First as usual the division algorithm is applied to n and a. Then repeatedly to pairs of remainders until the remainder 0 occurs.

    n = q_{1}a + r_{1}
    a = q_{2}r_{1} + r_{2}
    r_{1} = q_{3}r_{2} + r_{3}
    .
    .
    .
    r_{m-2} = q_{m}r_{m-1} + r_{m}
    r_{m-1} = q_{m+1}r_{m}

    Secondly( and this is where the problem starts) al the remainders up to r_{m-1} are eliminated from all but the last of the equation from the above step to obtain an equation of the form ab = kn + 1 with b in Z_{n}

    Firstly I don't understand where the idea of eliminating the remainders comes from and what purpose it is serving here. At this point my understanding was to express the final equation in terms multiples of the values n and a using the equations obtained from the first step.

    The method the implementation uses to eliminate the remainders is by multiplication by a suitable constant.

    It is said the constant must satisfy c_{j+2} = q_{j+1}c_{j+1} + c_{j} why is this? How can the remainders be eliminated through multiplication?

    I'm very confused about what the implementation is doing here and how it is doing it.
    Last edited by alyosha2; May 16th 2012 at 08:21 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2009
    Posts
    109

    Re: Implementation of Euclid's Algorithm

    I should probably add that the implementation is trying to find the multiple inverse of a.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,326
    Thanks
    1298

    Re: Implementation of Euclid's Algorithm

    A assume that by "multiple inverse of a" you mean the multiplicative inverse of a modulo p.

    First, you do NOT want to "repeat until the remainder 0 appears". a has an inverse modulo p if and only if a and p are "relatively prime" which is always true if p is a prime number. Instead, you want to get a remainder of 1.

    If b is the multiplicative inverse of a, modulo p, then ab= np+ 1 or ab- np= 1.

    For example, to find the multiplicative inverse of 6, modulo 11, we need to solve the diophantine equation 6x- 11n= 1. 6 divides into 11 once with remainder 5: 11(1)- 6(1)= 5. 5 divides into 6 once with remainder 1: 6(1)- 5(1)= 1. Replace "5" in that equation with 11(1)- 6(1) from the previous equation: 6(1)- (11(1)- 6(1))(1)= 6(2)- 11(1)= 1. The multiplicative inverse of 6, modulo 11, is 2: 6(2)= 12= 11+ 1

    Similarly, to find the multiplicative inverse of 5 modulo 17, we need to solve the diophantine equation 5x- 17n= 1. 5 divides into 17 three times with remainder 2: 17(1)- 5(3)= 2. 2 divides into 5 twice with remainder 1: 5(1)- 2(2)= 1. Again, we can replace that "2" by 17(1)- 5(3): 5(1)- 2(17(1)- 5(3)= 7(5)- 2(17)= 3 so the multiplicative inverse of 5 modulo 17 is 7: 5(7)= 35= 2(17)+ 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,283
    Thanks
    673

    Re: Implementation of Euclid's Algorithm

    the euclidean algorithm is generally invoked to find the inverse of a unit a modulo n.

    this only works if gcd(a,n) = 1. to see why, suppose that gcd(a,n) = d > 1 (with 0 < a < n).

    then a = ds and n = dt for some positive integers 1 < s,t < n.

    so at = (ds)t = (sd)t = s(dt) = sn = 0 (mod n), so a is a zero-divisor in Zn.

    so if a had some inverse (mod n), say x, we would have:

    t = (ax)t = (xa)t = x(at) = x0 = 0, contradicting how we found t (above).

    however, if gcd(a,n) = 1, then there are integers u,v such that:

    au + nv = 1.

    so au + nv ≡ 1 (mod n).

    but au + nv ≡ au + 0v ≡ au (mod n).

    so to explicitly find an inverse, we need to just compute u (mod n).

    well, in general, if gcd(a,b) = d, we have r,s such that ra + sb = d. the question is: how do we find this pair of integers r and s?

    let's assume that a < b (since gcd(a,b) = gcd(b,a), and gcd(a,a) is obviously a, and in that case we can choose r = 1, s = 0).

    note first, that gcd(a,b) = gcd(a,b-a) = gcd(a,b-qa), as long as b-qa > 0.

    if we write b = qa + r, where 0 ≤ r < a, we have:

    gcd(a,b) = gcd(r,a).

    we can then write:

    a = q'r + r'

    so that we have: gcd(a,) = gcd(r,a) = gcd(r',r). note our numbers are getting smaller each time.

    eventually, we'll reach a point where:

    rm-1 = qm+1rm + 0.

    this tells us that gcd(a,b) = rm = gcd(rm-1,rm).

    this lets us find r and s by "working backwards".

    for example, gcd(16,38) = 2. to find r,s such that 16r + 38s = 2, we use the algorithm:

    38 = (2)(16) + 6
    16 = (2)(6) + 4
    6 = (1)(4) + 2
    4 = (2)(2) + 0 <--back up one step to find the gcd.

    from step 3, we have: 2 = 6 - 4.
    from step 2, we have 4 = 16 - (2)(6).

    combining these two, we get:

    2 = 6 - 4 = 6 - 16 + (2)(6) = (1+2)(6) - 16 = (3)(6) - 16.

    from step 1, we have: 6 = 38 - (2)(16), and combining this with our previous "combo" we have:

    2 = (3)(6) - 16 = (3)(38 - (2)(16)) - 16 = (3)(38) - ((3)(2) + 1)16 = (3)(38) - (7)(16) = (3)(38) + (-7)(16).

    so r = -7, and s = 3 (and it is easy to check that (-7)(16) + (3)(38) = -112 + 114 = 2).

    when gcd(a,b) = 1, using this algorithm allows us to find r,s such that ra + sb = 1.

    for example, we will find gcd(7,16):

    16 = (2)(7) + 2
    7 = (3)(2) + 1
    2 = (2)(1) + 0 <---back up one step, gcd is 1.

    so 1 = 7 - (3)(2) = 7 - (3)[16 - (2)(7)] = 7 - 3(16) + (6)(7) = (1 + 6)(7) - 3(16) = (7)(7) + (-3)(16).

    so r = 7, and s = -3.

    this means that the inverse of 7 (mod 16) is 7. to check, note that:

    (7)(7) = 49 ≡ 1 (mod 16) (since 49 = 3(16) + 1).

    here is another example:

    find the inverse of 15 mod 41.

    we first want to find r,s such that 15r + 41s = 1.

    41 = (2)(15) + 11
    15 = (1)(11) + 4
    11 = (2)(4) + 3
    4 = (1)(3) + 1
    3 = (3)(1) + 0 <---back up one step, and (ok, it's getting repetitious by now)

    so 1 = 4 - 3 = (15 - 11) - (11 - 8) = 15 - 2(11) + 8 so far, so good, but we need 15's and 41's.

    = 15 - 2(41 - 2(15)) + 2(4) = 15 - 2(41) + 4(15) + 2(15 - 11) = 15 - 2(41) + 4(15) + 2(15) - 2(11)

    = 7(15) - 2(41) - 2(11) = 5(15) - 2(41) - 2(41 - 2(15)) = 7(15) - 4(41) + 4(15) = 11(15) + (-4)(41)

    so we get r = 11, s = -4, so the inverse of 15 mod 41 is 11 (and indeed 165 ≡ 1 (mod 41)).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2012, 11:32 AM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  3. Probability Transition Matrix Implementation Algorithm
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 12th 2009, 03:41 AM
  4. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  5. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM

Search Tags


/mathhelpforum @mathhelpforum