Let $f, g \in \mathbb{Z}[x]$. Let also $h \in \mathbb{Q}[x]$ be the $\gcd(f,g)$ found by the Euclidean algorithm. Now, for $p$ an odd prime, let $h^* \in \mathbb{Z}/p\mathbb{Z}[x]$ be the $\gcd(f,g)$ found by the Euclidean algorithm in $\mathbb{Z}/p\mathbb{Z}[x]$. Now, define $\phi: \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}$ by mapping each residue to the closest integer to zero with that remainder.
Can we always find such a $p$ and some $c_1 \in \mathbb{Z}, c_2 \in \mathbb{Z}/p\mathbb{Z}$ such that $c_1h = \phi(c_2h^*)$? In other words, can we find the $\gcd(f, g)$ in $\mathbb{Z}[x]$ by finding it in $\mathbb{Z}/p\mathbb{Z}[x]$?
Here's what I was thinking. If we work in $\mathbb{Q}_p$ (the $p$-adic numbers), then $h$ would divide the $\gcd(f,g)$ in $\mathbb{Q}_p[x]$ (since $h$ still divides both $f$ and $g$ in that field). Now if $\gcd(f,g) \in \mathbb{Q}_p[x]$ has the same degree as $h$ (this is the crux of the problem), then it's just $ch$ for some $c \in \mathbb{Q}_p$, so it can be rescaled to lie in $\mathbb{Z}[x] \subset \mathbb{Z}_p[x]$. Then, in order to find $\gcd(f,g)$ in $\mathbb{Z}_p[x]$, we could find it in $\mathbb{Z}/p\mathbb{Z}[x]$ and raise it to $\mathbb{Z}_p[x]$ using Hensel's lemma (since there exists a linear combination of $f/h$ and $g/h$ coprime to $h$). But since that $\gcd$ can be rescaled to lie in $\mathbb{Z}[x]$, we can rescale it in $\mathbb{Z}/p\mathbb{Z}[x]$ (simply dividing by the leading coefficient and then multiplying by the $\gcd$ of the leading coefficients of $f$ and $g$ should work, thanks to Gauss' lemma), and if $p$ is sufficiently large (larger than twice the largest coefficient of the factors of $f$ in $\mathbb{Z}[x]$), then we can just take the (signed) coefficients of the scaled $gcd$ in $\mathbb{Z}/p\mathbb{Z}[x]$ as coefficients in $\mathbb{Z}[x]$. Now, assuming this line of reasoning holds, I still don't know how to choose $p$ such that the $\gcd$ in $\mathbb{Q}_p[x]$ has the same degree as $h$, while also having $p$ be large enough (finding the bounds on the coefficients of factors of $f$ is fairly easy, but I don't know if we can satisfy the other condition with an arbitrarily large p).
UPD: Changed the reasoning a little, so now it's reduced to a smaller question. Would appreciate if someone could check if the reasoning is solid, if so then the problem basically becomes "when does $\gcd(f,g)$ in $\mathbb{Q}_p[x]$ has the same degree as in $\mathbb{Q}[x]$?".
UPD 2: It just dawned on me that the Euclidean algorithm will produce the same $\gcd$ in $\mathbb{Q}_p[x]$ as in $\mathbb{Q}[x]$. So, basically, if my earlier reasoning is correct, this should work for any sufficiently large $p$?
After a little more thinking, I've managed to prove that such a prime does exist, without even relying on $p$-adic numbers.
Let $f, g$ be nonzero primitive in $\mathbb{Z}[x]$. Let $\gcd_\mathbb{Z}(g, f)$ be the unique primitive polynomial $h \in \mathbb{Z}[x]$ that can be obtained by scaling the result of the Euclidean algorithm in $\mathbb{Q}[x]$. By Bezout's lemma, there exist $s,t \in \mathbb{Q}[x]$ s.t. $h=sf+tg$. We can rescale them by $c \in \mathbb{Z}$ so that $cs,ct \in \mathbb{Z}[x]$.
Let $p$ be a prime and $f_p,g_p,h_p,s_p,t_p$ are $f,g,h,cs,ct \mod p$. Then, we have $s_pf_p+t_pg_p = ch_p = h*$. So, $\deg(h*) \leq \deg(h)$ $(1)$, and since $h*$ is a $\mathbb{Z}/p\mathbb{Z}[x]$-linear combination of $f_p$ and $g_p$, $\gcd(f_p, g_p) \mid h*$. If $h*=0$, we have $p \mid c$ ($p \mid h$ can't happen since $h$ is primitive) which only happens for finitely many $p$. Otherwise, $\deg(\gcd(f_p, g_p)) \leq \deg(h*)$ $(2)$. But since $h$ divides $f$ and $g$, $h_p$ divides $f_p$ and $g_p$, so $h_p$ divides $\gcd(f_p, g_p) \neq 0$ (since if $f_p=0$ we have either $f=0$ or $p \mid f \implies f$ nonprimitive, and same for $g_p=0$ and $g$) and hence $\deg(h_p) \leq \deg(\gcd(f_p, g_p))$ $(3)$. Finally, if $p$ is coprime to the leading coefficient of $h$, then $\deg(h_p)=\deg(h)$, and combining this with $(1),(2),(3)$ we get $\deg(h)=\deg(h_p) \leq \deg(\gcd(f_p, g_p)) \leq \deg(h*) \leq \deg(h)$, so all inequalities become equalities. In particular, $\deg(h_p) = \deg(\gcd(f_p, g_p))$ and so $h_p = a\gcd(f_p, g_p)$ for some $a \in \mathbb{Z}/p\mathbb{Z}$. If $p$ is large enough (larger than $2H(h)$ wher $H$ is the highest coefficient in absolute value), we can recover $h$ from $h_p$ by taking each residue to the closest to zero integer with that residue. We can even find the scaling factor if we take $p$ larger than $2mH(h)$ where $m$ is the $\gcd$ of the leading coefficients of $f$ and $g$. We do so by scaling $\gcd(f_p, g_p)$ down to a monic polynomial, then multiplying by $m$, reading off the (signed) coefficients as if they were in $\mathbb{Z}$ and factoring out the content.
There is still a problem if $h* = 0$, but for large $p$, the probability that $p \mid c$ is vanishingly small (and, as mentioned earlier, it only happens for finitely many $p$). Still, we could check if the $\gcd$ that we get from finding it in $\mathbb{Z}/p\mathbb{Z}$ actually divides $f$ and $g$ (if it does, we still have $\deg(\gcd(f_p, g_p)) \leq \deg(h)$ and the rest of the proof follows), and if it doesn't we just try a different $p$. Still, if there was some way to choose $p$ s.t. $p \nmid c$, that would make this algorithm more elegant.