Talk:Polynomial greatest common divisor/Archive 1

This is an archive of past discussions about Polynomial greatest common divisor. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

GCD calculations wrong

x^2 + 7 x + 6 = (x + 1)(x + 6) indeed, but x^2 + 5 x - 6 = (x - 1)(x + 6), not (x + 1)(x - 6), as it is written presently.

Hence, the GCD = x + 6 and not x + 1. —Preceding unsigned comment added by 83.29.152.37 (talk) 20:10, 18 November 2010 (UTC)

Why so many examples?

Does four examples seem excessive? Oh – why aren't the Euclidean algorithm examples worked out all the way? DavidCBryant 14:07, 9 March 2007 (UTC)

please do finish the example for Euclid's algorithm with polynomials. I had trouble with formating. Example 4 is different. The later examples show the superiority of the Vedic method. Larry R. Holmgren 05:50, 10 March 2007 (UTC)

As far as formatting is concerned, there are good examples at Polynomial long division on how to format things. (But this is a bit off-topic :) Oleg Alexandrov (talk) 06:06, 10 March 2007 (UTC)

Yes, the first two examples are redundant and can be omitted. Larry R. Holmgren 15:12, 25 April 2007 (UTC)

Problems with the article

I added Template:Expert because I saw the following problems with the article:

The most common method, the Euclidean algorithm acting directly on polynomials, is not mentioned at all. Instead, it uses the Euclidean algorithm in a weird way which I haven't seen before and which will lead to problems if you don't pick the number x = 10 properly.
The so-called Vedic method is proven to be right and illustrated with examples, but it is never explained what this method actually is.
Apparently, the later examples show the superiority of the Vedic method, but it's not clear what this is based on.
As far as I can guess from the incomplete information, the Vedic method is rather similar to the Euclidean algorithm. Anyway, the article is seriously unbalanced in giving so much attention to the Vedic method.

-- Jitse Niesen (talk) 14:15, 30 March 2007 (UTC)

It seems like the best thing to do would be to move the "vedic method" into a separtate article. Certainly, the greatest common divisor of polynomials as commonly taught and understood outside of India does not involve it. Arcfrk 07:38, 5 April 2007 (UTC)

I agree. The "vedic method" seems to be an interesting historical method, but it doesn't work all the time (for example, if the highest and lowest powers are removed at the same time), and after the first part of the method, it has two polynomials whose GCD needs to be found and it reverts to factoring.

It shares some similarity with the Euclidean Algorithm in that it starts with decreasing the degree of the polynomials (removing the highest degree term reduces degree and removing the lowest degree term allows one to factor out

x

, again reducing degree). It isn't as efficient at doing so, though, as it takes two steps to decrease the degree by one, whereas the Euclidean Algorithm decreases degree with every step.

In summary, I think it should have its own page as it's neither standard nor superior (or even equivalent) to standard methods and seems to be of mainly historical interest. A short reference to such a page would then be appropriate. Kfgauss 20:13, 1 June 2007 (UTC)

Isn't this "Vedic" stuff only of interest to historians of ancient mathematics? --JeremyBoden 21:19, 6 July 2007 (UTC)

I disagree J.B. The subject is algebra, polynomials, and finding their GCF. The origin of the algorithm may be of historical interest but does not preclude our interest in and use of said algorithm. Likewise is our interest in the origin of "Hindu numerals" and their use (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9). Larry R. Holmgren 03:50, 7 July 2007 (UTC)

In order to remove Template:Expert, we need to figure out how to handle the "Vedic method." Here's how I see the current situation:

