Why is $\gcd(x^4+1,x^2-1) = 1$ but I get $2$? [unit normalization of gcds]

Question

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?

Answer 1

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.

Answer 2

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; said equivalently $\, c\mid a,b \!\iff\! c\mid \gcd(a,b),\, $ the universal definition of a gcd).

Often it is convenient to scale gcds by a unit to a normal form, e.g. in $\,\Bbb Z\,$ we normalize gcds $\ge 0,\,$ by scaling by the unit $-1$ if need be, 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, a nice unit normalization algorithm need not exist in all domains, so generally gcds are only determined up to unit multiples, i.e. up to associate-ness, so e.g. $\,\gcd(a,b)\approx 1$ means that the gcd is associate to $1$, i.e. is a unit, i.e $\,c\mid a,b\iff c\mid 1.\,$ Beware that a common abuse of language is to write $\gcd(a,b) = c\,$ to denote $\,\gcd(a,b)\approx c,\,$ esp. in contexts when there is no natural choice for unit normalization.

See here for further discussion.