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_{3}=floor(r_{2}/r_{3})=floor(47/31)=1
q_{k}=floor(r_{k-1}/r_{k})
Then follow the instructions in the table
We write the initial values of x and y as 1, 0, and 0, 1 and a=r_{1}
and b=r_{2}:
Table 2: gcd(a,b)
k
x_{k}
y_{k}
r_{k}
q_{k}
1
1
0
a (r_{1})
2
0
1
b (r_{2})
q_{2}
3
1
q_{2}
r_{3}
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_{1},r_{2})=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}=1, and r_{1}=a,
by our initial assumptions
[1.6]
because y_{1}=1, and b=r_{2}
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:
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: