[This document assumes that at least the early part of
eucnotes.html has been read. The jargon, introduced
there, is used within. In particular, the basic Euclidean algorithm (see
the pseudo code of 'Algorithm E') and problems with integer division (both in 'eucnotes') need
to be understood.
[All References below are in file refs.html.]]
Euclid's algorithm finds the greatest common divisor
(GCD) of 2 integers - call them 'A' and 'B'.
FIRST OBSERVATION :-
In the modern set of integers, in which negative integers
exist, if D evenly divides both A and B, -D will also divide both A and
B. However since positive-D is greater than negative-D, and the greatest
divisor is being sought, the negative value can be ignored. (Similar comments
apply to 'A' and 'B' - if either (or both) are negative, their absolute
values can be substituted.) Thus all variables in Euclid's algorithm can
be mapped to members of the Positives without loss of generality.
[Note that this rules out the possibility of either 'A' or 'B' being zero. If either A or B might be 'zero' on entry to your software, then an early test followed by the application of statement GCD(0, n) = n will be needed to prevent a 'division by zero' error occurring.]
[In Euclid's time, mainstream Greek mathematics did not accept the existence of negative integers, or zero.]
SECOND OBSERVATION :-
The GCD can be no larger than the lesser of 'A' and 'B'
= min(A, B).
Thus the GCD must be a member of
set {1, 2, ... min(A, B)}
Call this set the 'Candidate' set.
[The number of elements in a set is called the 'order' of the set by mathematicians. Clearly, the order of the Candidate set is initially min(A, B).]
The algorithm works by iteratively eliminating some of the largest members of the Candidate set, reducing the order of the set. It will be shown below, that the largest member of the Candidate set, might be the GCD. Hence, after a reduction of the set order, the new largest member is tested. If it is the GCD (step E1 of Algorithm E), the algorithm terminates; if it isn't, another iteration is carried out.
The following logic is the basis for each iteration step :-
Suppose D = GCD(A, B)
(D (or d) will be the GCD sought, from here down)
Then we must have :-
D can be no larger than min(A, B)
= the maximum element of the Candidate set.
This comes about because no larger value
than min(A, B) can evenly divide both.
[See comments on division in eucnotes.html]
[From here down I assume that neither 'A nor 'B' is zero at the start.
Also, I assume 'A' is less than or equal to 'B'.]
[Step E1 of Algorithm 'E' :- ]
Test whether A evenly divides B; if so, we are done - the GCD is A.
If not, an operation needs to be found, which step by step moves the
calculation closer to the GCD, while simultaneously ensuring D remains
a factor of the maximum Candidate element.
A suitable operation is :-
If 'D' is the GCD sought, we have :-
A = A'.D and B = B'.D.
where, since D is the greatest common divisor of A and B, by definition A' and B' can contain no common divisor, other than '1',
Hence we must have GCD(A', B') = 1.
If we subtract A from B we get :-
C, say, = B - A = B'.D - A'.D = (B' - A').D.
Clearly, C is simultaneously less than B and also evenly divisible by D, just as B was.
THIRD OBSERVATION (a) :-
If we subtract A from B the GCD(A, B) value sought remains a factor of the
difference.
[The logic above proves that D must divide (B-A) and, by
extension, any subsequent sequence of differences. However, it does not
prove that the GCD of any pair of differences is not a multiple of D. Below,
I shall prove that the GCD of such differences does not
'grow' to 2.D or 3.D ...]
Hence, we can replace B by C, confident that the GCD(A, C) = GCD(A, B), and if the GCD calculation is continued with {A, C} in place of {A, B} the result will be unchanged.
Having reduced the B value once, we can do it again and again ...
until such time as 1 <= B < A; call this value B2.
[Note that B2 will never equal '0' since we checked at the start that A did not evenly divide B.]
[A moments thought tells us that we could write
B2 = B mod A.
This is so, because precisely Floor() subtractions will have taken place leaving the remainder in B2.]
[Note that Euclid, himself used repeated subtractions,
rather than the Floor() division operation.
In logic, repeated subtraction gives precisely the same result
as taking the remainder after a Floor() division; but there is a difference
in software speed.]
If we replace B by B2, then from observation 2, the Candidate set will have been reduced to a set of lower order :-
Reduced Candidate set = {1, 2, ... (B2-1), B2}.
where B2 < A with D evenly dividing B2.
In words, repeatedly subtracting the smaller value (A) from the larger (B) simultaneously leaves the GCD unchanged and (at the last step) reduces the order of the Candidate set, and leaves the new maximum element divisible by D. Consequently, some progress has been made towards closing in on D.
[Step E2 of Algorithm E :-]
We can now replace B by B2, and (to keep the 1st entry in the GCD(,) expression the lesser value) swap A and B2 around - since B2 is now less than A.
If B2 evenly divides A, then the GCD is B2,
and we are done.
If not, we can start subtracting B2 from A
i.e. repeat the process above.
At the end of each stage the order of the Candidate set will have been reduced further as the An and Bn values are reduced in turn. Eventually the "if An evenly divides Bn" condition, above, will be TRUE and the calculation will be completed.
[This will always be true because the A and B values that we started out with, are reduced stage-by-stage; a process that, in the absence of even division occurring earlier, must end with one or other as '1'. (the smallest value in the Candidate set - i.e. the order of the Candidate set is reduced to '1'). When this happens, even division must follow, since all integers are evenly divisible by '1'. Hence the algorithm ALWAYS terminates.]
[The discussion next on the algorithm's accuracy comes from Ref 12]
Let the output from Algorithm E be 'd'.
(Comments below are not incorrect when d=1; but make little sense.
Hence I shall assume d is not equal to 1).
Above I mentioned that using only Third Observation (a) in isolation, all
that can be said, for certain about 'd' is :-
d is a member of set {1.D, 2.D, 3.D ...}
This is, of course, not satisfactory. In order to prove
that 'd' = 'D', we can reverse the subtraction process above as follows :-
THIRD OBSERVATION (b) :-
If 2 integers with a GCD of 'd' are added, their sum is evenly divisible
by 'd'.
(Similar logic to Third observation (a))
If now we use Third observation (b) to move backwards through the iterations of algorithm E, we find that 'd' must evenly divide all the intermediate values and, eventually,
evenly divide the input values as well.
Hence 'd' evenly divides 'D'.
(Recall that GCD(A', B') = 1 was derived above,
hence (when d is not equal to 1)
'd' cannot simultaneously evenly divide A' and B'
so 'd' must divide 'D')
Thus we have :-
'D' evenly divides 'd'
simultaneously with 'd' evenly dividing 'D'.
This is only possible if 'd' = 'D'.