Euclid's algorithm
Joe Snodgrass
Does Euclid's algorithm for finding the GCD of two polynomials work
for polynomials that don't have integer coefficients? TIA.
Pubkeybreaker
> Does Euclid's algorithm for finding the GCD of two polynomials work
> for polynomials that don't have integer coefficients? TIA.
What are the divisors of (say) 3/2???
What makes you think that the GCD is even defined?
JEMebius
> Does Euclid's algorithm for finding the GCD of two polynomials work
> for polynomials that don't have integer coefficients? TIA.
Euclid's Algorithm also works for polynomials with rational coefficients. Just multiply
such polynomials by the LCM of all denominators involved. Finally, divide the GCD thus
found by that LCM.
If there are irrational coefficients then one could try and find a relation to long
division, by way of generalization of Euclid's Algorithm.
The process of long division of divisor A into dividend B yielding quotient Q and
remainder R has the invariant relation B = A*Q + R. In practice the goal of a long
division is making R = 0, or if that is impossible, making its absolute value (*) as small
as desired / required / possible.
(*)
--------------------------------
absolute value derived from whatever valuation in the coefficient ring or in the
polynomial ring that fits into the context of the problem at hand.
Ciao: Johan E. Mebius
Pubkeybreaker
> Joe Snodgrass wrote:
> > Does Euclid's algorithm for finding the GCD of two polynomials work
> > for polynomials that don't have integer coefficients? TIA.
>
> Euclid's Algorithm also works for polynomials with rational coefficients. Just multiply
> such polynomials by the LCM of all denominators involved. Finally, divide the GCD thus
> found by that LCM.
??? 3/2 and 11/13 are polynomials. Their GCD is undefined. Your
"algorithm"
yields GCD = 1/26 and this makes no sense, since every non-zero
rational number
is a divisor of both 3/2 and 11/13.
The "GCD" is undefined under any reasonable definition of the word
"greatest"
that one might care to use.
JEMebius
I disagree.
Please make a serious study of ancient Greek math and take "GCD" in the sense of "Greatest
Common Measure".
Then you see that 1/26 is the GCM of 3/2 and 11/13. Indeed, 3/2 equals 39 times 1/26, and
11/13 equals 22/26. Better than 1/26 one cannot do because of GCD (39, 22) = 1.
Good luck: Johan E. Mebius
Ken Pledger
<7c5ca93c-b8e3-48f9...@f8g2000yqd.googlegroups.com>,
Joe Snodgrass <joe....@yahoo.com> wrote:
> Does Euclid's algorithm for finding the GCD of two polynomials work
> for polynomials that don't have integer coefficients? TIA.
Yes. The coefficients may be from any field F whatever, because
the polynomial domain F[x] admits division with remainder and hence the
Eucldean algorithm.
However, beware of expecting "the" rather than "a" g.c.d. Within
Z, the pair of numbers 6 and -9 have one g.c.d. which is 3 and another
which is -3. You can multiply any g.c.d. by -1 to get another g.c.d.
The numbers 1 and -1 are the units of the ring Z, i.e. the numbers
having multiplicative inverses in Z.
Within Q[x], the pair of polynomials (x^2 + x - 2) and (x^3 +
8) have one g.c.d. which is (x + 2), another which is ((5/2)x + 5),
another which is (-3x - 6), etc. etc. For every non-zero rational
number k, the polynomial (kx + 2k) is a g.c.d. Such numbers k
(i.e. polnomials of degree zero) are the units of the ring Q[x], i.e.
the polynomials having multiplicative inverses in Q[x].
Ken Pledger.
Tim Little
Polynomials over a field do have a well-defined GCD, and as always
"the" GCD is defined up to multiplication by units. (E.g. in Z there
are two gcds, one positive and one negative)
The canonical representative of these GCDs is typically taken to be
that with leading coefficient 1.
- Tim
Pubkeybreaker
> On 2010-12-20, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
>
> > On Dec 20, 4:00 pm, Joe Snodgrass <joe.s...@yahoo.com> wrote:
> >> Does Euclid's algorithm for finding the GCD of two polynomials work
> >> for polynomials that don't have integer coefficients? TIA.
>
> > What are the divisors of (say) 3/2???
>
> > What makes you think that the GCD is even defined?
>
> Polynomials over a field do have a well-defined GCD, and as always
> "the" GCD is defined up to multiplication by units. (E.g. in Z there
> are two gcds, one positive and one negative)
And in Q, EVERYTHING is a unit except 0.
Chip Eastham
What are we arguing about?
The OP is explicitly asking about polynomial
rings. If the coefficients are drawn from a
field, then the resulting ring is a Euclidean
domain, and the "Euclidean algorithm" works
where "greatest" is judged by degree.
You ask about the "GCD" of 3/2 and 11/13,
nonzero polynomials of degree zero. As I'm
pretty sure Pubkeybreaker knows, "the GCD"
refers to an equivalence class of
"associates", i.e. equivalence up to a
unit factor. So it's convenient in the
case of the (nonzero) polynomials to choose
1 as the class representative.
It is basic machinery of commutative ring
theory, covered in any first year of
abstract algebra at the graduate level,
if not earlier, that Euclidean domains
are PID's, PID's are UFD's, and UFD's are
GCD domains. Each of these inclusions is
strict, i.e. counterexamples can be given
to show the inclusions are proper.
The ring of polynomials over a Euclidean
domain is not necessarily Euclidean, but
the ring of polynomials over a UFD is
again a UFD, and hence a GCD domain. But
GCD only guarantees existence of greatest
common divisors, not the machinery of
the Euclidean algorithm.
regards, chip
Tim Little
True but irrelevant. The GCDs discussed by the original poster were
in Q[X] (or perhaps R[X]), not in Q.
- Tim
Alphy
Pubkeybreaker, you are usually quite rational in this forum and a good
contributor, so it mystifies me why you are being so wrong-headed.
The gcd is routinely used in ring theory, particularly for Euclidean
domains such as polynomials over a field. I don't know what you do
and don't know, so forgive me if I am saying things with which you are
familiar.
First of all a ring is collection of elements that can be "added" and
"multiplied" where these are both functions from ordered pairs to
single elements that have certain properties. Here multiplication is
commutative and there is a multiplicative identity. An ideal is a
subset of a ring that is closed under addition within itsself (the sum
of any two elements in the ideal is still in the ideal) and under
multiplication by any element in the ring. In other words multiply
any element of the ideal by any element in the ring and you get
another element of the ideal. A principal ideal is one that is
generated by a single element. Let us call that element x. Then the
ideal consists of every product xr where r is an element of the ring.
In the ring of polynomials over any field, all ideals are principal.
A unit in a ring is an element a in the ring such that 1/a is also in
the ring - for purists, there is an element b in the ring such that ab
= 1 where 1 is the multiplicative identity. Obviously these screw up
factorization, so we really factor ideals rather than elements, or
else we put in some verbiage about how to treat units.
That being said, polynomials over a field have unique factorization
(up to units of course) or we can say that there is unique
factorization of the ideals. There are two properties of the greatest
common factors that generalize readily to unique factorization
domains. The first is by looking at the minimum of the exponenents of
the prime factors of the two elements. The other is that the greatest
common divisor of two integers positive a and b is the unique positive
integer which divides both and and b and any other positive integer
which divides both a and b also divides it. Of course these have to
be expressed slightly differently in more general settings, but that
is very easily done. It is not important that these other sets of
things are not linearly ordered. These two properties are far more
commonly used for proving things about integers than is the standard
ordering of the integers.
It strikes me that you are getting too hung up on the word greatest.
However, you can put a partial order on ideals in a principal idea
domain such as the polynomials over a field,
namely a < b if a is a divisor of b. With this inequality, the gcd of
the two ideals of polynomials is indeed a maximal element in the set
of common divisors of a and b, so the term greatest common divisor can
in fact be quite reasonably employed.
Regards,
Achava
Bill Dubuque
Euclidean domains *are* preserved by localization.
Ditto for GCD domains and PIDs.
--Bill Dubuque