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 n_{1}, n_{2} with n_{1} > n_{2}. It is easy to see as a consequence of the Division Identity that either n_{1} = q_{1}n_{2} and consequently n_{2} = (n_{1}, n_{2}), or n_{1} = q_{1}n_{2} + n_{3} with n_{2} > n_{3} > 0. We iterate this process to obtain a set of relations

n_{i} = q_{i}n_{i+1} + n_{i+2} (1 < i< k)

n_{k}=q_{k}n_{k+1}

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

Now n_{k+1} = (n_{k}, n_{k+1}) and if n_{k+1} = (n_{i}, n_{i+1}) then n_{k+1} = (n_{i-1}, n_{i}) (i > 1) because certainly n_{k+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 n_{i} and n_{i+1}, generating a contradiction. Thus n_{k+1} = (n_{1}, n_{2}).

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

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

## Leave a Reply