Let $\mathbb{F}_q[X]$ be the polynomial ring over the finite field with $q$ elements. Let $f$ be a polynomial of the form $x^n-a$ and let $g$ be a polynomial of the form $x^m-b$. Is it known whether $\operatorname{gcd}(f,g)$ is of the same form, i.e. $x^k-c$, for some $k$,$c$? Thanks in advance.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
Here is another, more elementary approach, which works over any field, not just finite fields.
Assume that $n \geq m > 0$, suppose that $a,b \neq 0$, and let $c=b/a$. Then $$\gcd(x^n-a, x^m-b) = \gcd(cx^n-b, x^m-b) = \gcd(x^m-b, cx^n-x^m) \\ = \gcd(x^m-b, x^{n-m}-c^{-1}),$$ and proceed by induction until one of the exponents $n,m$ becomes $0$. The result follows.
answered May 20, 2016 at 15:19
-
2$\begingroup$ Clarify the "proceed by induction until..." part, since the exponents might not ever become $0$. Consider starting with $x^6 - 1$ and $x^9-1$, which have gcd $x^3-1$. More generally, $\gcd(x^m-1,x^n-1) = x^{\gcd(m,n)}-1$. $\endgroup$– KConradCommented May 20, 2016 at 15:29
-
$\begingroup$ Note also that this solution shows it is irrelevant for the coefficients to be in a finite field; any coefficient field works. $\endgroup$– KConradCommented May 20, 2016 at 15:31
-
3$\begingroup$ @KConrad: Isn't your 2nd comment already addressed by the first line in the answer ? $\endgroup$ Commented May 20, 2016 at 15:37
-
2$\begingroup$ @KConrad: The induction goes $\gcd(x^9-1,x^6-1)=\gcd(x^6-1,x^3-1)=\gcd(x^3-1,x^0-1)$ at which point we stop and observe $\gcd(x^3-1,0)=x^3-1$. This is just like the usual Euclid’s algorithm. $\endgroup$ Commented May 20, 2016 at 15:50
-
1$\begingroup$ Sorry, I have skipped a step, but anyway the calculation as indicated in the answer is correct. Your first comment seemed to argue that the answer is incorrect, whereas your last comment only says that alternatives are available, right? Notice that if you stop early with $n=m$, you effectively still have to perform the missing step reducing one of the coefficients to zero, or in other words, you have to find whether the constant coefficients are the same, so that you know whether the polynomials are coprime. Going all the way down to zero just requires less exceptions. $\endgroup$ Commented May 20, 2016 at 17:04
$\begingroup$
$\endgroup$
Represent a monic polynomial $f = \prod_{i=1}^n(x-\xi_i)$ of degree $n$ by the multiset $\{\xi_i\}_{i=1}^n$ of its roots in the algebraic closure of $\mathbb{F}_q$. Also, we can assume that $f$ and $g$ are separable, i.e., that $a$ and $b$ are nonzero and neither $n$ nor $m$ is multiple of $p$ (the characteristic) because otherwise just take $p$-th roots: so these multisets are just sets, and gcd is performed by intersection.
The polynomial $f$ being of the form $x^n-a$ means the multiset consists of the $\zeta^i\alpha$ for some $\alpha$ with $\zeta^i$ ranging over all $n$-th roots of unity. The question is now whether the intersection of two sets $\{\zeta^i\alpha\}$ and $\{\omega^j\beta\}$ of this form is again of this form (or disjoint). If they're not disjoint, we can redefine $\alpha$ and $\beta$ to be an element of their intersection and after dividing by $\alpha=\beta$ we are left to consider the intersection of the sets $\{\zeta^i\}$ of $n$-th roots and $\{\omega^j\}$ of $m$-th roots of unity. But if $\mathop{\mathrm{gcd}}(m,n)=d$ then something which is both an $n$-th root and an $m$-th root of unity is a $d$-th root of unity (writing a Bézout relation $um+vn=d$ if need be) and conversely.
