Definition: Let E be a Euclidean domain. A greatest common divisor of e,f Î E, denoted by a = gcd(e,f), is an element of E such that there exists y,z Î E with ay = e, az = f (i.e. a is a divisor of both e and f) and d(a) ³ d(b) for any other common divisor of e and f.
Two things should be noted about this definition. One is that we have defined a greatest common divisor, not the greatest common divisor. There will usually be several common divisors with the same value for d. This actually happens even with the integers Z. Both 3 and -3 are common divisors of 6 and 9 and |3| = |-3|. Note that 3 and -3 are multiples of each other with 1 and -1, and 1 and -1 are the only elements of Z which have inverses in Z. In the case of Q[x], there will actually be infinitely many different greatest common divisors. It will turn out that all these common divisors are just constant multiples of each other. The constants are the only elements of Q[x] which have inverses in Q[x]. This pattern works out in general, but we won't spend the time to prove it.
The other feature of this definition is that it isn't the usual definition given in mathematics texts. The usual definition of a = gcd(e,f) is that a is a common divisor of e and f such that if b is any other common divisor of e and f, then b|a. This definition is equivalent to the definition we have given, but again we won't spend the time to prove that. One thing we will prove is the existence of greatest common divisors.
Theorem: Let e,f Î E, a Euclidean domain. Then there exists a greatest common divisor of e and f.
Proof: Consider the set {d(b): b a common divisor of e and f}. This set is non-empty since 1 is a common divisor of e and f. It is also a finite set since if bx = e, then d(e) = d(bx) ³ d(b), so the set is bounded above by d(e). Being a bounded finite set, it has a largest element, say d(a). Then a is a common divisor of e and f, and d(a) ³ d(b) for any other common divisor of e and f, which by definition makes a = gcd(e,f).
This theorem explains why we need condition (3) in the definition of a Euclidean domain. Unfortunately, while we have proven that greatest common divisors exist, the theorem doesn't give any useful guidance on how to find them. Fortunately, it isn't hard. You can find the gcd by using the Euclidean algorithm, just as we did when finding the gcd of two integers. In fact, the proof that the method works is exactly the same (so I won't bother writing it out again). This is the justification for calling domains satisfying conditions (1) through (4) of the previous handout "Euclidean," that they have a Euclidean algorithm.
Example: Find the gcd(x4 + x2 + x + 1, x3 + 1) in Q[x].
Carrying out division of polynomials, just as we were taught in College Algebra, we find
| x4 + x2 + x + 1 | = | x(x3 + 1) + (x2 + 1) |
| x3 + 1 | = | x(x2 + 1) + (-x + 1) |
| x2 + 1 | = | (-x - 1)(-x + 1) + 2 |
| -x + 1 | = | -1/2(x - 1)2 |
Example: Find gcd(x4 + x2 + x + 1, x3 + 1) in Z2[x].
This is the same problem as before, except we are working over the domain of polynomials with coefficients in Z2, rather than the domain of polynomials with rational coefficients. We solve the problem in the same fashion, using the Euclidean algorithm.
| x4 + x2 + x + 1 | = | x(x3 + 1) + (x2 + 1) |
| x3 + 1 | = | x(x2 + 1) + (x + 1) |
| x2 + 1 | = | (x + 1)(x + 1) |
Note that we got a different answer this time from last time. Q[x] and Z2[x] are different domains with different rules for multiplication, so they will sometimes have different greatest common divisors. Z2[x] is a very convenient domain from the standpoint of developing computer algorithms, since all the coefficients are either 0 or 1. We will see examples of this soon.