Is it always possible to find the G.C.D of two polynomials?

[Arian.D]

Suppose that we've been given two polynomials and we want to find their Greatest Common Divisor. For integers, we have the Euclidean algorithm which gives us the G.C.D of the two given integers. Could we generalize the Euclidean algorithm to be used to find the G.C.D of any two given polynomials using long division?

If yes, how? For example I want to show that x+1 and x²+5x+6 are two co-prime polynomials. How could I do that? And can I ultimately find a way to represent this fact using the Bezout's theorem? (I mean can I finally find A and B as two polynomials that we have A(x+1) + B(x²+5x+6) = 1?)

 

[Arian.D]

OK, I did something for examination, I used long division and obtained this:

x²+5x+6 = (x+1)(x+4) + 2

That means (1)(x²+5x+6) + (-x-4)(x+1) = 2. So, A=(-1)(x+4) and B=1. The thing that (1)(x²+5x+6) + (-x-4)(x+1) equals 2 (a polynomial of degree 0) tells us that these two polynomials are relatively prime to each other. Right? So if two polynomials are relatively prime to each other, there exists a linear combination of them that is equal to a zeroth degree polynomial. Right?

Could I always use long division to find the G.C.D of two polynomials?

 

[chiro]

Hey Arian.D.

Do you simply want to factorize an existing polynomial P(x) by getting P(x) = B(x)Q(x) + R(x) where you are given B(x) and P(x)?

The answer is a definite yes as long as B(x) <> 0. This is taught in high school mathematics and is simply a statement of the division theorem but for polynomials.

In terms of the GCD for the polynomials, you do exactly the same as what is done in Euclid, but the difference is that you use polynomials. You will always get GCD(P(x),B(x)) = 1 at a minimum just like you do in the use of integer expressions, and the interpretation of the GCD is exactly the same, but in the context of polynomials.

