Ytukyg

Find the gcd of $x^4-2x^3-x+3$ and $x^2-1.$

Note: I am using $a=bq+r$

First approach:

$$
begin{align*}
x^4-2x^3-x+3&=(x^2-1)(x^2-2x+1)+(4x+4)\
x^2-1&=(4x+4)(2x-2)+0
end{align*}
$$
Therefore, $text{gcd}(x^4-2x^3-x+3,:x^2-1)=x+1.$

Second approach:

$$
begin{align*}
x^4+5x^3+6x+3&=(x^2+6)(x^2-5x-6)+(4x+4)\
x^2+6&=(4x+4)(2x+5)+0
end{align*}
$$
Therefore, $text{gcd}(x^4+5x^3+6x+3,:x^2+6)=x+1.$

In the first approach I used the given polynomials while in the second approach I first used $text{mod}:7$ to change the negatives to positives and then proceeded with the calculation.

For both approaches, the remainders shown are in $text{mod}:7$ i.e.
in the first approach the remainder is actually $-3x+4$ and in the second its $-24x+39.$

Which approach is the correct way of solving such problems? If it matters, why? Also, suppose I used the first approach, would the final answer be $-3x+4$, $4x+4$, or $x+1$?

When calculating in quotient rings (or, equivalently, with ring congruences), we enjoy the freedom to choose any representative of an equivalence class, e.g. $bmod 7!: 8^nequiv 1^nequiv 1$ is simpler by choosing the rep $1$ vs. $8$ of $,8+7Bbb Z.,$ So in your gcd calculation we can choose the coefficient reps as we please. Usually smallest magnitude reps yield simpler arithmetic, here $,0,pm1,pm2,pm3,$ for $,Bbb Z/7.$

In general domains, gcds and lcms are defined only up to associates, i.e. up to unit (invertible) factors. For integers the units are $pm1,$ and we normalize a gcd $,gneq 0$ by choosing the positive choice from $pm g.,$ For polynomials over a field the units are all coef's $,cneq 0.,$ Hence the associates of $,gneq 0,$ are its constant multiples $,cgneq 0.,$ The standard normalization convention here is to choose the rep that is monic (lead coef $= 1),,$ i.e. if $,0 neq g,$ has lead coef $,a,$ then we unit normalize it to the monic $,a^{-1} g,,$ e.g. your gcd $,g = -3x!-!3,$ times $,(-3)^{-1}$ yields $,x+1,$ as its unit normalized standard rep.

Worth remark is that we can compute your gcd more simply. Notice $,x^2-1 = (x!-!1)(x!+!1),$ is a product of nonassociate primes therefore $,gcd(f,(x!-!1)(x!+!1)) = gcd(f,x!-!1)gcd(f,x!+!1).,$ Furthermore $, g := gcd(f,x!-!a) = x!-!a,$ if $,f(a)=0,$ else $,g = 1,,$ by the Factor Theorem. Hence the gcd in your example is $,x!+!1,$ because $,f(-1)equiv 0,$ but $f(1)notequiv 0pmod{!7}$.