Working in $\mathbb Q[x]$. Two polynomials are coprime if their gcd is a constant? When are two polynomials coprime? Is it when their gcd is a constant?
If we divide $x^3-7x-5$ by $x-4$, we get:
$$x^3-7x-5=(x-4)(x^2+4x+9)+31$$
So, is $31$ their gcd, but since $31$ is not monic then we say the gcd is $1$?
Does $1$ count as monic?
 A: The Euclidean algorithm will not always terminate if you are working in a domain which is not a principal ideal domain (PID). You may perform $(a,b)\mapsto (a,b+n)$ or $(a,b)\mapsto(b,a)$ all you want, if the ideal generated by $a$ and $b$ (denoted $(a,b)$ suggestively) is not a principal ideal you will never get it down to the form $(x,x)$ and so you will not find any gcd.
In particular, just performing one operation in the Euclidean algorithm is not enough to say you have found the gcd. Say I perform the Euclidean algo on seven and five: I go $(7,5)\mapsto(2,5)$. Well, I found the remainder when I divide $7$ by $5$ is $2$ so does that mean the gcd is $2$? No. Going further, $(2,5)\mapsto(2,1)$ $\mapsto(1,1)$ and so the gcd is $1$. Let's work on the Euclidean algorithm in your case:


*

*In $\Bbb Z[x]$: start off $(x^3-7x-5,x-4)\mapsto(31,x-4)$. You have not concluded $31$ is a gcd, any more than we had just concluded $2$ is the gcd of $5$ and $7$ a few seconds ago. In fact, $31$ is not a divisor of either polynomial at all, so certainly it can't be a gcd. Instead, the process can't go any further, since there is nothing you can multiply $31$ by and subtract from $x-4$ in order to decrease its degree. And so the Euclidean algorithm will be of no help here.

*In $\Bbb Q[x]$: at the stage $(31,x-4)$ we can continue further: multiply $31$ by $\frac{1}{31}x\in\Bbb Q[x]$ and then subtract from $x-4$ to get $(31,x-4)\mapsto(31,-4)$. Of course now the usual Euclidean algorithm works for integers and you end up with a gcd of $1$. Note $\Bbb Q[x]$ is a Euclidean domain.
We can conclude $1$ is a gcd in both rings with a different kind of reasoning. Since $x-4$ is linear, it is an irreducible in $\Bbb Q[x]$, and since it's also monic it's irreducible in $\Bbb Z[x]$. An irreducible element has a shared nonunit common divisor with another element iff that irreducible element itself divides the other (since the irreducible element is wanting for divisors anyway). Once we see $x-4$ does not divide the cubic polynomial in either $\Bbb Z[x]$ or $\Bbb Q[x]$, we may conclude that $1$ is a gcd of them.
Notice I said a gcd, not the gcd. This is because there is not generally a unique gcd. Let's recall the definition: we say that $d\in R$ is a gcd of $a$ and $b$ if every common divisor of $a$ and $b$ is also a multiple of $d$. Even in the integers, every pair of nonzero integers will have two distinct gcds technically. For instance, consider $5$ and $7$ again. Notice that $-1$ satisfies the property of being a gcd of five and seven: anything that divides both is a multiple of $-1$. (This should be obvious: every integer is a multiple of $-1$.) In $\Bbb Z$ there is always a canonical choice of gcd - you can just pick the nonnegative one. But in more general rings there may not be a canonical choice of gcd. Although if a unit is a gcd we can always canonically pick the equivalent gcd of $1$.
More generally, gcds (when they exist) are only defined up to units. If $d$ is a gcd of $a$ and $b$ and $u$ is any unit, then $ud$ is also a gcd of $a$ and $b$. Do you understand why? Anything $d$ divides, $ud$ divides also, so if $d$ is minimal among all common divisors of $a$ and $b$ (minimal in the order-theoretic sense, ordered by the divisibility relation), then so too us $ud$.
In $\Bbb Q[x]$, since every nonzero rational $r$ is a unit, having a gcd of $r$ is equivalent to having a gcd of $1$; however in $\Bbb Z[x]$ if $n$ is an integer with $|n|>1$ then $n$ is not a unit, and so having $n$ as a gcd is not equivalent to having $1$ as a gcd.
"Coprimality" is another concept that needs some special care. If it means two elements of a ring share no nonunit common divisor, then your two polynomials are coprime regardless of whether you're working in $\Bbb Z[x]$ or $\Bbb Q[x]$. However, if you take it to mean the principal ideals $(a)$ and $(b)$ are coprime, meaning $(a,b)$ is the whole ring, then these two polynomials are coprime in $\Bbb Q[x]$ but not in $\Bbb Z[x]$. In $\Bbb Z[x]$, the ideal they generate, which is $(x-4,31)$, is not the whole ring (for instance $1$ is not in it).
