## Euclid’s Algorithm

Suppose that a and b are integers with b non-zero.  If there is an integer q such that a = qb, then we say that b divides a.

We can visualise the real numbers as lying in increasing order from left to right along a line.  If b is some non-zero integer, then the integers qb, where q runs through all the integers, divide the number line into segments of length |b| and all real numbers other than the qb lie inside one of these segments. Thus we can regard the following as self-evident:

Proposition (The Division Identity): If s is some real number and b is a non-zero integer, then either s = qb for some integer q (b divides s) or there is a unique integer q such that qb < s < qb + |b|.

Any integer that divides each of the integers m and n is called a common divisor or common factor of m and n. If m,n are not both zero we can assume that the set of all common divisors of m and n has a greatest member which is unique and call it the greatest common divisor of m and n and denote it as (m,n) or gcd(m,n). It is clear from the definition that: (m,n) = (|m|, |n|).

An algorithm for finding the gcd of two positive integers was given in Euclid’s Elements around 300 BC. Suppose the integers are n1, n2 with n1 > n2. It is easy to see as a consequence of the Division Identity that either n1 = q1n2 and consequently n2 = (n1, n2), or n1 = q1n2 + n3 with n2 > n3 > 0. We iterate this process to obtain a set of relations

ni = qini+1 + ni+2 (1 < i< k)

nk=qknk+1

The process must terminate because the ni form a descending, finite sequence of positive numbers and if it has not terminated beforehand, the condition ni+2 = 1 forces it to terminate at the next step.

Now nk+1 = (nk, nk+1) and if nk+1 = (ni, ni+1) then nk+1 = (ni-1, ni) (i > 1) because certainly nk+1 divides both these latter numbers and if there were a larger number that divided both of them it would also be a common divisor of ni and ni+1, generating a contradiction.   Thus nk+1 = (n1, n2).

We can obtain a measure of the efficiency of the Euclidean algorithm. Suppose there are k ≥ 3 steps, and that i < k. If ni+1 ≤ ni/2 then since ni+2 < ni+1 then ni+2 ≤ ni/2. If ni+1 > ni/2 then since 1 = ni+2/ni +qini+1/ni we must have qi = 1 and ni+2 ≤ ni/2 also. Hence when 2j + 1 < k we have

$\displaystyle \frac {n_{2j+1}}{n_{1}}=\frac {n_{2j+1}}{n_{2j-1}} ... \frac{n_3}{n_1} < \left( \frac{1}{2} \right)^j$

Set 2j + 1 = k – s where s = 1 or 2 depending whether k is even or odd. Then

$\displaystyle k = s + 1 + \frac {2}{\ln 2} \left( \ln n_{1} - \ln n_{k-s} \right) < 2 \frac{\ln n_{1}} { \ln 2} + 3$