Division and Euclidean algorithms

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

The division algorithm for

If a, b with b 0 then q, r 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 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 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 .
   

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 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 Euclidean algorithm shows that gcd(a, b) is in I and this must be either a since a is the smallest element in I. So b is a multiple of a.
Thus I = < a > .

We now prove similar results for another ring.

The division algorithm for [x]

If a(x), b(x) [x] with b(x) 0 then q(x), r(x) [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 case.

2. The remainder is smaller than the divisor. In [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

Remark

The above shows that if you divide by a monic polynomial (one with leading coefficient 1) you can do it in [x], but in general you may need to invert some elements so you'd better be in [x].

Definition

The greatest common divisor of two polynomials a(x), b(x) [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 [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 -- except that the divisions are more tedious.

Remarks

In Maple the integer gcd is impemented 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 [x] is principal.

Proof
Just as in the 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 } of . It is denoted [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).
   

The division algorithm for [i]

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

Remarks

1. The remainder is smaller than the divisor. In [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 . 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.


Example

Divide 3 + 4i by 1 - i. In we have (3 + 4i)/(1 - i) = [multiplying top and bottom by 1 + i] (-1 + 7i)/2 and this is in the square:
So we have a choice of four quotients and remainders:
q₁ = 3i, r₁ = 3 + 4i - (1 - i)3i = i ;
q₂ = -1 + 3i, r₂ = 1 ; q₃ = 4i, r₃ = -1 ; q₄ = -1 + 4i, r₄ = -i.
In each case N(r_i) < N(1 - i) = 2

Definition

The greatest common divisor of two Gaussian integers u, v [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 [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 [i] is principal.

Remark

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

2. In the Microlab you will find there is an Algebra package in MacTutor and the stack Gaussian integers there will let you calculate with these (and with certain other interesting subrings of also).