2
$\begingroup$

Why is it that I can change the sign of a polynomial during the Euclidean algorithm as in the following example:

$ \begin{array}{lll} &(t^5 + t^3 -4t) : (t^5 + 2 t^3 - t) &= 1 &\text{remainder:}\quad -t^3 -3t \\ \\ &(t^5 + 2 t^3 - t) : (\mathbb{+} t^3 \mathbb{+} 3t) &= t^2 &\text{remainder:} \quad -t^3 -t\\ \end{array} $

1 Answers 1

4

The reason you can change signs is that $-1$ is a unit (a number with a multiplicative inverse). In general, if $u$ is a unit, then we have that $\gcd(a,b) = \gcd(a,ub).$

In doing the Euclidean algorithm, you are trying to compute the greatest common divisor by using the fact that for any $k$, $\gcd(a,b) = \gcd(a,b+ka)$ and so, if $b = qa + r$, then $\gcd(a,b) = \gcd(a,b+(-q)a) = \gcd(a,r).$ But since $\gcd(a,r) = \gcd(a,-r)$, you can then replace $r$ with $-r$ in order to compute the next division: after all, if $a=q_2r + r_2$, then $a = (-q_2)(-r)+r_2$, and what you really care about is $r_2$, not $q_2$ or $-q_2$.

(In fact, you can do better than change signs: you can multiply by any nonzero constant; so in the "next" step, you can always take the divisor to be monic if you want.)