# 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!

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).$$

• Why this $(x−2)gcd(x^2+1,x^3+7−x(x^2+1))$? How did it come to your mind? – bomba6 Apr 13 '13 at 15:36
• @bomba6 It's the idea behind the Euclidean algorithm, which I edited in a few words about just now. Recall in the integer setting, if you want to compute say $\gcd(100,23)$ using EA, you'd write $100=23\cdot4+8$ via the division algorithm, so that you may write $$\gcd(100,23)=\gcd(100-4\cdot23,23)=\gcd(8,23).$$ Similarly $23=4\cdot8-1$ so $$\gcd(8,23)=\gcd(8,23-4\cdot8)=\gcd(8,-1)=1.$$ In the polynomial setting, to do the same, at each stage ask "what can I multiply one argument by and add/subtract to the other in order to reduce degrees?" – anon Apr 13 '13 at 15:44
• Continuing your example for GF(5), and the fact that 7=4(3), -1=2(3) and 1=-2(3) I get $2(x-2)gcd(x+2,x-2)$, but again, I'm stuck. – bomba6 Apr 13 '13 at 15:54
• @bomba6 If you're going mod 3 then you're talking about GF(3) rather than GF(5). In this case (first of all ignore the 2 out in front; remember we want monic so we can ignore all scalar multiples of the entire expression by invertible elements), note that mod 3 we have -2=1 and 7=1 so $$\rm (x-2)\gcd(7x+1,7-x)=(x+1)\gcd(x+1,2x+1)$$ $$\rm =(x+1)\gcd(x+1,2x+1-(x+1))=(x+1)\gcd(x+1,x)=x+1.$$ – anon Apr 13 '13 at 15:58
• Thanks, I'm going to try that... Lets see were I'm heading. Thanks for your help. (and I meat GF(3) indeed. – bomba6 Apr 13 '13 at 16:02

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!)

• What I'm missing is, probably, the notion that $(x^3+7)=(x-2)(x^2+2x+4)$ in GF(5)... I wonder how to calculate this. Plus- what do you mean calculating the GCD using the Euclidean algorithm? I have used this method go get my "original" $x-2$ answer... (f,g were not factored in the first place). – bomba6 Apr 13 '13 at 15:18
• @bomba6 You don't need to compute such factorizations - see my answer. Please feel welcome to ask questions if anything is not clear. – Math Gems Apr 13 '13 at 15:28
• @bomba6: Then either you made a mistake in the Euclidean algorithm, or more likely you computed the GCD by doing arithmetic in $\mathbb{Q}$ when you should have been doing it with arithmetic in $\mathbf{F}_2$. Did you ever divide by $2$ in your calculation? That's a sure sign that you were doing arithmetic in the wrong field. (because you can't divide by $2$ in $\mathbf{F}_2$... because $2=0$ and you can't divide by $0$) – user14972 Apr 13 '13 at 15:41
• @Hurkyl I need to compute the GCD over GF(p) for all primes < 31. I think I not supposed to run the entire algorithm so many times. – bomba6 Apr 13 '13 at 15:59
• @bomba6: If you don't use my resultant trick, then what you can do is proceed by using only steps that work in every field. Then, when you want to do something special (like divide by $2$), then you can split the problem into two cases: one where you find it in $\mathbf{F}_2$, and one where division by $2$ is allowed. – user14972 Apr 13 '13 at 16:02

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).

• @Math Gems- I am a slow reader. Plus, my reputation is not letting me to vote up. I'm reading, still trying to figure out the best way to do it, without the trick of $(x-2)gcd(...)$ because we haven't learned this way. – bomba6 Apr 13 '13 at 15:34
• @bomba6 You don't know that $\rm\:gcd(ca,cb)\, =\, c\,gcd(a,b)\,?\$ This is the gcd distributive law. $\$ – Math Gems Apr 13 '13 at 15:41
• @bomba6 This answer has three proofs of the gcd distributive law - all of which work also for polynomials over a field. – Math Gems Apr 13 '13 at 15:58
• @MathGems yes, my mistake... haven't noticed that. – bomba6 Apr 13 '13 at 15:59

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..

• This should not be posted as an answer to the initial question. – jvdhooft May 24 '17 at 7:24
• This should be asked as its own question: that way people can find it and benefit from the answer as well. – postmortes May 24 '17 at 7:28
• Yeah realized that after posting. Made a new question for that. Thx for the advice. – Sano Suke May 24 '17 at 12:25