Return to highest common factor (idea)

If a,b are integers then the highest common factor (or greatest common divisor) is simply the largest integer that divides both a and b.

This definition does not generalise well to other interesting rings. For example, we want to be able to make sense of the highest common factor of two Gaussian integers or two polynomials. Here's the correct definition.

Definition Let R be a commutative integral domain and let a,b be two elements of R. We say that an element d in R is a highest common factor (or HCF) of a,b if

  • d | a (i.e. d divides a) and d | b
  • if e in R is such that e | a and e | b then e | d.

Notice that if R=Z this is essentially the same definition as we gave before. Except that we now are saying a highest common factor instead of the highest common factor. That's because according to the new definition if d is a HCF of integers a,b then so is -d.

In the general case if a HCF exists it is unique up to associates. This means that if d is a HCF then so is any associate. And conversely any other HCF has to be an associate. We use (a,b) to denote any HCF of a,b.

Notice that in general it is not guaranteed that a HCF exists. But they do always exist if R is a unique factorization domain. To prove this write

a=u.p1r1...pnrn and b=v.p1s1...pnsn
for units u,v, primes p1,..., pn then we get a HCF from

It's a familiar and useful fact that Euclid's algorithm will compute the HCF of an integer. More generally if R is a Euclidean ring the same algorithm will compute a HCF. This goes for the polynomial ring over a field or the ring of Gaussian integers. If you work backwards through the Euclidean algorithm you can see that it is possible to write (a,b)=ra+sb, for some r,s in the Euclidean ring R. I'll illustrate this with an example in a second but first let's note that there is a rather elegant existential proof of this fact.

Proposition Let R be a principal ideal domain. Then given two elements a,b there exist r,s such that

Proof: Consider the ideal I=aR+bR. This just means all elements of R of the form ar+sb. By assumption R is a PID so there exists d such that I=dR. Since d is in I it must be that there exist r,s such that d=ar+bs. Now to show d is a HCF. Since a is in dR this shows that d | a and likewise it divides b. Now suppose that e | a,b. then since d=ar+bs then e | d.

As promised here is an example of how to use the Euclidean algorithm to find the r,s of the proposition for the case of the Gaussian integers. Let a=3+i and b=2i.

(3+i)/2i = (3+i)(-2i)/2i(-2i) = -6i+2/4 = (-i+1) + (-1/2i-1/2)
so if we multiply up by 2i we get the first line in our workout of Euclid's algorithm
(3+i) = (2i).(-i+1) + (1-i)
But the next line is the last line
2i= (1-i)(-1+i)
so we see that 1-i = (3+i, 2i). The other HCFs can be found by multiplying this one by the units of Z[i] which are 1,-1,i,-i. Finally
1-i = 3+i + 2i(i-1)