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 shortcuts 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
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
r_{k}
r_{k+1}
q_{k}
r_{k+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
k
r_{k}
r_{k+1}
x_{k}
y_{k}
q_{k}
3
11
2
1
5
5
2
46
11
5
21
4
1
57
46
21
26
1
We have therefore found that x=21 and y=26, so: 57·2126·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:
r_{n2}q_{n2·}r_{n1}=r_{n} where r_{n}=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·q_{1}+r_{1}
b=r_{1}·q2+r_{2}
....
r_{nk+1}=q_{nk+1}·r_{nk+2}+r_{nk+3}
r_{nk}=q_{nk}·r_{nk+1}+r_{nk+2}
...
r_{n5}=q_{n5·}r_{n4}+r_{n3}
[n5]
r_{n4}=q_{n4·}r_{n3}+r_{n2}
[n4]
r_{n3}=q_{n3·}r_{n2}+r_{n1
}[n3]
r_{n2}=q_{n2·}r_{n1}+r_{n}
[n2]_{
}
Assuming that r_{n} is equal to d, so we can
express [n2] as:
d=r_{n2 }− r_{n1}·q_{n2}
[2.1]
As in the arithmetic example, we can substitute r_{n1}
from Equation n1 into 2.1:
d=r_{n2 }− (r_{n3}−q_{n3·}r_{n2})·q_{n2}
which gives:
d=r_{n2}·(1+q_{n3}·q_{n2})_{
}− r_{n3·}q_{n2}
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= −r_{n3·}q_{n2}+r_{n2}·(1+q_{n3}·q_{n2})
[2.2],
which shows the r's in the order r_{nk}, r_{nk+1},
of a, b)
Naturally, we can continue... We can substitute in Equation 2.2, the
value of r_{n2} from Equation n4:
d= −r_{n3·}q_{n2}+(r_{n4}−q_{n4·}r_{n3})·(1+q_{n3}·q_{n2}),
and by collecting like terms, showing the linear combination of the r's:
d= −r_{n3·(}q_{n2}+q_{n4}·(1+q_{n3}·q_{n2}))+r_{n4}·(1+q_{n3}·q_{n2}),
and bringing the r's into the order a, b:
d= r_{n4}·(1+q_{n3}·q_{n2})−r_{n3·(}q_{n2}+q_{n4}·(1+q_{n3}·q_{n2}))
[2.3]
Substituting the value for r_{n3} from [n5] in
Equation 2.3, we get:
d= r_{n4}·(1+q_{n3}·q_{n2})−(r_{n5}−q_{n5·}r_{n4})_{·(}q_{n2}+q_{n4}·(1+q_{n3}·q_{n2})),
and again collecting the r's together:
d= r_{n4}·(1+q_{n3}·q_{n2}+q_{n5}·[q_{n2}+q_{n4}·(1+q_{n3}·q_{n2})])−r_{n5}·(q_{n2}+q_{n4}·(1+q_{n3}·q_{n2})), and we need to begin with r_{n5} because n5<n4, and this preserves our order:
d= −r_{n5}·(q_{n2}+q_{n4}·(1+q_{n3}·q_{n2}))+r_{n4}·(1+q_{n3}·q_{n2}+q_{n5}·[q_{n2}+q_{n4}·(1+q_{n3}·q_{n2})])
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 r_{1} and r_{2}, which are a and b, expressed as a linear combination of the form: ax+by=d ■
We now have the gcd, which is 1, because 57 and 46 are
relatively prime. We now have our d=1
4
2=
1·
2+
0
5
1=
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 (q_{k})
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 r_{k}·x_{k}+r_{k+1}·y_{k} 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
k
r_{k}
r_{k+1}
x_{k}
y_{k}
q_{k}
5
1
0
1
0

4
2
1
0
1
2
3
11
2
1
5
5
2
46
11
5
21
4
1
57
46
21
26
1
The significant parts of the table for this section are the last three columns, x_{k}, y_{k}, and q_{k}.
Clearly, we see that x_{k}=y_{k1}. Also, all the information in x_{k} is contained in y_{k}. 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: x_{k}=x_{k2}q_{k1}·x_{k1}, and y_{k}=y_{k2}y_{k1}·q_{k}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 n2
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 r_{n}=d=gcd, where this is the (n2) term from the beginning.
We note that r_{n}=d, the gcd(r_{1},r_{2}). In term [n1], r_{n+1}=0, because it is the remainder after the gcd. (Because d divides all remainders, then the remainder when divided into r_{n1} is zero).
Because r_{n+1} is zero, then r_{n+2}=r_{n}=d.
We begin the extended algorithm: [3.1] Because the coefficient of r_{n} is 1, and q_{n}=0 (because there are zero r_{n+1}), we have our starting values 1, 0.
Substituting r_{n+1} from [n1]
which tells us that:
Also that:
Rearranging: [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:
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:
[4.1] where d is gcd(r_{1},r_{2}) and x_{k} and y_{k} are kth values in our calculation of x_{1} and y_{1}; n2 ≤ k ≤ 1; and d is the gcd, r_{n}. Naturally, all the numbers are integers.
The next stage in the algorithm is to substitute: (from Euclid's Algorithm) [4.2] in 4.1: [4.3] which is the k1 th term of the algorithm.
Therefore: [4.4] which tells us that an x value is equal to the previous y value, as we saw in the table.
Also, [4.5] By using 4.4, we can express the y's in terms of other y's (and the q!)
or [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): [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:
Table 6: Solve 57x+46y=1 (Using the rules)
k
x_{k}
y_{k}
q_{k}
5
1
0

4
0
1
2
3
1
5
5
x_{3}=1−5·0=1 y_{3}=0−5·1=5
2
5
21
4
x_{2}=1−5·1=5 y_{2}=1−4·(5)=21
1
21
26
1
x_{1}=1−(5)·4=21 y_{1}=(−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'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: