Gcd of polynomials over a finite field 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.
 A: 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.
A: 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.
