Extended Euclidean Algorithm

a, b

gcd(987,610)1

987	=	610	×	1	+	377
610	=	377	×	1	+	233
377	=	233	×	1	+	144
233	=	144	×	1	+	89
144	=	89	×	1	+	55
89	=	55	×	1	+	34
55	=	34	×	1	+	21
34	=	21	×	1	+	13
21	=	13	×	1	+	8
13	=	8	×	1	+	5
8	=	5	×	1	+	3
5	=	3	×	1	+	2
3	=	2	×	1	+	1
2	=	1	×	2	+	0

⇒

1

=

987

×

233

+

610

×

(-377)

987	=	987	×	1	+	610	×	0
610	=	987	×	0	+	610	×	1
377	=	987	×	1	+	610	×	(-1)
233	=	987	×	(-1)	+	610	×	2
144	=	987	×	2	+	610	×	(-3)
89	=	987	×	(-3)	+	610	×	5
55	=	987	×	5	+	610	×	(-8)
34	=	987	×	(-8)	+	610	×	13
21	=	987	×	13	+	610	×	(-21)
13	=	987	×	(-21)	+	610	×	34
8	=	987	×	34	+	610	×	(-55)
5	=	987	×	(-55)	+	610	×	89
3	=	987	×	89	+	610	×	(-144)
2	=	987	×	(-144)	+	610	×	233
1	=	987	×	233	+	610	×	(-377)

The greatest common divisor of two integers

a

and

b

can be found by the Euclidean algorithm by successive repeated application of the division algorithm. The extended Euclidean algorithm not only computes

gcd(a,b)

but also returns the numbers

s

and

t

such that

gcd(a,b)=as+bt

. The remainder

r

i

of the

th

i

step in the Euclidean algorithm can be expressed in the form

r

i

=a

s

i

+b

t

i

, where

s

i

and

t

i

can be determined from the corresponding quotient

q

i

and the values

s

i-1

,

s

i-2

, or

t

i-1

,

t

i-2

two rows above them using the relations

s

i

=

s

i-2

-

q

i

s

i-1

and

t

i

=

t

i-2

-

q

i

t

i-1

, respectively. This forward method requires no back substitutions and reduces the amount of computation involved in finding the coefficients

s

and

t

of the linear combination.