nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Euclid's Extended Algorithm

Number Theory Contents
Like most theorems in mathematics, Euclid's Extended Algorithm is important, not only for its conclusion, but also for what we can learn about computation from the way it works, and the short-cuts it reveals. Like Euclid's Algorithm, it is very important in Number Theory and other subjects.

The theorem tells us that if a and b are relatively prime, then we can find numbers, x and y, such that:
ax+by=1

As a consequence of this, if a and b are not relatively prime and have a greatest common divisor d, then we can find numbers, x and y such that:
ax+by=d

Page Contents

  1. Arithmetic Examples
    1. Example 1
  2. Proof
  3. Relationship Between the Coefficients
    1. Arithmetic Example
  4. Determining the Coefficients in the Extended Algorithm prior to term n-2
  5. Proving the Rules
    1. Arithmetic Demonstration of the Rules
    2. The solution is not unique




Arithmetic Examples

Example 1

Suppose we have two numbers, 57 and 46, we seek two numbers x, and y such that:
57x+46y=d (where d is the greatest common divisor of 57 and 46).
First we seek the gcd, using Euclid's Algorithm.

Table 1: gcd(57,46)
k rk rk+1 qk rk+2  
1 57= 46· 1+ 11  
2 46= 11· 4+ 2  
3 11= 2· 5+ 1 We now have the gcd, which is 1, because 57 and 46 are relatively prime. We now have our d=1
Next, we figure out the x and y values.

Considering the equation when k=3, and we already have a "1". We can arrange the equation:
11=2·5+1, so:
1=11−2·5                 [1.1]

Progressively we can substitute the remainders, beginning with 2. When k=2, we have:
46=11·4+2, so:
2=46−11·4. Substituting this value for 2 in 1.1:
1=11−5·(46−11·4)
1=11·21−5·46         [1.2]

When k=1, we have:
57=46·1+11, which gives:
11=57−46·1, and substituting for 11 in Equation 1.2:
1=(57−46·1)·21−5·46
1=57·21−26·46, which is our equation          [1.3]

Presenting the results in a table, we have:
Table 2: Solve 57x+46y=1
krkrk+1xkykqk
31121-55
24611-5214
1574621261


We have therefore found that x=21 and y=26, so:
57·21-26·46=1
■

Proof

This is really a formalisation of our example. We will prove that if gcd(a,b)=d, then there exist numbers x and y such that:
ax+by=d. Assuming both a, b ≠0, and a>b.

Our argument is that we can express the gcd as a linear combination of the kind:
rn-2-qn-2·rn-1=rn
where rn=d, n is the number of steps required in Euclid's Algorithm to find the gcd. By Euclid's Algorithm, we know that n is finite and the algorithm always gives us the gcd. So working backwards from this linear combination, substituting for the r's until we have r1=a and r2=b, and we have the sought for linear combination.

First we will use Euclid's Algorithm to find gcd.

a=b·q1+r1
b=r1·q2+r2
....
rn-k+1=qn-k+1·rn-k+2+rn-k+3
rn-k=qn-k·rn-k+1+rn-k+2
...
rn-5=qn-5·rn-4+rn-3     [n-5]
rn-4=qn-4·rn-3+rn-2     [n-4]
rn-3=qn-3·rn-2+rn-1         [n-3]
rn-2=qn-2·rn-1+rn       [n-2]

Assuming that rn is equal to d, so we can express [n-2] as:
d=rn-2 − rn-1·qn-2   [2.1]

As in the arithmetic example, we can substitute rn-1 from Equation n-1 into 2.1:
d=rn-2 − (rn-3−qn-3·rn-2)·qn-2   which gives:

d=rn-2·(1+qn-3·qn-2) − rn-3·qn-2 which is an expression of the r's in as a linear combination, equal to d. We will write this equation as follows to maintain consistency:
 d= −rn-3·qn-2+rn-2·(1+qn-3·qn-2)  [2.2],
which shows the r's in the order rn-k, rn-k+1, of a, b)

Naturally, we can continue... We can substitute in Equation 2.2, the value of rn-2 from Equation n-4:
d= −rn-3·qn-2+(rn-4−qn-4·rn-3)·(1+qn-3·qn-2), and by collecting like terms, showing the linear combination of the r's:
d= −rn-3·(qn-2+qn-4·(1+qn-3·qn-2))+rn-4·(1+qn-3·qn-2), and bringing the r's into the order a, b:
d= rn-4·(1+qn-3·qn-2)−rn-3·(qn-2+qn-4·(1+qn-3·qn-2))   [2.3]

Substituting the value for rn-3 from [n-5] in Equation 2.3, we get:
d= rn-4·(1+qn-3·qn-2)−(rn-5−qn-5·rn-4)·(qn-2+qn-4·(1+qn-3·qn-2)), and again collecting the r's together:
d= rn-4·(1+qn-3·qn-2+qn-5·[qn-2+qn-4·(1+qn-3·qn-2)])−rn-5·(qn-2+qn-4·(1+qn-3·qn-2)), and we need to begin with rn-5 because n-5<n-4, and this preserves our order:
d= −rn-5·(qn-2+qn-4·(1+qn-3·qn-2))+rn-4·(1+qn-3·qn-2+qn-5·[qn-2+qn-4·(1+qn-3·qn-2)])