Pace StatisticsMan, the Vedic method is not defined at all in this article. Before we regard it as a "method" on par with factorization or the Euclidean Algorithm, we need to articulate it, step by step. This is done for factorization in section 3.1 (current version), and for the Euclidean Algorithm on its own page, linked from section 3.2. If someone knows explicitly what the Vedic method is, that person should write "section 3.3." (As far as I can tell, the method is not described any more explicitly in the given references.)
The section called "Algebraic proof..." claims to prove that the Vedic method is valid. But the proof is not sound. Specifically:
- the sentence beginning "Therefore, the GCD of P and Q is also..." does not follow logically from the sentence before it, without some further explanation, and
- neither does the final sentence -- it is not sufficient to say that "then the GCD appears and shows itself."]
- There is certainly a problem with the claim that $GCD(P,Q)=GCD(MP+NQ,MP-NQ)$ , unless we put clear conditions on M and N. (It's probably fine if M and N are scalars, but we seem to take $M=2x$ in example 3. We need to know why N isn't divisible by x.)
In fact, kfgauss suggests that a counterexample exists. I agree, except that I'm worried I may not know what the Vedic method really is. We can't tell whether the Vedic method always works, or sometimes fails, until we have "section 3.3" in place.
The fact that the proof is not sound raises the issue of the reliability of the references given for the Vedic method.
Nevertheless, as Larry argued, I think the method is worth mentioning here. Even if it doesn't work in general, it seems like a useful way to make some initial simplifications in a given problem.

I'd like a user who understands this method to show how the Vedic method is applied to $GCD(x^{2}+6x+5,x^{2}+4x+5)$ . That would let us make some progress. If this doesn't happen in a while, I think we should conclude that the Vedic method doesn't work in general. Hopefully these issues can be resolved and we can move on to reorganizing the examples :). Jaswenso 00:11, 3 September 2007 (UTC)

Given Lambiam's major edit at 02:38 today, I've now gone ahead and done what I think is sensible with the Vedic method. It's included as a helpful idea, but not as a standalone method. I think that's best, because AFAICT it is only a degree-reduction trick for transforming some problems into simpler problems. That's useful, I think, but one still needs a way to solve the simpler problem.

I hope I've clarified the conditions under which the method is valid, and why it works (when it does).

I've also added a bigger example, solved by all 3 "methods." It seems to me that the practical issues involved are more visible in that example.

If this general approach gains consensus, I think Template:Expert can probably be removed. That's not to say that the article is perfect, by any means: not least, my math formatting could be beautified quite a bit! Jaswenso 17:27, 3 September 2007 (UTC)

definition

The definition is a little weird. There are two main definitions given of GCD in various abstract algebra books, both of which are totally equivalent. This definition combines both definitions in one. I guess that is somewhat acceptable but I think it'd be better to just define the greatest common divisor as the actual greatest (highest degree polynomial) common divisor (it divides both polynomials). Then, it is a consequence that any common divisor, h(x), must divide the GCD. So, I am changing the definition in this way.

Also, its being unique is not part of the definition so I am putting this as a consequence as well.

Thirdly, it is only defined for polynomials if at least one of them is nonzero. If they are both zero, then every polynomial divides them so there is no greatest common divisor. But, this definition does not account for that fact so I am adding that part in. I have seen one book which defines the GCD of two zero polynomials to be the zero polynomial but many others which do not do this.

It also has a typo, currently saying the "greatest common denominator" but obviously it should be divisor, not denominator.

StatisticsMan 06:36, 21 April 2007 (UTC)

Someone messed up the first section; the conclusion, "= 5x+1" does not make sense. Larry R. Holmgren 15:14, 25 April 2007 (UTC)

I've reworked this example. The point is that if polynomials don't have unique prime factorizations, then in general the GCD will not be uniquely defined. I've tried to be more explicit about how this works. Jaswenso 17:11, 1 September 2007 (UTC)

HCF

