highest common factor (idea)
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 integer]s or two [polynomial]s. 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
Notice that if R=[integer|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 [associate]s. 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...pnsnfor [unit]s u,v, [prime]s 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 integer]s. 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 integer]s. 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 [unit]s of Z[i] which are 1,-1,i,-i. Finally
1-i = 3+i + 2i(i-1)