GCD of polynomials over GF(p) I have two polynomials:
$$
f(x)=(x^2+1)(x-2)
$$
$$
g(x)=(x^3+7)(x-2)  
$$
I am supposed to find their GCD over GF(p) for some prime p.
I "understand" that their GCD is $(x-2)$ but what is the meaning to find the GCD over $GF(2)$ or $GF(3)$?
I know that $(x-2) \equiv x \pmod 2$, so the GCD(f,g) over GF(2) is $x$?
Am I right? wrong? Am I getting anywhere?
Thanks!
 A: It means what it literally says; $f(x)$ and $g(x)$ are given as polynomials with coefficients in, say, $\mathbf{F}_5$. (any polynomial with coefficients in the integers can easily be converted to such a polynomial) Then, you compute their polynomial $\gcd$.
And the $\gcd$ might not be $x-2$. Continuing with the $\mathbf{F}_5$ example, it turns out that their $\gcd$ is $(x-2)^2$, because
$$ (x^2 + 1) = (x-2)(x-3) $$
$$ (x^3 + 7) = (x-2)(x^2 + 2x + 4) $$
and $x^2 + 2x + 4$ is relatively prime to $x-3$. But rather than factoring, the $\gcd$ can be easily computed by using the Euclidean algorithm.
Of course, $(x-2)^2 = (x+3)^2 = (x-2)(x+3)$, so any of those could be given as the $\gcd$.

One might be interested in the more sophisticated question of, given those two polynomials with coefficients in the integers, for which values of $p$ their $\gcd$ be $(x-2)$ after converting them into polynomials over $\mathbf{F}_p$.
The answer to this question can be solved with resultants; as polynomials over the integers, we have
$$ \text{Res}(x^2 + 1, x^3 + 7) = 50 $$
which tells us that these two polynomials will be relatively prime (after converting them into polynomials over $\mathbf{F}_p$) if and only if $p$ is relatively prime to $50$.
In particular, this means you need to rethink your statement of the $\gcd$ in the case of $p=2$!
(note that $\text{Res}(f(x), g(x)) = 0$ which tells us that $f$ and $g$ aren't even relatively prime over the rational numbers!)
A: Hint $ $  Use Euclid's algorithm $\rm\ gcd(a,b) = gcd(a,b\ {\bf mod}\ a)\ $
and this $\rm\:gcd(ca,cb) = c\,gcd(a,b)$
$$\rm\quad (x\!-\!2)\,gcd(\color{}{x^2\!+\!1},\,7\!+\!\color{#c00}{x^3})\, =\, (x-2)\,gcd(\color{#0a0}{x^2}\!+\!1,\,7\!\color{#c00}{-\!x})\, =\, (x\!-\!2)\,gcd(\color{#0a0}{7^2}\!+\!1,\,7\!-\!x)$$
where we used $\rm\:{\bf mod}\ \ \color{}{ x^2\!+1}\!:\ x^2\!\equiv -1\, \Rightarrow\,\color{#c00}{x^3\!\equiv -x};\: $  $\rm\:{\bf mod}\ \ 7\!-\!x\!:\ x\equiv 7\:\Rightarrow\:\color{#0a0}{x^2\!\equiv 7^2}$
Remark $\ \rm{GF}(p) = \Bbb F_p\:$ denotes the finite field of $\rm\:p\:$ elements. The Euclidean algorithm works for polynomials over any field, in the same way as it does over the classical fields, because polynomial long division-with-remainder algorithm works universally for polynomials that are monic (i.e. lead coefficient $= 1$). But, over a field, every polynomial is associate to a monic polynomial (multiply it by the inverse of the leading coefficient).
A: Often things turn up in mathematics to have a natural ordering. In particular, when it comes to divisibility in commutative rings, we can say that "$\rm n$ is bigger than $\rm d$" if $\rm d\mid n$ (that is, if there exists some $\rm k\in R$ such that $\rm n=dk$). Given two elements $\rm a,b$ in a ring $\rm R$, we say $\rm d$ is a common divisor if it is a divisor of both, i.e. $\rm d\mid a$ and $\rm d\mid b$. Then we say $\rm c$ is a gcd of $\rm a$ and $\rm b$ if it's uniquely maximal among the set of common divisors - that is, if $\rm c$ is itself a common divisor of $\rm a,b$, and every other common divisor $\rm d$ of $\rm a,b$ divides $\rm c$ as well (i.e. $\rm d\mid a,b\implies d\mid c$).
The gcd is generally only defined up to multiplication by arbitrary unit $\rm u\in R^\times$. In the context of polynomial rings, $\rm K[x]$ where $\rm K$ is a field, of all of the gcds we choose the monic one so that the gcd is a well-defined function (spits out only one output for any set of inputs). In addition, for this setting we have a nice Euclidean algorithm (which is used explicitly below) that makes hand computations feasible, pleasant even.
See the Wikipedia page on polynomial gcds for more information. To summarize the Euclidean algorithm for computing gcds as succinctly as possible, I'd say this: add/subtract multiples of one argument to the other repeatedly in order to simply the expression - in particular, to reduce the degree of the polynomial in one or the other argument at each stage. Notice how in the integer setting the algorithm seeks to reduce the size of the arguments at each stage, whereas in the polynomial setting the algorithm seeks to reduce the degrees. The analogy between the absolute values of integers and degrees of polynomials runs surprisingly deep into number theory.
One useful trick is $\rm \gcd(an,am)=a\gcd(n,m)$. This allows you to reduce the problem via
$$\rm \gcd(f(x),g(x))=(x-2)\gcd(\color{Blue}{x^2+1},\color{Purple}{x^3+7})$$
$$\rm =(x-2)\gcd(\color{Blue}{x^2+1},\color{Purple}{x^3+7}-\color{DarkOrange}{x}(\color{Blue}{x^2+1}))=(x-2)\gcd(\color{Teal}{x^2+1},\color{Purple}{7-x})$$
$$\rm =(x-2)\gcd(\color{Teal}{x^2+1}+\color{Red}{x}(\color{Purple}{7-x}),7-x)=(x-2)\gcd(7x+1,7-x)$$
using the rules $\rm \gcd(\color{Blue}{a},\color{Purple}{b})=\gcd(\color{Blue}{a},\color{Purple}{b}\pm\color{DarkOrange}{n}\color{Blue}{a})$ and $\rm \gcd(\color{Teal}{a},\color{Purple}{b})=\gcd(\color{Teal}{a}\pm \color{Red}{m}\color{Purple}{b},\color{Purple}{b})$ (for arbitrary choices of $\rm \color{DarkOrange}{n},\color{Red}{m}\in K[x]$) repeatedly. Notice the above computation is valid in any field. Specializing to ${\bf F}_2$ aka $GF(2)$ (see here), $\color{Purple}{7}=\color{Purple}{1}$ and $\color{Teal}{2}=\color{Teal}{0}$ and $\color{Blue}{-1}=\color{Blue}{1}$ so the computation may be finished as
$$\rm (x-\color{Teal}{2})\gcd(\color{Purple}{7}x+1,\color{Purple}{7}\color{Blue}{-}x)=x\gcd(x+1,1\color{Blue}{+}x)=x(x+1).$$
A: Hurkyl said:
Res(x2+1,x3+7)=50
which tells us that these two polynomials will be relatively prime (after converting them into polynomials over Fp) iff p is relatively prime to 50.
Could someone point me to a proof of said statement? Obviously for the general case not just this specific one..
