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:

• Number Theory Contents
• Euclid's Algorithm
• Euclid's Extended Algorithm

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 r_k, begin with 47 and 31, and then write down the remainders on division: 16, 15, 1...
r_k=remainder(r_k-2/r_k-1)
Under q_k, write the whole-number divisions, that is:
q₃=floor(r₂/r₃)=floor(47/31)=1
q_k=floor(r_k-1/r_k)
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=r₁ and b=r₂:

	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 gcd is a (or b, as they are the same).

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

And in general that if:
[1.2]
And
[1.3]
Then:
[1.4]

We know the following is true, because of Euclid's algorithm:
[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:
[1.6]
[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 r_n-2=d, if:
[1.2]
And
[1.3]
Then:
[1.4]

For k=1, we have:
[1.5]
which is true because x₁=1, and r₁=a, by our initial assumptions

[1.6]
because y₁=1, and b=r₂

So, by Euclid's Algorithm:
[1.7]

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

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

Rearranging 1.7, we have:
[1.10]

By assumption (Equations 1.2, and 1.3):
[1.11]
By Euclid:


Therefore, by mathematical induction if:
[1.2, repeated]
And
[1.3, repeated]
Then:
[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