Let $f \in \mathbb{Z}[x]$.
Is it true that $\deg(\gcd_{\mathbb{Z}_q}(f, x^p - 1)) \geq \deg(\gcd_{\mathbb{Q}}(f, x^p - 1))$? Where $\mathbb{Z}_q = \mathbb{Z}/ q\mathbb{Z}$ for $q$ some prime?
I'm not able to connect the gcd over the rationals to that in $\mathbb{Z}_q$, since I have no information about what the coefficients are. Furher, any division I do in the rationals may end up containing fractions with base $q$ so not seeing a way to divide in the finite field.
Thanks for the help,
Let $d ∈ ℚ[X]$ be a greatest common divisor of two polynomials $f$ and $g$ in $ℚ[X]$. Without loss of generality, you may assume that $d ∈ ℤ[X]$ is primitive. Gauß’s lemma (or some version of it) implies that $d$ then divides already both $f$ and $g$ in $ℤ[X]$. Hence, its residue $[d]_{qℤ}$ in $ℤ_q[X]$ divides both their residues $[f]_{qℤ}$ and $[g]_{qℤ}$ in $ℤ_q[X]$.
Hence, $[d]_{qℤ}$ divides the greatest common divisor of $[f]_{qℤ}$ and $[g]_{qℤ}$ in $ℤ_q[X]$ and thereby is of no greater degree than this greatest common divisor.
Now, if $g$ is monic, $d$ must be monic, too. Since $g = X^p - 1$ is monic, $d$ is monic. So $\deg d = \deg [d]_{qℤ}$. With the above, this implies the assertion.