Recursive Extended Euclidean Algorithm
Recursive Extended Euclidean Algorithm
The greatest common divisor of positive integers , , …, is the largest integer such that divides each of the integers. There always exist integers , , …, such that +…+=d.
a
1
a
2
a
n
d
d
n
x
1
x
2
x
n
a
1
x
1
a
n
x
n
Mathematica's built-in function ExtendedGCD returns , given the arguments ,…,. This Demonstration implements ExtendedGCD with a recursive extended Euclidean algorithm that computes a list of the results of the recursive steps.
{d,{,…,}}
x
1
x
n
a
1
a
n
The basic case is . The algorithm, given = and =, returns the list (as a column):
n=2
a
0
a
1
b
0
a
2
{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,{,},,{,{0,1}}}
q
k
d
k
d
k
q
k
d
k
These rows are , where is the depth of the recursion, is the integer quotient of and , and is recursively defined by , if , and if , , where and .
{i,{,},,g(,)}
a
i
b
i
q
i
a
i
b
i
i
q
i
a
i
b
i
g
g(a,b)={b,{0,1}}
amodb=0
r=amodb>0
g(a,b)={,{,-q}}
d
1
y
1
x
1
y
1
{,{,}}=g(b,r)
d
1
x
1
y
1
q=(a-r)/b
The recursion terminates because . If , , , and . If , assume and . Then, , and . By induction, whenever and are positive integers, , where and .
b>r≥0
r=0
a=qb
gcd(a,b)=b
a0+b1=b=gcd(a,b)
r>0
gcd(q,r)=
d
1
b+r=
x
1
y
1
d
1
gcd(a,b)=gcd(b,r)=
d
1
a+b(-q)=b+r=
y
1
x
1
y
1
x
1
y
1
d
1
a
b
t(a,b)={d,{x,y}}
gcd(a,b)=d
ax+by=d
Thus, in each row , , is the depth of recursion, is the input and is the output of with +==gcd(,).
i
i≥0
i
{,}
a
i
b
i
{,{,}}
d
i
x
i
y
i
g
a
i
x
i
b
i
y
i
d
i
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 , it is a little more difficult to prove, but you can still verify numerically that if and are successive rows and +...+==gcd(,…,), then +…,==gcd(,…,). Also, this is true for the last row.
n>2
{i,{,…,},,{,{,…,}}}
a
1
a
n
q
i
d
i
x
1
x
n
{i+1,{,…,},,{,{,…,}}}
b
1
b
n
q
i+1
d
i+1
y
1
y
n
b
1
y
1
b
n
y
n
d
i+1
b
1
b
n
a
1
x
1
a
n
y
n
d
i
a
1
a
n