Division and Euclidean algorithms

We now investigate some rather special rings. We start with a very familiar result.

The division algorithm for Z

If a, b ∈ Z with b ≠ 0 then ∃ q, r ∈ Z such that a = bq + r with |r| <|b|.

The element q is called the quotient and r is the remainder.

Proof

Assume a > b > 0. Subtract multiples of b from a until just before things go negative. The quotient q is the number of times you subtract and r = a - bq.

Remarks

1. The remainder is smaller than the divisor. In Z we measure "size" by absolute value.

2. Note that in fact there is a choice of remainders: you can either take it to be positive or negative.
   

The greatest common divisor (or highest common factor) of two integers a, b ∈ Z is the largest integer which divides them both.

Remarks

1. We measure the "largeness" using the absolute value.
   
   
2. The gcd is only unique up to multiplication by ±1. These are the invertible elements or units of Z.
   

The Euclidean algorithm

If d is the gcd of a, b there are integers x, y such that d = ax + by.

Proof

Here is an example: Take a = 76, b = 32 :

As a consequence of this algorithm we can now prove:

Theorem

Every ideal of Z is principal.

Proof

Let I be a non-zero ideal. Choose the smallest (non-zero) element a in the ideal I. If b is any other element then the gcd(a, b) is in I and this must be either ±a. So b is a multiple of a.
Thus I = < a > .

We now prove similar results for another ring.

The division algorithm for R[x]

If a(x), b(x) ∈ R[x] with b(x) ≠ 0 then ∃ q(x), r(x) ∈ R[x] such that a(x) = b(x)q(x) + r(x) with either r(x) = 0 or deg(r(x)) < deg(b(x)).

Remarks

1. Note that this is almost word-for-word the same as the Z case.

2. The remainder is smaller than the divisor. In R[x] we measure "size" by the degree.
   

Proof

We use the (slightly less well-known) process of dividing one polynomial by another (of lower degree). It is just like long division.
One example will suffice!
Take a(x) = 3x⁴ + 2x³ + x² - 4x + 1 and b = x² + x + 1

Definition

The greatest common divisor of two polynomials a(x), b(x) ∈ R[x] is a polynomial of highest degree which divides them both.

Remarks

1. This is the largest polynomial dividing both where we measure the "largeness" using the degree.
   
   
2. The gcd is only determined up to multiplication by a non-zero real number. These are the invertible elements or units of R[x].

3. Note that if you calculate the gcd of (say) 2 and 4 as polynomials you get the answer 1, while as integers the result is 2.
   

One can then prove:

The Euclidean algorithm for polynomials.

If d(x) is the gcd of a(x), b(x) there are polynomials p(x), q(x) such that d = a(x)p(x) + b(x)q(x).

Proof

Just the same as for Z -- except that the divisions are more tedious.

Remarks

In the calculating package Maple the integer gcd is implemented with igcd and the Euclidean algorithm with igcdex. For polynomials use gcd and gcdex.

The above result on principal ideals follows for this ring.

Every ideal of R[x] is principal.

Proof
Just as in the Z case, an ideal is generated by its smallest (in degree) element.

Remarks

1. An integral domain in which every ideal is principal is called a principal ideal domain or PID.

2. The results about the real polynomials above can be proved for the ring of polynomials F[x] over any field F. What we have just proved is that: F[x] is a PID.
   

Definition

The ring of Gaussian integers is the subring {a + bi | a, b ∈ Z} of C. It is denoted Z[i].

We'll prove the division and Euclidean algorithms for this ring but first we have to decide when one Gaussian integer is bigger or smaller than another.

Definition

The norm (or length) of the Gaussain integer a + bi is a² + b². We will write it as N(a + bi).

Remarks

1. This is, of course, |z|² with z = a + bi. It is more convenient not to take the square root, since it keeps the norm as an integer.

2. If u, v are Gaussian integers, the norm satisfies N(uv) = N(u)N(v).
   

If u, v ∈ Z[i] with v ≠ 0 then ∃ q, r ∈ Z[i] such that u = vq + r with N(r) < N(v).

Remarks

1. The remainder is smaller than the divisor. In Z[i] we measure "size" by the norm.

2. We will see that in fact there is sometimes a choice of remainders.
   

First divide u by v in C. You get a complex number u /v which lies in one of the "cells of the integer lattice".
At least one corner of the square is within distance 1 of u/v. This is the quotient q. The remainder is then r = u - vq and since |u/v - q| < 1 we have |u - qv| < |v| and so N(r) < N(v) as required.


Remark

For most positions of u/v there will be a choice of 2, 3 or even four Gaussian integers for the quotient.


Definition

The greatest common divisor of two Gaussian integers u, v ∈ Z[i] is a Gaussian integer of largest norm which divides them both.

Remarks

1. Note that we measure the "largeness" using the norm.
   
   
2. The gcd is only determined up to multiplication by an invertible Gaussian integer. These units of Z[i] are ±1 and ±i.
   

The Euclidean algorithm for Gaussian integers.

If w is the gcd of u, v there are Gaussian integers g, h such that w = ug + vh.

and then we can deduce:

Every ideal of Z[i] is principal.

Remark

A ring in which one can define a sensible notion of size which leads to a Euclidean algorithm is called a Euclidean ring.