Euclid's Extended AlgorithmDate: 09/16/2001 at 23:11:24 From: Anna Subject: Extended euclid's algorithm Can you please state for me the steps of Euclid's extended algorithm in simple terms? All of the things I have been able to find about it on the Internet have just confused me. Thank you! Anna Date: 09/17/2001 at 14:08:13 From: Doctor Rob Subject: Re: Extended euclid's algorithm Thanks for writing to Ask Dr. Math, Anna. Start the Euclidean Algorithm as usual, with two positive integers r(1) and r(2) as input: r(1) = q(3)*r(2) + r(3), 0 <= r(3) < r(2), r(2) = q(4)*r(3) + r(4), 0 <= r(4) < r(3), r(3) = q(5)*r(4) + r(5), 0 <= r(5) < r(4), ... Now notice that the remainders r(3), r(4), r(5), and so on, can be expressed as combinations of the two input numbers, r(1) and r(2), by substitution: r(3) = 1*r(1) - q(3)*r(2), r(4) = 1*r(2) - q(4)*r(3), = 1*r(2) - q(4)*[1*r(1) - q(3)*r(2)], = -q(4)*r(1) + [1+q(3)*q(4)]*r(2), r(5) = 1*r(3) - q(5)*r(4), = 1*[1*r(1)-q(3)*r(2)] - q(5)*[-q(4)*r(1)+[1+q(3)*q(4)]*r(2)], = [1+q(4)*q(5)]*r(1) - [q(2)+q(4)+q(2)*q(3)*q(4)]*r(2), and so on. It turns out that these coefficients of r(1) and r(2) can be computed right along with the usual Euclidean Algorithm process as follows. Let a(1) = b(2) = 1, a(2) = b(1) = 0. Let the a(n)'s and b(n) be computed recursively from the equations a(n+2) = a(n) - q(n+2)*a(n+1), b(n+2) = b(n) - q(n+2)*b(n+1). Then for all n >= 1, you have r(n) = a(n)*r(1) + b(n)*r(2). Example: Start with the two numbers 114 = r(1) and 48 = r(2). 114 = 2*48 + 18, so q(3) = 2 and r(3) = 18. a(3) = a(1) - q(3)*a(2) = 1 - 2*0 = 1, b(3) = b(1) - q(3)*b(2) = 0 - 2*1 = -2. 48 = 2*18 + 12, so q(4) = 2 and r(4) = 12. a(4) = a(2) - q(4)*a(3) = 0 - 2*1 = -2, b(4) = b(2) - q(4)*b(3) = 1 - 2*(-2) = 5, 18 = 1*12 + 6, so q(5) = 1 and r(5) = 6. a(5) = a(3) - q(5)*a(4) = 1 - 1*(-2) = 3, b(5) = b(3) - q(5)*b(4) = -2 - 1*5 = -7, 12 = 2*6 + 0, so q(6) = 2 and r(6) = 0. a(6) = a(4) - q(6)*a(5) = -2 - 2*3 = -8, b(6) = b(4) - q(6)*b(5) = 5 - 2*(-7) = 19. Sure enough, 114 = (1)*114 + (0)*48, 48 = (0)*114 + (1)*48, 18 = (1)*114 + (-2)*48, 12 = (-2)*114 + (5)*48, 6 = (3)*114 + (-7)*48, 0 = (-8)*114 + (19)*48. You can keep track of the work like this n q(n) r(n) a(n) b(n) 1 114 1 0 2 48 0 1 3 2 18 1 -2 4 2 12 -2 5 5 1 6 3 -7 6 2 0 -8 19 Start by filling in the first two rows with r(1) = one of input numbers, r(2) = other input number, a(1) = b(2) = 1, a(2) = b(1) = 0. For each new row labeled n, compute q(n) = integer part of r(n-2)/r(n-1), r(n) = r(n-2) - q(n)*r(n-1), a(n) = a(n-2) - q(n)*a(n-1), and b(n) = b(n-2) - q(n)*b(n-1). Here's a larger example: n q(n) r(n) a(n) b(n) 1 9810 1 0 2 7047 0 1 3 1 2763 1 -1 4 2 1521 -2 3 5 1 1242 3 -4 6 1 279 -5 7 7 4 126 23 -32 8 2 27 -51 71 9 4 18 227 -316 10 1 9 -278 387 11 2 0 783 -1090 If you need further explanation, please write again. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/