Find the $\gcd$ of the polynomials $f(x)=5x^3 + x^2 + 5x + 1$ and $g(x)=5x^2 + 21x + 4$ over $\mathbb{Z}_5$.
For now I get these results
- $f(x)=g(x) x + (x+1)$
- $g(x)=(x+1)(5x+1) + 3$
But I'm stuck in the last passage and I think I've gone wrong somewhere in the exercise.
Best Answer
.The reason why you can reduce the coefficients of a polynomial modulo $p$ if evaluating the gcd of two or more polynomials modulo $p$, is because the $\gcd$ makes sense only for polynomials in the same ring : you cannot interpret $p$ and $q$ as polynomials with integer coefficients and demand their $\gcd$ over $\mathbb Z_5$, because they are not polynomials over $\mathbb Z_5$, but rather real polynomials. If they appear to have real, and not $\mathbb Z_p$ coeffients,then we reduce each coefficient modulo the prime to get a polynomial of simpler representation, which is equivalent to this polynomial in the ring of polynomials over $\mathbb Z_p$.
That is , $f(x) = x^2+1$ over $\mathbb Z_5$ and $g(x) = x+4=x-1$ over $\mathbb Z_5$. So the $\gcd$ of $f$ and $g$, as polynomials over $\mathbb Z_5$, is $1$, because $g(x)$ is irreducible (every polynomial of degree $1$ is) and does not divide $x^2 + 1$ because $1^2 + 1$ is not equal to $0$ modulo $5$, so $g(x)$ is not a multiple of $f(x)$. Therefore, $f(x)$ and $g(x)$ are coprime in $\mathbb Z_5$.