Scribd
Upload
265 views

The Extended Euclidean Algorithm

1) The Extended Euclidean Algorithm uses matrices to find the greatest common divisor (gcd) of two integers m and n by finding integers x and y such that mx + ny = gcd(m,n). 2) It starts with an initial matrix and computes subsequent matrices using a recursion rule, reducing the second entry of each matrix until it reaches 0. 3) This provides the values of x and y such that the gcd is achieved.

Uploaded by

chrislucas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
265 views

The Extended Euclidean Algorithm

1) The Extended Euclidean Algorithm uses matrices to find the greatest common divisor (gcd) of two integers m and n by finding integers x and y such that mx + ny = gcd(m,n). 2) It starts with an initial matrix and computes subsequent matrices using a recursion rule, reducing the second entry of each matrix until it reaches 0. 3) This provides the values of x and y such that the gcd is achieved.

Uploaded by

chrislucas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

The Extended Euclidean Algorithm

(Matrix Method)
Aim: Given integers m, n, find x, y Z such that
mx + ny = gcd(m, n).
Idea: Find successively xi, yi such that we have
mxi + nyi = ri,
where ri = rem(ri2, ri1) (and r1 = m, r0 = n).
 
1 0 m
Algorithm: 1) Start with the matrix A0 = .
0 1 n
2) Compute the matrices A1, . . . , Ak+1 successively
by using the recursion rule
 
Ri2
Ai+1 = ;
Ri1 qi+1Ri2
here qi+1 = quo(ri1, ri) and
   
Ri1 xi1 yi1 ri1
Ai = = .
Ri2 x i y i ri
3) Stop when ri = 0. (Thus, rk+1 = 0.)
Conclusion: mxk + nyk = rk = gcd(m, n).
Example: m = 1239, n = 735.
Here q1 = 1, q2 = 1, q3 = 2, q4 = 5, q5 = 2. Thus
! !
1 0 1239 R01R02 0 1 735
A0 = = A1
0 1 735 1 1 504
!
R11R12 1 1 504
= A2
1 2 231
!
R212R22 1 2 231
= A3
3 5 42
!
R315R32 3 5 42
= A4
16 27 21
!
R412R42 16 27 21
= A5
35 59 0

Conclusion: 1239(16) + 735(27) = 21.


Note: If we view each matrix Ai as an augmented ma-
trix, then it is clear that (m, n) = (1239, 735) is the
solution of the associated system of linear equations.

You might also like