1

I need to calculate the GCD of $$x^4+3x^3+2x^2+x+4 \ \text{and } x^3+3x+3 \ \text{in} \ \mathbb{Z}_5$$ Using Euclid algorithm: $$x^4+3x^3+2x^2+x+4 = (x^3+3x+3)(x+3)-3x\\ x^3+3x+3 = (-3x)(\frac{1}{3}x^2 - \frac{2}{3})+3 \\-3x = (3)(-x)+0 $$ Now I should consider the last not-null remainder (so 3) that (I think) it should be the GCD, actually it seems that the GCD is 1 according to wolfram

So my question is: what result should I consider as GCD when GCD is calculated with polynomials?

Loris Simonetti
  • 567

2 Answers2

1

Over the field $\Bbb F_5$ we have $$ x^4+3x^3+2x^2+x+4=(x^3 + 4x^2 + x + 1)(x + 4) $$ and $x^3+3x+3$ has no root in $\Bbb F_5$ and hence is irreducible. So is the other polynomial of degree $3$. Here we have used that a cubic polynomial over a field is reducible if and only if it has a root. From this it is clear that the gcd is equal to one.

Dietrich Burde
  • 130,978
1

In general GCDs are only defined up to unit factors* -- so since $3$ is a unit in $\mathbb Z_5$, saying that the GCD is $3$ is the same as saying the GCD is $1$.

*For polynomial rings over a field, it is common to choose the representative of the set of GCDs that is a monic polynomial, so in that sense it is slightly more conventional to say that $1$ is the GCD than to say $3$ is it. But that's a normalization you'd do after Euclid's algorithm. (Or, for that matter, you might choose to normalize each remainder to be monic after each step. That makes no significant difference since for divisibility purposes you're essentially always just concerned with the ideals generated by each of the concrete polynomials you're looking at).

Troposphere
  • 7,158
  • Maybe I did not understand what a unit factor in a modulo is... but $3 mod 5$ is congruent to $-2 mod 5$, so why 1? in the meantime, I'll mark yours as the answer. – Loris Simonetti Mar 31 '21 at 19:28
  • 1
    @LorisSimonetti: A "unit" of a ring is an element that has a multiplicative inverse. $3$ is a unit in $\mathbb Z_5$ because it has an inverse, namely $2$ -- that is, $3\cdot 2\equiv 1\pmod 5$. – Troposphere Mar 31 '21 at 19:29
  • So basically every time the GCD is a value with multiplicative inverse I can just say that the GCD is 1? – Loris Simonetti Mar 31 '21 at 19:32
  • That is correct. (In a polynomial ring over field, the elements that have multiplicative inverses are exactly the nonzero constant polynomials.) – Troposphere Mar 31 '21 at 19:38
  • Ok, I got it, Thank you very much! – Loris Simonetti Mar 31 '21 at 19:39