Section 2.3 The Euclidean Algorithm
The Euclidean algorithm says that to find the gcd ofExample 2.3.1.
Let
So
Historical remark 2.3.2. Euclid's Elements.
Euclid, a mathematician in Alexandria during the Hellenistic era, appears to have written the Elements as a compendium of rigorous mathematical knowledge. In addition to being the main geometry textbook in the Western and Islamic worlds for two millennia (as late a teacher as Charles Dodgson a.k.a. Lewis Carroll extolled its virtues in print in Euclid and His Modern Rivals), there are substantial number-theoretic portions as well. No one really knows how much of the Elements is original to Euclid, but the work as a whole is monumental and well-organized, despite some well-known criticisms (see e.g. the discussion in [E.5.5]).
xxxxxxxxxx
gcd(2013,1066)
Algorithm 2.3.3. Euclidean algorithm.
To get the greatest common divisor of
Then the previous remainder,
Proof.
First let's see why this algorithm even terminates. The division algorithm says each \(r_i\) is less than the previous one, yet they may not be less than zero. So let's apply the Well-Ordering Principle to the set of remainders. This set must have a least positive element, and will be the answer. Another way to think about it is that since \(b\) is finite, there won't be an infinite number of steps.
Of course, that just gives a number, with no guarantee it has any connection to the gcd. So consider the set of common divisors \(d\mid a\) and \(d\mid b\text{.}\) All such \(d\) also divide
So these \(d\) also divide \(r_2=b-q_2r_1\text{,}\) and indeed divide all the remainders, even \(r_{n-1}=r_{n-3}-q_{n-1}r_{n-2}\text{.}\) So all common divisors of \(a\) and \(b\) are divisors of \(r_{n-1}\text{.}\)
On the other hand, if \(d\) divides \(r_{n-1}\text{,}\) it divides \(r_{n-2}=r_{n-1}q_{n}\text{,}\) and thus divides \(r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}\text{,}\) and so forth. Hence \(d\) divides \(a\) and \(b\text{.}\)
So the set of common divisors of \(a\) and \(b\) are equal to the set of divisors of \(r_{n-1}\text{,}\) so this algorithm really does give the gcd.