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
(a,b)=p1min(r1,s1)...pnmin(rn,sn)
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
(a,b)=ar+bs.
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)