2
$\begingroup$

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidean algorithm.

Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer.

  1. First I divided $f(x)$ by $g(x)$ and got that the remainder is $2$.
  2. Then, I divided $g(x)$ by the remainder, $2$, and got a remainder of zero, hence concluding that the gcd is $2$.

What am I doing wrong?

$\endgroup$
  • $\begingroup$ g(x) has two real roots (+1, -1) while f(x) has no real roots. $\endgroup$ – Jimmy R. Mar 21 '15 at 17:54
  • 1
    $\begingroup$ The gcd is only unique up to a unit. $\endgroup$ – MooS Mar 21 '15 at 17:56
  • $\begingroup$ GCDs are only defined up to associativity (i.e. pairwise divisibility). If your polynomials are over a field (e.g. $\mathbf{R}$, $\mathbf{Q}$), then gcds of 1 and 2 are equivalent. $\endgroup$ – user3493525 Mar 21 '15 at 17:57
  • $\begingroup$ @user3493525 It's supposed to be over R. Why are 1 and 2 equivalent? $\endgroup$ – Jonathan Mar 21 '15 at 18:02
  • $\begingroup$ @Jonathan I will elaborate in an answer. $\endgroup$ – user3493525 Mar 21 '15 at 18:08
3
$\begingroup$

If your polynomials are over $\mathbf{R}$, then a gcd of $1$ is equivalent to a gcd of $2$ (and any other nonzero real), because in general gcds are only well-defined up to associatedness, i.e. mutual divisibility.

The greatest common divisor of $f$ and $g$ is (in the case of polynomials) defined as a polynomial $d$ such that $d$ divides $f$ and $g$ and every divisor of $f$ and $g$ also divides $d$.

Thus, if we have another polynomial $e$ that is associated with $d$ (which means that $e|d$ and $d|e$), then we have $e|d|f$, $e|d|g$ and for every common divisor $z$ of $f$ and $g$ we have $z|d|e$, so $e$ is also a gcd of $f$ and $g$.

In your case you have two gcds of $1$ and $2$. Because $1\cdot 2 = 2$ and $2\cdot\frac12=1$ you have $1|2$ and $2|1$, so $1$ and $2$ are associated, thus if $1$ is a gcd, so is $2$ and vice versa.

Note that it is possible to normalize the gcd of polynomials by requiring the first nonzero coefficient to be $1$, which is what Wolfram|Alpha presumably does.

$\endgroup$
  • $\begingroup$ Note that I haven’t actually checked your calculation. $\endgroup$ – user3493525 Mar 21 '15 at 18:20
  • $\begingroup$ What do you mean by "gcds are only well-defined up to associativity, i.e. pairwise divisibility"? What is key to the OP is that gcds are only well-defined up to unit factors - see my answer. $\endgroup$ – Bill Dubuque Mar 21 '15 at 19:39
  • $\begingroup$ @BillDubuque I explained what I mean in my second and third paragraph. Is anything unclear about that? BTW, in an integral domain two elements $a$, $b$ are associated iff there is a unit $u$ such that $au=b$. $\endgroup$ – user3493525 Mar 22 '15 at 8:19
  • $\begingroup$ Ah, you mean associates (or associateness). In English one does not use associativity (or pairwise divisibility) to describe that. Even though I know well the term "associate" I was thrown off by that wording. $\endgroup$ – Bill Dubuque Mar 22 '15 at 19:43
  • $\begingroup$ @BillDubuque Ok, I will edit my answer. I learned this in German and could not find an English noun for being associated, so I had to guess. Thanks for the tip. $\endgroup$ – user3493525 Mar 23 '15 at 8:16
1
$\begingroup$

