WOLFRAM|DEMONSTRATIONS PROJECT

Recursive Extended Euclidean Algorithm

​
n
2
3
4
5
a
1
210
a
2
330
a
3
462
a
4
140
a
5
105
gcd(210,330) = 30
210
x
1
+330
x
2
= 30,where {
x
1
,
x
2
} = {-3,2}
0
{210,330}
0
{30,{-3,2}}
1
{330,210}
1
{30,{2,-3}}
2
{210,120}
1
{30,{-1,2}}
3
{120,90}
1
{30,{1,-1}}
4
{90,30}
3
{30,{0,1}}
The greatest common divisor of positive integers
a
1
,
a
2
, …,
a
n
is the largest integer
d
such that
d
divides each of the
n
integers. There always exist integers
x
1
,
x
2
, …,
x
n
such that
a
1
x
1
+…+
a
n
x
n
=d
.
Mathematica's built-in function ExtendedGCD returns
{d,{
x
1
,…,
x
n
}}
, given the arguments
a
1
,…,
a
n
. This Demonstration implements ExtendedGCD with a recursive extended Euclidean algorithm that computes a list of the results of the recursive steps.
The basic case is
n=2
. The algorithm, given
a
0
=
a
1
and
b
0
=
a
2
, returns the list (as a column):
{0,{
a
0
,
b
0
},
q
0
,{
d
0
,{
x
0
,
y
0
}}}
,
{1,{
a
1
,
b
1
},
q
1
,{
d
1
,{
x
1
,
y
1
}}}
,
…,
{k,{
q
k
d
k
,
d
k
},
q
k
,{
d
k
,{0,1}}}
.
These rows are
{i,{
a
i
,
b
i
},
q
i
,g(
a
i
,
b
i
)}
, where
i
is the depth of the recursion,
q
i
is the integer quotient of
a
i
and
b
i
, and
g
is recursively defined by
g(a,b)={b,{0,1}}
, if
amodb=0
, and if
r=amodb>0
,
g(a,b)={
d
1
,{
y
1
,
x
1
-q
y
1
}}
, where
{
d
1
,{
x
1
,
y
1
}}=g(b,r)
and
q=(a-r)/b
.
The recursion terminates because
b>r≥0
. If
r=0
,
a=qb
,
gcd(a,b)=b
, and
a0+b1=b=gcd(a,b)
. If
r>0
, assume
gcd(q,r)=
d
1
and
b
x
1
+r
y
1
=
d
1
. Then,
gcd(a,b)=gcd(b,r)=
d
1
, and
a
y
1
+b(
x
1
-q
y
1
)=b
x
1
+r
y
1
=
d
1
. By induction, whenever
a
and
b
are positive integers,
t(a,b)={d,{x,y}}
, where
gcd(a,b)=d
and
ax+by=d
.
Thus, in each row
i
,
i≥0
,
i
is the depth of recursion,
{
a
i
,
b
i
}
is the input and
{
d
i
,{
x
i
,
y
i
}}
is the output of
g
with
a
i
x
i
+
b
i
y
i
=
d
i
=gcd(
a
i
,
b
i
)
.
You can check this by studying numerical examples. Check it is true for the last row. Then check that if is true for a given row, then it is true for the previous row. It is therefore true for the first row.
When
n>2
, it is a little more difficult to prove, but you can still verify numerically that if
{i,{
a
1
,…,
a
n
},
q
i
,{
d
i
,{
x
1
,…,
x
n
}}}
and
{i+1,{
b
1
,…,
b
n
},
q
i+1
,{
d
i+1
,{
y
1
,…,
y
n
}}}
are successive rows and
b
1
y
1
+...+
b
n
y
n
=
d
i+1
=gcd(
b
1
,…,
b
n
)
, then
a
1
x
1
+…,
a
n
y
n
=
d
i
=gcd(
a
1
,…,
a
n
)
. Also, this is true for the last row.