Eventually, we will obtain an expression involving a linear combination of a and b. "Eventually", because we know that we will reach this point, because Euclid's Algorithm begins with a and b and reaches at zero in a finite number of steps, which we have proved under Euclid's Algorithm.
Therefore, we can continue as far as r1 and r2, which are a and b, expressed as a linear combination of the form:
ax+by=d
■

Relationship Between the Coefficients

Arithmetic Example

We first use Euclid's Algorithm to compute gcd(57,46)
Table 3: gcd(57,46)
k rk rk+1 qk rk+2  
1 57= 46· 1+ 11  
2 46= 11· 4+ 2  
3 11= 2· 5+ 1 We now have the gcd, which is 1, because 57 and 46 are relatively prime. We now have our d=1
42=1·2+0
51=0·0+1

We can use the above to compute x and y such that:
57x+46y=1
From the above table 3, we can fill in the first 3 rows and the sixth row (qk) of Table 4 (There is a great deal of redundancy in this information, and normally we wouldn't write these columns. They are written only to enable the calculation of rk·xk+rk+1·yk which is 1 in each case).
We start at k=5, in the above table and fill in Table 4 below, as we did before.

Table 4: Solve 57x+46y=1
krkrk+1xkykqk
51010-
421012
31121-55
24611-5214
1574621-261

The significant parts of the table for this section are the last three columns, xk, yk, and qk.

Clearly, we see that xk=yk-1. Also, all the information in xk is contained in yk. That is, except for the first and last numbers.

Also, the table begins with x, and y values 1, 0 and the next row is 0, 1.

What isn't obvious, but what we will later prove is:
xk=xk-2-qk-1·xk-1, and
yk=yk-2-yk-1·qk

That is, in computing the x's and y's, we need only to go back two terms. And we can compute the extended algorithm using the q's from the computation of the gcd

Determining the Coefficients in the Extended Algorithm prior to term n-2

In the previous example, we noted that the first coefficients in the extended algorithm were 1, 0 and on the next row, 0, 1. The question is, is this fortuitous or is it true in general.
The following are some continued terms of Euclid's algorithm, with rn=d=gcd, where this is the (n-2) term from the beginning.
extended_1.gif

We note that rn=d, the gcd(r1,r2).
In term [n-1], rn+1=0, because it is the remainder after the gcd. (Because d divides all remainders, then the remainder when divided into rn-1 is zero).

Because rn+1 is zero, then rn+2=rn=d.

We begin the extended algorithm:
extended_2.gif  [3.1]
Because the coefficient of rn is 1, and qn=0 (because there are zero rn+1), we have our starting values 1, 0.

Substituting rn+1 from [n-1]
extended_3.gif
which tells us that:
extended_6.gif
Also that:
extended_7.gif

Rearranging:
extended_8.gif [3.2]
which gives us our second row, with coefficients 0, 1

Proving the Rules

The following table illustrates the Extended Euclidean algorithm using algebra:

Table 5: Algebraic Illustration
k xk yk
n10
n-101
n-2 1 -qn-2
n-3 -qn-2 1+qn-3·qn-2
n-4 1+qn-3·qn-2 -(qn-2+qn-4·(1+qn-3·qn-2) )
n-5 -(qn-2+qn-4·(1+qn-3·qn-2) ) 1+qn-3·qn-2+qn-5·[qn-2+qn-4·(1+qn-3·qn-2)]
The above table is present only to demonstrate the algebra, and does not take part in the proof.

We prove the rules in the following way:
Imagine that the following is the kth term of Euclid's Extended Algorithm:
rules_1.gif [4.1]
where d is gcd(r1,r2) and xk and yk are kth values in our calculation of x1 and y1;  n-2 ≤ k ≤ 1; and d is the gcd, rn. Naturally, all the numbers are integers.

The next stage in the algorithm is to substitute:
rules_2.gif(from Euclid's Algorithm) [4.2]
in 4.1:
rules_3.gif [4.3]
which is the k-1 th term of the algorithm.

Therefore:
rules_4.gif [4.4]
which tells us that an x value is equal to the previous y value, as we saw in the table.

Also,
rules_5.gif [4.5]
By using 4.4, we can express the y's in terms of other y's (and the q!)
rules_6.gif
or
rules_8.gif  [4.6]
That is, the new y value equals the y value 2 rows up less the current q times the previous y.

Similarly, we can express the x's in terms of the x's (and the q):
rules_7.gif [4.7]
That is the new x value equals the x value two rows down less the previous x value times the previous q value.
■

Arithmetic Demonstration of the Rules

The table below is a previous table, computed using the rules this time, that is:
rules_8.gif 
rules_7.gif 
Table 6: Solve 57x+46y=1 (Using the rules)
kxkykqk
510-
4012
31-55x3=1−5·0=1
y3=0−5·1=-5
2-5214x2=1−5·1=-5
y2=1−4·(-5)=21
121-261x1=1−(-5)·4=21
y1=(−5)·1−21=−26

Therefore a solution to
57x+46y=1, is:
57(21)+46(-26)=1

The solution is not unique

One solution to 57x+46y=1 is:
57(21)+46(-26)=1

Other solutions are:
57(67)+46(-83)=1
57(113)+46(-140)=1

There are, in fact, an infinite number of such solutions. So the solution given above is not unique.
■





Ken Ward's Mathematics Pages