# Whis is $\gcd(x^4+1,x^2-1) = 1$ but I get $2$ by the Euclidean algorithm?

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?

• g(x) has two real roots (+1, -1) while f(x) has no real roots. – Jimmy R. Mar 21 '15 at 17:54
• The gcd is only unique up to a unit. – MooS Mar 21 '15 at 17:56
• 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. – user3493525 Mar 21 '15 at 17:57
• @user3493525 It's supposed to be over R. Why are 1 and 2 equivalent? – Jonathan Mar 21 '15 at 18:02
• @Jonathan I will elaborate in an answer. – user3493525 Mar 21 '15 at 18:08

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.

• Note that I haven’t actually checked your calculation. – user3493525 Mar 21 '15 at 18:20
• 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. – Bill Dubuque Mar 21 '15 at 19:39
• @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$. – user3493525 Mar 22 '15 at 8:19
• 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. – Bill Dubuque Mar 22 '15 at 19:43
• @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. – user3493525 Mar 23 '15 at 8:16

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.

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}$$.

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

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.