If you apply the Euclidean algorithm to $p(x)$ and $q(x)$ and the last non zero remainder is $44$, then there are polynomials $\alpha(x)$ and $\beta(x)$ such that $\alpha(x)p(x)+\beta(x)q(x)=44$. But then $\frac{\alpha(x)}{44}p(x)+\frac{\beta(x)}{44}q(x)=1$. So, $1$ is also a greatest common divisor of $p(x)$ and $q(x)$. Actually, if $r(x)$ is a greatest common divisor of $p(x)$ and $q(x)$, then so is $\frac{r(x)}k$, where $k$ is the coefficient of the monomiel with highest exponent in $r(x)$. Then $\frac{r(x)}k$ is a monic polynomial and it is usual to work with a monic polynomial when we are working with greatest common divisors of two polynomials.

$\endgroup$
1
$\begingroup$

The general principle behind this is the concept of units in a ring (with a $1$-element): https://en.wikipedia.org/wiki/Unit_(ring_theory)

A unit is an element of the ring that divides $1$ (the multiplicative neutral element). When you are dealing only with multiplication (like in this case), elements that differ only by a unit have exactly the same behaviour regarding divisibility (I assume a commutative ring here):

If $u$ is a unit and $x=yu$, then $x$ and $y$ divide exactly the same ring elements:

$$x|a \iff \exists f:fx=a \Rightarrow (fu)y=a \Rightarrow y|a$$

and with $u'={1\over u}$ we have $y=xu'$ and we get similiarly

$$y|a \iff \exists f:fy=a \Rightarrow (fu')x=a \Rightarrow x|a.$$

One can show very similiarly, that exactly the same ring elements divide $x$ and $y$.

So to state this again, regarding divisibilty, $x$ and $y$ have exactly the same properties.

That means if you find by some calulation that $\gcd(a,b)=x$, then you can also say $\gcd(a,b)=y$ (always assuming that $x=yu$ with $u$ being a unit). That means the $\gcd$ is only determined up to a unit!

When starting on these topics of divisibility and $\gcd$ etc. with $\mathbb Z$, this is usually ignored, as the only units of $\mathbb Z$ are $1$ and $-1$, and the general presentation on these topics is centered on positive integers, so the $-1$ gets ignored.

To come back to your problem, the ring in questions is ${\mathbb Q[x]}$. It's easy to check that in that ring the units are exactly the non-zero constant polynomials. That means that any $\gcd$ is only determined up to a unit (=constant polynomial). It is just as valid to claim the $\gcd$ equals the polynomial $p(x)=1$ or $q(x)=15$ or $r(x)=-2019.0319$, or whatever other constant comes to your mind.

As the other answers said, using the polynomial with the leading coefficient equal to $1$ is a general convention so results can be easily compared. It's the same (a convention) as writing one half usually as ${1 \over 2}$ and not the equally valid ${-17 \over -34}$.

$\endgroup$
  • $\begingroup$ Thank you for this explanation, I've seen the phrase 'determined up to units' before but now I understand it. $\endgroup$ – Shree Mar 19 at 19:21
1
$\begingroup$

Note that gcds are preserved under scaling by units (invertibles) because this holds true for divisibility, i.e. if $\,u\,$ is a unit then $\,ua\mid b\iff a\mid b\iff a\mid ub.\,$ Thus scaling a gcd by a unit does not alter its multiples nor its divisors, so it remains a gcd, i.e. a common divisor that is greatest divisibility-wise (i.e. divisible by every common divisor); equivalently $\, c\mid a,b \!\iff\! c\mid \gcd(a,b).$

When possible we often scale gcds by a unit to a normal form, e.g. in $\,\Bbb Z\,$ we normalize gcds $\ge 0,\,$ and in a polynomial ring $\,K[x]\,$ over a field, we normalize them to be monic (lead coeff $\,c_n = 1),\,$ by scaling the polynomial by $\,c_n^{-1}\,$ if need be (thus a constant gcd $\,c_0\neq 0$ normalizes to $1).\,$ However, such unit normalizetion is not possible in all domains, so generally gcds are only determined up to unit multiples, i.e. up to associate-ness.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.