3.2 The Euclidean Algorithm

[http://www-gap.dcs.stand.ac.uk/~history/Mathematicians/Euclid.html](http://www-gap.dcs.stand.ac.uk/~history/Mathematicians/Euclid.html)

Figure 3.1: http://www-gap.dcs.stand.ac.uk/~history/Mathematicians/Euclid.html

For larger integers we can automate the process using one of the oldest algorithms in mathematics, Euclid’s algorithm:

Euclid’s algorithm (published in Book VII of Euclid’s Elements around 300 BC) is based on the following simple observation:

If \(a,b\) are integers with \(a>b\) then \(\gcd(a, b)=\gcd(a-b, b)\).

By repeated application of Euclid’s observation, we can reduce the size of the numbers involved in our calculations.

For example, suppose we wish to calculate \(\gcd(765432,56789)\). Euclid’s observation says that as \(765432 - 56789 = 708643\) then \(\gcd(765432,56789) = \gcd(708643,56789)\). But then \(708643 - 56789 = 651854\) and so \(\gcd(765432,56789) = \gcd(651854,56789)\). We continue our calculations in this fashion:

\[\begin{eqnarray*} 765432 - 56789 &= &708643\\ 708643 - 56789 &=& 651854\\ 651854 -56789&=& 595065\\ \vdots\\ \end{eqnarray*}\]

We can speed this process up slightly by observing that if \(a,b\) are integers with \(a>b\) then

\[\begin{eqnarray*} \gcd(a, b)&=&\gcd(a-b, b)\\ &=&\gcd(a-2b, b)\\ \vdots\\ &=&\gcd(r,b)\\ \end{eqnarray*}\]

where \(r\) is the remainder when we divide \(a\) by \(b\).

Now we can subtract 56789 from 765432, 13 times.

\[\begin{eqnarray*} 765432 - 13 * (56789) &= &27175\\ \gcd(765432,56789)&=&\gcd(56789,27175)\\ \end{eqnarray*}\]

We then repeat the process with the two smaller numbers 56789 and 27175.

\[\begin{eqnarray*} 765432 - (13) * (56789) &= &27175\\ \gcd(765432,56789)&=&\gcd(56789,27175)\\ 56789 - (2) * (27175) &=& 2439\\ \gcd(765432,56789)&=&\gcd(27175,2439)\\ \end{eqnarray*}\]

Carrying on in this way we can deduce the value of the \(\gcd(765432,56789)\).

\[\begin{eqnarray*} 765432 - (13) * (56789) &= &27175\\ 56789 - (2) * (27175) &=& 2439\\ 27175 - (11) * (2439) &=& 346\\ 2439 - (7) * (346) &=& 17\\ 346 - (20) * (17) &=& 6\\ 17 - (2) * (6) &=& 5\\ 6 - (1) * (5) &=& 1\\ 5 - (5) * (1) &=& 0.\\ \end{eqnarray*}\]

So gcd of \(765432\) and \(56789\) is \(1\).

The Remainder Theorem

At each stage of the process above, given integers \(a\) and \(b\), we have to find integers \(q\) and \(r\) such that \[a=qb+r\qquad\text{and}\qquad 0\le r<b.\] Recall that Theorem 2.14 which we proved in Chapter 2 tells us that for any positive integers \(a,b\) there are unique values of \(q\) and \(r\) satisfying the above conditions.

We will now generalise the result to allow negative values.

In order to be able to apply Lemma 3.12, we require the following important theorem.

Theorem 3.4 (Remainder Theorem)

If \(a\) and \(b\) are integers with \(b\neq 0\), then there is a unique pair of integers \(q\) and \(r\) such that \[a=qb+r\qquad\text{ and}\qquad 0\le r<| b|.\]

Here \(|n|\) denotes the absolute value of \(n\) which is defined by \[ |n|=\begin{cases} n & \text{if }n\geq 0\\ -n &\text{if } n\leq 0 \end{cases} \] Note that when \(n=0\) we can use either \(n\) or \(-n\) since \(-0=0\) (Exercise: Show this from the axioms of \(\mathbb Z\)).

The absolute value is constructed to be non-negative: When \(n\geq 0\) then \(|n|=n\geq 0\), and when \(0\geq n\) then \(|n|=0-n\geq n-n=0\) by (Sh).

Proof. As \(b\neq 0\) we have \(|b|\neq 0\). Since \(|b|\geq 0\) for any integer \(b\), we have \(|b|>0\).

We know \(a\geq 0\) or \(a\leq 0\) so we consider cases.

Suppose \(a\geq 0\):

Then we can apply Theorem 2.14 to the integers \(a\geq0, |b|>0\) to show \[\exists q',r\in\mathbb Z\text{ such that }\ a=q'|b|+r\text{ and } 0 \leq r < |b|.\] If \(b>0\) then \(|b|=b\) and \(q=q',r\) satisfy \(a=qb+r\) as required.

If \(b<0\) then let \(q=-q'\). Then \(qb=(-q)(-b)=(-(-q'))|b|=q'|b|\) (see exercises).

So again \(a=qb+r\) as required.

Hence the result is true when \(a\geq 0\).

Suppose \(a\leq 0\):

Then \(|a|=-a\geq 0\) so we can apply the first case to show \[\exists q'',r'\in\mathbb Z\text{ such that }\ -a=q''b+r'\text{ and } 0 \leq r' < |b|.\] Hence \(a=-q''b-r'\).

If \(r'=0\) then \(q=-q'',r=0\) satisfy \(a=qb+r\) as required.

If \(r'>0\) then \(-r'<0\) so \(|b|-r'<|b|\) while \(r'<|b|\) implies \(0<|b|-r'\) by (Sh).

Let \(r=|b|-r'\). We have \(a=-q''b-|b| +r\).

Letting \(q\) be \(-q''-1\) if \(b>0\) and \(-q''+1\) if \(b<0\) we have \(qb=-q''b-|b|\) so \(a=qb+r\) as required.

Exercise 3.5

Let \(a\) and \(b\) be integers with \(b\ne0\). Show that there exists a unique pair of integers \(q\) and \(r\) such that \[ a = qb + r\qquad\text{ and } -|b|/2<r\le|b|/2. \]

The following example will prove useful in Chapter 5.

Example 3.6

If \(n\) is a square then \(n\) leaves a remainder \(0\) or \(1\) when divided by \(4\).

Solution. Let \(n=a^2\).

According to Theorem 3.4 \(a=4q+r\) where \(r=0, 1, 2\) or \(3\), so that

\[n=(4q+r)^2= 16q^2+8qr+r^2.\]

If \(r=0\) then \(n=4(4q^2+2qr)+0\),
if \(r=1\) then \(n=4(4q^2+2qr)+1\),
if \(r=2\) then \(n=4(4q^2+2qr+1)+0\),
and if \(r=3\) then \(n=4(4q^2+2qr+2)+1\).

This completes the result.

Example 3.7

Show that any number that is both a square and a cube leaves a remainder of either 0 or 1 when divided by \(7\).

Solution. Let \(a\) be an integer. By the Remainder Theorem there exists integers \(q\) and \(r\) such that \(a = 7q + r\) and \(0\le r\le 6\). Hence \[ a^2 = (7q+r)^2 = 49q^2 + 14qr + r^2 = 7(7q^2+2qr) + r^2. \] Then \(r^2\in\{0^2,\ldots, 6^2\} = \{0,1,4,9,16,25,36\}\). But \(9 = 7+2\), \(16 = 7\times2+2\), \(25=7\times3+4\), \(36=7\times5+1\) and so \(a^2 = 7q' + r'\) where \(r'\in\{0,1,2,4\}\).

Using a similar argument, we see that if \(b=7q+r\) then \[ b^3 = (7q+r)^3 = 343q^3 + 147q^2r + 21qr^2 + r^3. \] We can then easily check that \(r^3\) leaves a remainder of \(0,1\) or \(6\) on division by \(7\) and hence \(b^3 = 7q'' + r''\) where \(r''\in\{0,1,6\}\).

So if a number is both a square and a cube it must have a remainder of either 0 or 1 when divided by \(7\).

We shall consider lots of examples of Euclid’s algorithm later in this chapter. For now, we want to focus on proving that Euclid’s observation is true and that the resultant algorithm gives the correct result.

Recall our definition of a divisor

We say that an integer \(d\) is a divisor of the integer \(a\) if and only if there is an integer \(b\) such that \(a=db\).

Notice that the definition is phrased entirely using properties of the integers encoded in the axioms given in Chapter 2.

Now what can we say about divisors using the axioms and the definitions?

Every integer divides \(0\). This is because \(0=d\cdot0\). Notice that this is not one of our axioms but we can deduce it from the axioms, and will do so in one of the tutorial sheets for the course.
\(1\) divides every integer. This is because \(a=1\cdot a\) from axiom (Id).
Every integer divides itself. This is because \(a=a\cdot 1\) from axiom (Id).
\(0\) does not divide any integer except itself. If \(a=0\cdot b\) then \(a=0\), from the first of these observations.

We have already mentioned that we shall attempt to avoid using division whenever possible. The following important result will often help us in this task.

Lemma 3.8 (Cancellation Lemma)

If \(m,n,p\) are integers with \(m\cdot p=n\cdot p\) then either \(p=0\) or \(m=n\).

Proof. Since \(m\cdot p=n\cdot p\) we have \(m\cdot p-n\cdot p=n\cdot p-n\cdot p=0\) by axiom (Neg).

By axiom (Comm) we get \(p\cdot m-p\cdot n=0\) and by axiom (Dist) we get \(p(m-n)=0\).

Now by axiom (ZD) either \(p=0\) or \(m-n=0\), and so \(p=0\) or \((m-n)+n=0+n\) which means \(m + (-n+n)=n\) by (Id) and (As). Hence \(m=m+0=m+(n-n)=n\) by (Id), (Neg) and (Comm) as required.

Lemma 3.9

Let \(a,b\) and \(c\) be integers.

If \(a| b\) and \(b| c\) then \(a| c\).
If \(a| b\) and \(c| d\) then \(ac| bd\).
If \(m\neq 0\), then \(a| b\) if and only if \(ma| mb\).
If \(d| a\) and \(a\ne 0\) then \(|d| \le|a|\).

Proof. Let \(a,b\) and \(c\) be integers.

If \(b=ma\) for some integer \(m\), and \(c=nb\) for some integer \(n\), then \(c=n(ma)=(nm)a\) and \(nm\) is an integer.
If \(b=ma\) for some integer \(m\) and \(d=nc\) for some integer \(n\), then \(bd=(ma)(nc)=((ma)n)c=(m(an))c=(m(na))c=((mn)a)c =(mn)(ac)\).
If \(ma|mb\) then there is an integer \(k\) such that \(mb=k(ma)=m(ka)\). Since \(m\neq 0\) we can apply the cancellation lemma to see that \(ka=b\). It follows that \(a|b\) as required.
Now suppose that \(a|b\). Since \(m|m\) and \(a|b\) it follows that \(ma|mb\) by part 2.
If \(a=md\) for some integer \(m\) then \[|a|=|md|=|m||d|.\] Since \(a\neq 0\) then \(m\neq 0\) and so \(|m|\geq 1\). Hence \(|a|\geq |d|\).

This concludes the proof.

Notice that in part (4), we have mentioned that \(|md| = |m||d|\). This is not one of the axioms, but can be deduce from the axioms and will appear as an example in one of the tutorial sheets for the course.

Let \(a_1,\ldots, a_k, u_1, \ldots, u_k\) be integers. We shall refer to an expression of the form \[ a_1u_1+\cdots+a_ku_k \] as a linear combination of the integers \(a_1,\ldots, a_k\).

Theorem 3.10

Let \(a_1,\ldots, a_k, u_1, \ldots, u_k, a, b, c\) be integers

If \(c\) divides \(a_1, \ldots, a_k\), then \(c\) divides any linear combination of the integers \(a_1,\ldots, a_k\).
\(a| b\) and \(b| a\) if and only if \(a=\pm b\).

Proof. Let \(a_1,\ldots a_k, u_1, \ldots u_k, a, b, c\) be integers

If \(c\) divides \(a_i\) then \(a_i=q_ic\) for some integers \(q_i\) (\(i=1, \ldots, k\)). Then \(a_1u_1+\cdots+a_ku_k=q_1cu_1+\cdots+q_kcu_k=(q_1u_1+\cdots+q_ku_k)c\), and as \(q_1u_1+\cdots+q_ku_k\in\mathbb Z\) (since \(q_i, u_i\in\mathbb Z\)) we see that \(c| (a_1u_1+\cdots+a_ku_k)\).

NOTE:

The fact that we can “pull” the factor of \(c\) out of this expression is due to the distributive law (Dist), the commutative law (Comm) and the associative law (As) for integer multiplication and addition.

If \(a=\pm b\) then \(b=qa\) and \(a=q'b\) where \(q=q'=\pm 1\). Hence \(a| b\) and \(b| a\).
Conversely, suppose that \(a| b\) and \(b| a\), so \(b=qa\) and \(a=q'b\) for some integers \(q\) and \(q'\).
If \(b=0\) then the second equation gives \(a=0\), and so \(a=\pm b\) as required. Suppose now that \(b\neq 0\).
Combining the two equations, we have \(1.b = b = qq'b\), and so by the cancellation lemma, and since \(b\neq 0\), we deduce that \(qq'=1\).
Hence \(q\) and \(q'\) both divide \(1\), and by Lemma 3.9(4), \(|q|\le |1|=1\) and \(|q'|\le 1\).
Hence \(q\) and \(q'\) are both in the set \(\{-1, +1\}\) and \(a=\pm b\).

We get the following very useful Corollary for the case \(k=2\).

Corollary 3.11

If \(c\) divides \(a\) and \(b\), then \(c\) divides \(au+bv\) for all integers \(u\) and \(v\).

We are now in a position to prove Euclid’s observation mentioned earlier.

Lemma 3.12

If \(a,b\) are integers with \(a=qb+r\) then \(\gcd(a,b)=\gcd(b, r)\).

Proof. By Corollary 3.11, any common divisor of \(b\) and \(r\) also divides any integer of the form \(ub+vr\).

Now if \(a=qb+r\) we can put \(u=q\) and \(v=1\) to see that any common divisor of \(b\) and \(r\) is also a divisor of \(a\). Hence any common divisor of \(b\) and \(r\) is also a common divisor of \(a\) and \(b\).

Conversely, any common divisor of \(a\) and \(b\) also divides \(a-qb\) (again by Corollary 3.11, with \(u=1\) and \(v=-q\)).

Hence any common divisor of \(a\) and \(b\) is also a common divisor of \(b\) and \(r=a-qb\).

Thus the two pairs \(a, b\) and \(b, r\) have the same common divisors, so they have the same greatest common divisor.

Proof of Euclid’s Algorithm

We are now in a position to prove that Euclid’s algorithm, both terminates, and produces the desired greatest common divisor. We use the remainder theorem to successively define the integers \(r_i\) so that \(r_1\) is the remainder upon dividing \(a\) by \(b\) and for \(i\geq 1\) each \(r_{i+1}\) is the remainder upon dividing \(r_{i-1}\) by \(r_{i}\). \[ \begin{array}{rclcr} a&=&q_1b+r_1&&0\le r_1<b\\ b&=&q_2r_1+r_2&&0\le r_2<r_1\\ r_1&=&q_3r_2+r_3&&0\le r_3<r_2\\ &\ldots&\\ r_{i-1}&=&q_{i+1}r_i+r_{i+1}&&0\le r_{i+1}<r_i\\ &\ldots&\\ r_{n-1}&=&q_{n+1}r_{n}+r_{n+1}&\qquad&0\le r_{n+1}<r_n\\ r_n&=&q_{n+2}r_{n+1}+0.\\ \end{array} \] In particular we have \(a\geq b>r_1>r_2>\ldots \geq 0\). By the well ordering principle this process stops, and by inspection we see it can only stop when the final remainder is \(0\).

By Lemma 3.12 we see that \[ \gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\ldots \] and in general each pair \(r_i, r_{i+1}\) has the same greatest common divisor as the successor pair \(r_{i+1}, r_{i+2}\) so in particular (and by induction) \(\gcd(a, b)=\gcd(r_n,r_{n+1})=r_{n+1}\) as required.

Example 3.13

To calculate \(d=\gcd(1815, 1415)\) we write

\[ \begin{array}{rcr} 1815&=&1\times1415+400\\ 1415&=&3\times400 +215\\ 400&=&1\times215+185\\ 215&=&1\times185+30\\ 185&=&6\times30+5\\ 30&=&6\times5+0\\ \end{array} \] The last non-zero remainder is \(5\), so \(d=5\).

In many cases, the value of \(d\) can be identified before a zero remainder is reached: since \(d=\gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\ldots\), one can stop as soon as one recognises the greatest common divisor of a pair of consecutive terms in the sequence \(a, b, r_1, r_2, \ldots\). In Example 3.13, for instance, the remainders \(185\) and \(30\) clearly have greatest common divisor \(5\), so \(d=5\).

Exercise 3.14

Use Exercise 3.5 to devise an alternative algorithm to Euclid’s for calculating the greatest common divisor. This is known as the least remainders algorithm.

Euclid’s algorithm for polynomials

A polynomial over the integers is a function like \(5x^3+2x^2+7x-4\) with integer coefficients. It’s degree is the highest power of the variable which arises in the expression. [There is a much more formal definition which can be given, but it agrees with this naive idea.]

The set of all integer polynomials shares certain similarities with the integers. In particular we can add, subtract and multiply polynomials just as we can integers. Note that the polynomials include constant polynomials, i.e. the integers.

The operations on polynomials satisfy all of the algebra axioms – (Op),(Id),(Neg),(Comm),(As),(Dist) and (ZD) – as the integers do.

To have a version of the Remainder Theorem we also need the idea of ordering. One approach is to say that \(f\le g\) if and only if \(f=g\) or \(f\) has strictly lower degree than \(f\). The idea here is that “smaller” polynomials are ones of lower degree. This order satisfies (Ref),(AS),(Tr),(Sc) and a variation of (WO)⁸.

The idea is then to apply a version of the remainder theorem to polynomials \(f,g\) (essentially long division of polynomials) to write \[g=q\cdot f+r \] where \(q,r\) are polynomials and \(r<f\) (meaning that the degree of \(r\) is less than the degree of \(f\)).

Lemma 3.12 works as before to say that the common divisors of \(q,f\) are the same as the common divisors of \(f,r\), to these have the same greatest common divisors (though now there may be more than one “greatest” common divisor since greatest is defined only in terms of the degree of the polynomials).

The question of divisibility of integers complicates the question of divisibility of integer polynomials. A version of the remainder theorem for polynomials will work provided that the leading coefficient⁹ of \(f\) is a divisor of the leading coefficient of \(g\). Things are much simpler if we look at polynomials with rational coefficients in which case the remainder theorem always works.

You will find a description of Euclid’s algorithm in the context of polynomials on the page

http://en.wikipedia.org/wiki/Greatest common divisor of two polynomials

Rings

Definition 3.15

A ring is a set \(R\) equipped with two binary operations \(+,\cdot\) and satisfying the axioms (Op),(Id),(Neg),(Comm),(As),(Dist).

Of course \(\mathbb Z\) is an example of a ring as we based the definition of ring on (most of) the algebraic axioms of \(\mathbb Z\).
The set of polynomials with coefficients in \(\mathbb Z\) is a ring.
The rational numbers \(\mathbb{Q}\), the real numbers \(\mathbb{R}\) and the complex numbers \(\mathbb{C}\) are examples of rings.
The set of polynomials with coefficients in \(\mathbb{Q},\mathbb{R}\) or \(\mathbb{C}\) is a ring.
The set \(\{0,1\}\) with the operations \(\oplus\) defined by \(0\oplus 0=1\oplus 1=0\) and \(0\oplus 1=1\oplus0=1\) and the usual multiplication \(\cdot\) is a ring. We can think of this example as representing even/odd (where \(0\) is interpreted as meaning even and \(1\) meaning odd): \[\text{even}\oplus\text{even}=\text{odd}\oplus\text{odd}=\text{even},\qquad \text{even}\oplus\text{odd}=\text{odd}\oplus\text{even}=\text{odd}\]

We will see other examples of rings in later chapters when we study modular arithmetic.

Non-empty sets of polynomials will have one or more least elements.↩︎
The leading coefficient of a polynomial is the coefficient of the highest power of \(x\).↩︎