If you want to use HCF for highest common factor, you should say somewhere that HCF will stand for highest common factor. I changed the definition to include (GCD). Also, I've looked in many books and can't ever remember this being called the highest common factor. Add to that the fact that this page is called the "greatest common divisor..." and that the term defined is "greatest common divisor", I am changing every instance of HCF to GCD. I think it would be acceptable/good to put a note that in some places this is called the highest common factor and is abbreviated HCF (I left in the parenthetical statement which says "or highest common factor". But, as I've already said, it should be abbreviated GCD throughout this article.

StatisticsMan 06:36, 21 April 2007 (UTC)

Vedic Method

The proof of this method has two typos (missing a ± and missing an N), both of which I am now correcting.

StatisticsMan 06:36, 21 April 2007 (UTC)

I disagree that the "vedic method" should be moved

"It seems like the best thing to do would be to move the "vedic method" into a separtate article. Certainly, the greatest common divisor of polynomials as commonly taught and understood outside of India does not involve it. Arcfrk 07:38, 5 April 2007 (UTC)"

I disagree. I've never seen this method but it seems very nice. If the article is unbalanced, then let's make it more balanced. We don't need four different examples on the vedic method. It is defined perfectly well. Give one or two nice examples tops of its use and stop. Honestly, one nice example explained nicely seems best. Then, give exactly one example each of the other two methods also. Then, the article is nice in that it has three nice methods and an example of each in case some people find it hard to understand the method's definition. It is not unbalanced and it is not cluttered with tons of examples on one subject. StatisticsMan 06:48, 21 April 2007 (UTC)

The important thing is not 'balance', it's accuracy. You have confirmed that you have not seen the method before. This strongly suggests WP:OR concerning the main topic of the article, namely, gcd of two polynomials. But there is no problem describing the method elsewhere, in a separate article. Arcfrk 04:08, 31 May 2007 (UTC)

Arcfrk, this article was started to show the Vedic method of finding the GCD or (HCF) of two polymonials. Both the Vedic method and Euclid's Algorithm are simple enough that an Algebra I student can do them while factoring is easy only with low degree expressions. The Vedic method of elimination of the highest and lowest powers deserves to be included. Furthermore, the only reference is from a book on Vedic Math.Larry R. Holmgren 17:54, 10 September 2007 (UTC)

I think we are spending way too much time and energy on these "vedic" methods, which have at best marginal notability and very limited significance. They are given totally undue prominence. A footnote and a link to Vedic mathematics would just be fine. --Lambiam 23:28, 10 September 2007 (UTC)

Future Changes

Hey, these are changes I think should be made and I would like to have input from others. Though, if I don't get any, I'll probably just do these. Also, this list might not be complete, just things I'm thinking about right now.

1. In looking at the regular GCD page, not polynomial GCD, I see lots of other stuff such as a section on properties of the GCD. This same thing could be added here.

2. The one Euclidean algorithm example, as mentioned above, is not done in the same way the Euclidean algorithm is done in most books (at least I've seen). So, I'd redo this example so it is done in that way, doing the division algorithm repeatedly until the GCD is achieved. And, I could include in that part the fact that we can then show the GCD as a linear combination of the two polynomials.

2.a. Along the same lines, instead of completely explaining the Euclidean algorith, we can just put a link to the Euclidean algorith Wikipedia page which already mentions polynomial stuff.

3. The math formatting needs to be redone. I'm not so sure on those boxes (dotted lines), whether it would be better to have them or not, but I know for sure that the math should all be redone with <math.> and </math.>.

4. Split things up in sections better... right now there's just examples and it doesn't flow real well, just several examples. It'd be nicer to have a section on methods. Then, hierarchically below that, three sections, one each on the three methods. Each of those could then have an example section itself. Perhaps at the end, there could be one more example showing all of the three methods used on the same pair of polynomials.

5. Could talk about gcd of more than two polynomials.

6. A lot of time, I see lots of links in articles I think are dumb. For example, I mention some basketball thing happened on a certain date and someone makes the date a link to the page for that day. I mean, I sort of see this but it mostly has no relation to the article. That being said, there are probably at least a few links on this page we could do such as polynomial, coefficients, field and that's just in the first few words.

That's all I have right now. Like I said, let me know what you think.

StatisticsMan 04:24, 24 April 2007 (UTC)

Mathematical Style

And, I had not even read the Manual of Style (mathematics) yet, so there are more changes.

7. It suggests starting the article with an informal definition that is easily accessible. Then, later, possibly in a definition section, put the formal definition. That's all for now.

StatisticsMan 05:48, 25 April 2007 (UTC)

Vedic method

I've been bold and

removed the incomprehensible proof of the unexplained Vedic method;
removed the list of mainly Vedic examples that made the article totally lopsided.

--Lambiam 02:41, 3 September 2007 (UTC)

"The trick," i.e., the method of finding the GCD by canceling the highest and the lowest powers, is within the power of a 1st year algebra student using pencil and paper! It works on pairs of polynomials without use of a computer and without a multitude of "invisible" steps. No example was given where the Vedic math "trick" did not find the GCD of two polynomials. While I appreciate the inclusion of an example of 5th degree polynomials I found most of the examples difficult to follow as the lines were very wide and steps were missing. Lastly, I object to the use of the word "trick" as a title of an algorithm. Larry R. Holmgren 19:41, 3 September 2007 (UTC)

No offense is intended; I don't regard "trick" as derogatory. Feel free to edit, but: the "Vedic method" cannot be called an "algorithm" unless/until it's written out, step by step, as the factorization method and the Euclidean algorithm are. See the definition at algorithm, in fact: "...a finite list of well-defined instructions for accomplishing some task...." Until this is written, the null hypothesis is that the Vedic method is not an algorithm. WP:PROVEIT applies here.

Notwithstanding, here are examples. Nothing in the article has shown me how to apply the Vedic method to

GCD(x^{3}+6x^{2}+11x+6,~x^{3}-4x^{2}+x+6)

,

(which is the kind of example mentioned by kfgauss) nor to

GCD(x^{2}+1,~2x^{5}+13x^{4}+17x^{3}+15x)

.

I bet we could find consensus more easily if you'd show me how these two are done.

Even if it's not an algorithm, it's a good trick, and probably deserves to be included here.

For what it's worth, the Euclidean Algorithm can certainly be done with paper and pencil by a student. Certainly, for big polynomials, either method is likely to be better than factoring.

Finally: when you write "steps are missing," I think you're referring to the Euclidean Algorithm section of the example. I wasn't sure it would be helpful to show the (very big) long divisions on the screen, but perhaps it would; please do add any missing steps and/or improve the formatting. I'm sorry; I'm a newbie, and very bad at the typesetting -- hopefully someone who's better at this than I am can help?

Jaswenso 20:31, 3 September 2007 (UTC)

Just as the method of solving systems of equations by judicious multiplications so to eliminate a variable, this Vedic method of eliminating the highest and the lowest degree terms is worked out.

Given two polynomials, find their GCD, greatest common divisor. 
 $GCD(x^{3}+6x^{2}+11x+6,~x^{3}-4x^{2}+x+6)$  
By subtraction we can eliminate both the x-cubed term and the constant term:            x^3 +6x^2 +11x +6 
              -(x^3 -4x^2 +x   +6)  
                    10x^2 +10x 
Then, pull out the common factors, 10(x)(x + 1). 
By analyzing the original pair of expressions we see that neither
ten nor x are common factors, hence the remaining expression,
(x+1) is their GCD. 
Check: The sum of the odd power coefficients equals the sum of the
even power coefficients when (x+1) is a factor.
Does 1+11=6+6? Yes. And does 1+1=-4+6? Yes. 
Therefore, (x+1) is a factor of both expressions.
The Vedic method of elimination of highest and lowest powers 
says that (x+1) is their greatest shared factor, their GCD.  —Preceding unsigned comment added by Larry R. Holmgren (talk • contribs) 23:12, 3 September 2007 (UTC)

(unindent) OK, thanks. Here's what puzzles me. What's wrong with the following example?

Find  $GCD(x^{3}+6x^{2}+11x,~x^{3}-4x^{2}+x)$ .
The difference is  $10x^{2}+10x$ .
Remove the common factor:  $10x(x+1)$ .
The remaining  $(x+1)$  is GCD.
Check:  $(x+1)$  does not divide either of the given polynomials.  Now what?

Forgive me if I seem dense; but this is the point. If the Vedic method is an algorithm, I'm not supposed to have to make "judicious" choices. I should just be able to follow the steps. What are the steps?

Perhaps the second example will make things clearer to me. Thanks for the energy you're putting into this page. Jaswenso 23:40, 3 September 2007 (UTC)

Find  $GCD(x^{3}+6x^{2}+11x,~x^{3}-4x^{2}+x)$ . 
We can find the GCD working in parallel columns. 
First eliminate the highest powers. 
Then eliminate the lowest powers. 
Then factor and compare the results. 
       Expression A:           Expression B: 
       x^3 +6x^2 +11x          x^3 -4x^2 +x 
Eliminate the x-cubed term by subtraction, (A-B).
Eliminate the x-term by subtraction of (A-11B). 
       x^3 +6x^2 +11x          x^3 + 6x^2 +11x 
     -(x^3 -4x^2 + x )     -(11x^3 -44x^2 +11x )
Difference: 10x^2 +10x       -10x^3 +50x^2 
Factored:   10(x)(x+1)  and  -10(x)(x)(x-5) 
By inspection, 10 is not a common factor. 
On sight we see that x is a common factor. 
The Vedic technique shows that x is also their GCD.

Larry R. Holmgren 21:28, 5 September 2007 (UTC)

By the way: given enough downtime, my mind finally stopped withholding the word "technique." I hope that's less objectionable than "trick." Sorry; I didn't mean to offend. Jaswenso 23:46, 3 September 2007 (UTC)

Assuming that the page [1] is a moderately accurate translation of the cited reference, the reference contains no description of a "Vedic algorithm." As I've tried to emphasize, this doesn't make it a bad technique; it's just not an algorithm. We might be able to produce one ourselves, but that would violate WP:NOR. I think we've gone as far as we can with this method, unless further sources are available. Jaswenso 01:47, 4 September 2007 (UTC)

OK, thanks, Larry. Unless a Vedic computation of

GCD(x^{2}+1,~2x^{5}+13x^{4}+17x^{3}+15x)

is still forthcoming, I guess I understand the method completely now. Let me emphasize again that I think it's cool. It's just not an algorithm.

Jaswenso, your reference above, has mis-spelled sūtra. The only reference in the article is mine, for the Vedic method. A proof of the Vedic method was given in the article but it was rejected. I apologize for the Swami. He was 80 years old and suffering from glaucoma when he re-wrote his manuscript! Here is a working of the GCD for your second pair of polynomials. Yes, here, Euclid's Algorithm is easier.

 $GCD(x^{2}+1,~2x^{5}+13x^{4}+17x^{3}+15x)$ 
Expression A:               Expression B: 
x^2 +1                      2x^5 +13x^4 +17x^3 +15x 
        Factored,(x)(B'): x(2x^4 +13x^3 +17x^3 +15 ) 
Eliminate the fourth power x-term by subtraction, (B'-15A).
Eliminate the constant term by subtraction of (B'-(2x^2)A).
         2x^4 + 13x^3 + 17x^2 + 15       2x^4 +13x^3 +17x^2 +15
       -(2x^4         + 2 x^2     )                 -(15x^2 + 15) 
Difference:    13x^3  + 15x^2 + 15  and  2x^4 + 13x^3 +2x^2   
Factored:    1(13x^3  + 15x^2 + 15) and  1(x^2)(2x^2 +13x +2)
The trinomials are prime. Hence their GCD = 1. 
Expressions A and B are relatively prime.
Larry R. Holmgren 04:33, 6 September 2007 (UTC)

Again, thanks. I didn't intend to suggest that the external link above should be added to the reference list -- but I don't have the book Vedic Mathematics... at hand. A Google search pointed me to the website I mentioned above. I presume that its contents reflect the contents of the book. Please let me know if that's not true.

As I recall, I was one of the editors who objected to the "proof" that used to be in the article. It was not a correct proof, and it was not possible for it to be correct -- because there was no way of knowing what was to be proved -- because we can not cite any reference in which the Vedic method is adequately specified for application to the general case. Do we agree on this last point? Jaswenso 14:13, 6 September 2007 (UTC)

Jaswenso, the link works. I do have a copy of that book. www.vedamu.org does use material directly from the Vedic Mathematics book but with new examples. The proof is very general, showing that adding or subtracting multiples of the quotients of the original expressions divided by the GCD also have the GCD as a factor. [Vedic Mathematics: Sixteen Simple Mathematical Formulae from the Vedas, by Swami Sankaracarya (1884-1960), Motilal Banarsidass Indological Publishers and Booksellers, Varnasi, India, 1965; reprinted in Delhi, India, 1975, 1978. Page 99.] If a step is missing please complete it and make it rigorously acceptable.Larry R. Holmgren 15:07, 6 September 2007 (UTC)

Though I'm sure I've made errors here, a "Vedic algorithm" might look something like this.

Input : p(x), q(x)
Output: GCD(p(x),q(x))
Pre   : Let LC denote a function defined on (some set of) polynomials, such that LC(f) is the
  leading coefficient of f.  Let M denote an integer-valued function defined on (that set of)
  polynomials, such that f(x) is divisible by x^M(f) but not by x^M(f)+1.
-------------------
Fix g(x)=x^{min{M(p(x)), M(q(x))}}.
(*) Replace p(x) by p(x)/(LC(p(x))x^M(p(x))).
Replace q(x) by q(x)/(LC(q(x))x^M(q(x))).
If p(x)=q(x), then quit; g(x)p(x) is the desired answer.
Otherwise, by switching the names of p and q if necessary, ensure that deg(p(x)) ≥ deg(q(x)).
Replace q(x) by x^{deg(p(x))-deg(q(x))}q(x).
Replace p(x) by p(x)-q(x).
Replace q(x) by q(x)-(q(0)/p(0))p(x).
Go back to the (*) label and continue.

This is an algorithm: it's a finite list of well-defined instructions. But it's not suitable for inclusion in Wikipedia, even if it happens to work, because I just made it up. It's my own abstraction of the four very special examples given in Vedic Mathematics..., together with some of my own answers (based on my familiarity with the Euclidean Algorithm and unique factorization domains) to questions that are not addressed in the original source.

I don't think we could say that this algorithm is superior to the Euclidean Algorithm.

It would be cool if we had a source that provided such an algorithm, because only when the method is completely specified might we be able to prove that it really does (or does not) apply in general. Absent that, I think the current version of the article has it right: the contribution of Vedic Mathematics... is that it gives examples of a useful idea for reducing some GCD problems to simpler problems. Jaswenso 03:01, 6 September 2007 (UTC)

Well, Lambiam, the article is no longer lop-sided, the Vedic method has been excised completely, the cavalier, mathematical surgeons have done their work. Only two pencil and paper methods remain! My book reference and the discussion are all that remain of the Vedic method of the elimination of highest and the lowest powers in my article on three methods of finding the GCD.Larry R. Holmgren 05:38, 14 October 2007 (UTC)

Why is the Euclidean algorithm example so complex?

From a user point of view I found the extended example for this article unduly complex. Surely we could have a simpler example without so many fractions. I realise that the authors wish may have been to stress the required monic nature of a solution however I feel a simpler example would be more beneficial than the complex one that is currently there. If there is consent for it to be changed then I may go ahead and post something simpler. The only hesitation I have is that I would use a more general method of polynomial division rather than the synthetic division used in the example, however that is a matter of general applicability of the algorithm to cases where synthetic division is difficult.

Milco2002 (talk) 11:33, 5 June 2008 (UTC)

Why monic polynomial?

From what I've learnt, GCD is unique up to a constant. Any constant multiple of the monic GCD should also be GCD. However, the article defines GCD as a monic polynomial without providing any source. Can anyone provide a valid source to support the requirement to be monic?202.40.137.196 (talk) 10:43, 28 January 2010 (UTC)

This should not be understood as a definition but as a convention: To get a unique result for the GCD one usually choses the monic variant among all the possible multiples.--LutzL (talk) 12:07, 28 January 2010 (UTC)

If it should not be understood as a definition, why is it stated as a such? In the article, the formal definition is written as "The greatest common divisor of p(x) and q(x) is the monic polynomial d(x) of highest degree such that d(x) is a divisor of p(x) and of q(x)". I agree that it's a convention but I don't think this is part of the formal definition.202.40.137.202 (talk) 09:12, 30 January 2010 (UTC)

As Humpty Dumpty realised, definitions are there to be our servants, not our masters. The definition which restricts the greatest common divisor to be a monic polynomial is convenient, and is therefore commonly used. No, I can't offhand provide a source, but I am sure they exist. I have, nevertheless, rewritten the definition in the article to satisfy the objection raised in the anonymous posts above, and added a note explaining the usual restriction to monic polynomials. JamesBWatson (talk) 14:10, 1 February 2010 (UTC)

I think the part about it being monic is wrong. For a start, that only works for polynomials over a field e.g. polynomials over the rationals. What about polynomials over the integers or multivariate polynomials?

Instead what is considered to be the gcd of polynomials is the product of the gcd of its contents and the gcd of its primitive parts ie.

\gcd(A(x),B(x))=\gcd({\text{cont}}(A),{\text{cont}}(B))\cdot \gcd({\text{pp}}(A(x)),{\text{pp}}(B(x))).

The gcd of primitive parts is itself primitive (due to Gauss's lemma). All polynomials over a field are primitive by definition (and therefore have a content equal to 1). Since the GCD over a field makes no sense then I guess taking the monic polynomials makes sense. But for the more general case of polynomials over a UFD (which itself is a UFD), the gcd is not necessarily primitive let alone monic.

My source for this would be Algorithms for Computer Algebra by Geddes et al. (1992, Kluwer Academic Publishers, ISBN 0-7923-9259-0). Just thought I'd put this here first in case I misinterpreted the text. -- Borb (talk) 15:02, 14 April 2010 (UTC)

Feel free to add a section about polynomial gcd's with coefficients in UFD, integral or even non-integral domains. No one is claiming that the article is finished. If the contents is extended, then this should also be reflected in the intro.--LutzL (talk) 08:17, 15 April 2010 (UTC)

New lead

I have rewritten the lead in order to follows wp:LEAD and to mention the important facts about polynomial GCD's. IMO the remainder of the article has to be rewritten and expanded in order to follows the structure sketched in the lead. This is a hard work, that I am not sure to be able to do soon. Thus some help would be welcome. D.Lazard (talk) 13:14, 9 August 2012 (UTC)

Due to some edit conflicts occurring while cleaning up (today), I'd better stay out of the way and let other editors e.x. D.Lazard make edits before continuing. I apologize for edit conflicts. Maschen (talk) 13:14, 10 September 2012 (UTC)

Lede

I presume that the lede has undergone various revisions over the years, but I would like to add this comment about it. The opening sentence and paragraph is

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a notion which is very similar to the greatest common divisor of two integers.

That's the entire first paragraph, and it does not define the title term. Then the second paragraph starts off talking about methods of computing it. As far as I can see, the opening section never does define it.

Would anyone object if I modify the first paragraph to say

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that gives no remainder when polynomial long division is used to divide it into either of the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

Revisions welcome. Duoduoduo (talk) 15:15, 5 October 2012 (UTC)

I would prefer

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that divides evenly the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

There are two reasons for this. First, the article is not restricted to univariate polynomials and your formulation is. In my recent edits I have been careful to write or rewrite the lead in a way which is convenient for people which know only univariate polynomials, but remains correct when applied to multivariate case. The second reason is that polynomial long division is a specific algorithm, thay is not needed here.

By the way, in my recent edit, I had some trouble , because Euclidean division of polynomials does not exists. I have created it as a subsection (and, just now, as a redirect to this section). Should it be a separate article? How Euclidean division (which contains one sentence about this topic) and Polynomial long division should be updated or merged?

D.Lazard (talk) 15:43, 5 October 2012 (UTC)

It seems to me that Euclidean division and Polynomial long division are fine as they are, as separate articles. Maybe you could mention late in the lede of Euclidean division that the concept extends beyond the integers.

In the present article, while I haven't looked at it very closely, it seems that the section GCD by hand writing computation (better title: GCD by hand computation) assumes the polynomials are univariate. Then the section Univariate polynomials with coefficients in a field seems to partially overlap with it. Maybe the former section could be cut down to apply in general, and everything univariate could be placed in the section with univariate in its title. Duoduoduo (talk) 17:21, 5 October 2012 (UTC)

Before I began to expand this article (August 8) the article consisted in only three sections, the one now called GCD by hand writing computation (I agree with your proposition to change its title) and the two preceding ones. I have minimally edited these three sections, only to avoid mathematical mistakes and contradictions with the newer sections. Even after my edits on these sections, I am not fully comfortable with them. IMO, they should be rewritten to become an introduction to the remainder of the article, which is accessible to the layman. But I am too far of being a layman to do this correctly. Thus, intervention of other editors would be welcome. I agree that one possibility could be to insert most of section GCD by hand computation as an introductory subsection of Univariate polynomials with coefficients in a field, which could be called Introductory examples. Also the example at the end of the article could be introduced here to show that things are not as simple as it could seem. Some work is yet needed on this article. D.Lazard (talk) 20:42, 5 October 2012 (UTC)

Your ideas sound good. Sorry that I can't help -- this article is way beyond my expertise. Duoduoduo (talk) 21:58, 5 October 2012 (UTC)