nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Euclid's Algorithm and Euclid's Extended Algorithm

It is possible to compute the gcd of a number, and find x and y such that ax+by=d, without backtracking. See also:

Page Contents

  1. Computing Both the gcd and Solving ax+by=d, all in one
  2. Proof
  3. Application to Indeterminate Equations

Computing Both the gcd and Solving ax+by=d

We wish to compute the gcd(47,31) and also find an equation where:
47x+31y=gcd(47,31) The following table illustrates the method:

First fill in the first 4 cells for the y's: 1 ,0 and 0, 1
Under rk, begin with 47 and 31, and then write down the remainders on division: 16, 15, 1...
rk=remainder(rk-2/rk-1)
Under qk, write the whole-number divisions, that is:
q3=floor(r2/r3)=floor(47/31)=1
qk=floor(rk-1/rk)
Then follow the instructions in the table

Table 1: gcd(47,31)
k xk yk rk qk  
1 1 0 47  
2 0 1 31 1   q2=floor(45/31)=1
3 1 -1 16 1 r3=remainder(47/31)
q3=floor(31/16)=1
x3=x1-x2·q2=1
y3=y1-y2·q2=−1
4 -1 2 15 1 r4=remainder(31/16)
q4=floor(16/15)=1
x4=x2-x3·q3=−1
y4=y2-y3·q3=2
5 2 -3 1 15 r5=remainder(16/15)
q5=floor(15/1)=15
x5=x3-x4·q4=2
y5=y3-y4·q4=−3

Therefore, the gcd(47,31)=1, and using x and y values for this line (line 5), we find that x=2 and y-3 are one solution to:
47x+31y=1.

Proof

We simply apply Euclid's algorithm.

We write the initial values of x and y as 1, 0, and 0, 1 and a=r1 and b=r2:
Table 2: gcd(a,b)
k xk yk rk qk
1 1 0 a (r1)
2 0 1 b (r2) q2
3 1 q2 r3  

Assumptions

a and b are two numbers where a≥b, and both a and b are not zero. If a and b are both zero, then the gcd and ax+by=d are indeterminate. If a or b is zero, then the gcd is the non-zero number, and ax+by=d has a trivial solution. If a=b, the the gcd is a (or b, as they are the same).

k is a number 1≤k≤n-2, when n is such that rn-2=d, and consequently, rn-1=0
We need to prove that the sequence of r's reaches zero just after rk=d (gcd(r1,r2)=gcd(a,b) )

And in general that if:
ext_2.gif [1.2]
And
ext_11.gif [1.3]
Then:
ext_12.gif [1.4]

We know the following is true, because of Euclid's algorithm:
ext_3 [1.5]

Similarly, the following are true because they are effectively the same as 1.3; that is, they are the application of the algorithm to two variables, which add up to the r's in 1.3:
ext_4.gif# [1.6]
ext_4.gif [1.7]

The Proof

The sequence of r's is eventually (in a finite number of steps) equal to zero just after it is equal to d, the gcd(a,b). This has been proved in Euclid's Algorith. That is, in our example, we have 47, 31, 16, 15, 1, 0.

We argue that for k=1, k≤n-2, where rn-2=d, if:
ext_2.gif [1.2]
And
ext_11.gif [1.3]
Then:
ext_12.gif [1.4]

For k=1, we have:
ext_13.gif [1.5]
which is true because x1=1, and r1=a, by our initial assumptions

ext_14.gif [1.6]
because y1=1, and b=r2

So, by Euclid's Algorithm:
ext_15.gif [1.7]

Therefore, our formula works for k=1
Assuming that:
ext_2.gif [1.2, repeated]
And
ext_11.gif [1.3, repeated]
Then using Equations 1.6 and 1.7 (Euclid applied to the parts)
ext_16.gif [1.7]

Because:
ext_17.gif [1.8]
ext_18.gif [1.9]
Then Equation 1.7 is true.

Rearranging 1.7, we have:
ext_19.gif [1.10]

By assumption (Equations 1.2, and 1.3):
ext_20.gif [1.11]
By Euclid:
ext_12.gif

Therefore, by mathematical induction if:
ext_2.gif [1.2, repeated]
And
ext_11.gif [1.3, repeated]
Then:
ext_12.gif [1.4, repeated]

Application to Indeterminate Equations

Suppose we wish to solve
7x+17y=1
for x and y.
Using Euclid's Extended algorithm:

  Solve 7x+17y=1  
k xk yk rk qk  
1 1 0 7  
2 0 1 17 0   q2=floor(7/17)=0
3 1 0 7 2 r3=remainder(7/17)=7
q3=floor(17/7)=2
x3=x1-x2·q2=1
y3=y1-y2·q2=0
4 -2 1 3 2 r4=remainder(17/7)=3
q4=floor(7/3)=2
x4=x2-x3·q3=−2
y4=y2-y3·q3=1
5 5 -2 1 3 r5=remainder(7/3)=1
q5=floor(3/1)=3
x5=x3-x4·q4=5
y5=y3-y4·q4=-2

At the 4th step, we find x=5 and y=-2, when the remainder is 1. That is, these are one solution to 7x+17y=1 (there are an infinite number of them!)

We deal with indeterminate equations using Euclid and congruences later.







Ken Ward's Mathematics Pages


Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com
Faster Arithmetic for Adults