As an exercise, take a polynomial of say order 4 and do an example of figuring out the GCD using Euclids algorithm of (P(x),B(x)) where you have examples where P(x) has no polynomial factor and where it does (like for example expand (x+1)(x-2)(x+3) and then use Euclids algorithm to find GCD(P(x),(x-2)) for example.

 

[Arian.D]

Hey Arian.D.

Do you simply want to factorize an existing polynomial P(x) by getting P(x) = B(x)Q(x) + R(x) where you are given B(x) and P(x)?

The answer is a definite yes as long as B(x) <> 0. This is taught in high school mathematics and is simply a statement of the division theorem but for polynomials.

In terms of the GCD for the polynomials, you do exactly the same as what is done in Euclid, but the difference is that you use polynomials. You will always get GCD(P(x),B(x)) = 1 at a minimum just like you do in the use of integer expressions, and the interpretation of the GCD is exactly the same, but in the context of polynomials.

As an exercise, take a polynomial of say order 4 and do an example of figuring out the GCD using Euclids algorithm of (P(x),B(x)) where you have examples where P(x) has no polynomial factor and where it does (like for example expand (x+1)(x-2)(x+3) and then use Euclids algorithm to find GCD(P(x),(x-2)) for example.

Hi Chiro,

Well, I always get stupid in the early hours when I wake up. lol. I know that the ring of polynomials over a field is indeed a Euclidean ring, but is this true if the coefficients are coming from any arbitrary ring? I'd like to add more conditions on what I had said earlier. For example, could we always find A and B as monic polynomials? It seems the answers is no from my example.

Actually I was working on continued fractions. I know that many elementary functions have generalized continued fractions and I also know that Gauss has proved a beautiful relation between his hyper-geometric function and a generalized continued fraction. Since there is already an algorithm to find the simple continued fraction of any real number using the Euclidean algorithm, I thought maybe it could be the case with polynomials as well and we could always represent a polynomial of degree n as a simple terminating continued fraction, and then, with a little generalization, we succeed to show that any given Taylor series could be represented as a simple continued fraction. That was the general idea. I also asked myself if there could be any logical generalization for the ceiling function that takes a polynomial and gives another polynomial with some nice properties because there's obviously a link between the Euclidean division algorithm and the ceiling function.

So, what do you think? Do you think given a polynomial of degree less than n, we could represent it as a simple continued fraction? And could we represent a given Taylor series as an infinite simple continued fraction?

 

[chiro]

According to this: the standard structure of a continued fraction for a number is given by a sequence of {a_n}n=1 to infinity that has the definition given in the wiki article.

Are you trying to find the {a} sequence where each element of the sequence is a polynomial? If so what further constraints do you wish to have for the actual sequence elements?

 

[Arian.D]

According to this: the standard structure of a continued fraction for a number is given by a sequence of {a_n}n=1 to infinity that has the definition given in the wiki article.

Well, yea, you could associate a sequence of \{ a_n\}_{n\in \mathbb{N}} to any simple continued fraction if that's what you're saying because I didn't fully understand what you meant. I usually denote a continued fraction by the symbol [a_0;a_1,a_2,...] which is more comfortable than the sequence notation.

Are you trying to find the {a} sequence where each element of the sequence is a polynomial? If so what further constraints do you wish to have for the actual sequence elements?

Yes. I'm trying to find the proper sequence where each element is a polynomial. I think I should add a further constraint so it becomes a nice question that the elements of the sequence should be irreducible polynomials (That's ideal, but I think even if the degree of each element of the sequence is less than the previous one, it's still a nice question). In case of polynomials with real coefficients, I'd accept only linear and quadratic factors.

So here is the question reworded in a more mathematically meaningful way: Given a polynomial of degree less than n, I'm looking for a simple continued fraction that its elements are irreducible polynomials.

And then the question would be, could we generalize this result to polynomials of infinite degree? i.e. Taylor series.

 

[chiro]

It's definitely an interesting question.

The irreducible nature of all the elements of the sequence implies that a0 is also irreducible which means GCD(a(x),b(x)) = 1 where b(x) has degree less than or equal to a(x).

So I guess if we start off with a finite degree polynomial, then we can establish through the division theorem, the conditions required for the irreducibility factors to maintain.

For example if we start off with a polynomial ax^2 + bx + c, then we can say given a polynomial ex + f, we use the division algorithm with the coeffecients left as variables to give us the conditions for a factorization over a general field (R), and then if we change the field to the rationals, integers, or naturals, we then use number theory to identify the constraints.

So let's just for the moment consider any factorization with real coeffecients (I know this is not what you want, but bear with me). We use the division algorithm to take a finite polynomial and generate the condition to get a remainder 0. This doesn't necessarily give is irreducible, but it does give us the constraints for an actual factorization.

Now for the irreducible part: all we have to show for irreducible polynomials is that there exists no factorization when the polynomial we divide by is less than or equal to the degree of the starting polynomial: basically the reverse of the above in that the remainder is always non-zero, over the selected field (which will no doubt be an integer or rational one of some kind).

Now for the continued fraction part: we know that we have to get an irreducible polynomial for all elements of the sequence, and the above definition with non-zero R for the entire field gives us this. We then use this to construct the set of irreducible polynomials over that field in the context of our original polynomial, and then given that all elements of the sequence have this property, we take it from there.

As for the infinite-case, the key thing IMO will be the irreducibility.

The first thing is to show any case where there is no irreducibility. Now in the criterion above, I used the non-zero remainder as a criterion for irreducibility but obviously for an infinite polynomial this is not going be as simple.

I'd characterize the above as trying to factorize an infinite-number because the number of factors is potentially infinite given that the degree shoots off to infinity, and so the actual nature of factorization is nothing like the bounded degree case.

Let's look at an example why in the context of normal number theory, this doesn't make sense in general.

Consider the infinite polynomial (x - 1)^n where n goes to infinity. Now we can factor this into (x - 1) * (x-1)^(n-1) where n is still going to infinity. But this doesn't make sense as a unique factorization! This is the problem with an infinite polynomial and factorization.

You will need to develop a new form of decomposition for the infinite-case where the decomposition has uniqueness like we have uniqueness for any prime-decomposition for an integer > 1.

 

[algebrat]

Isn't there an issue if your coefficient of highest degree term is not a unit? That is, if your coefficients are not in a field, but more generally in a ring, e.g. the integers.