<s>[INST] GCD of $n^3+3n+1$ and $7n^3+18n^2-n-2$ is always $1$ A problem I found yesterday says to prove $\gcd(n^3+3n+1, 7n^3+18n^2-n-2)=1$ for all integers $n\ge 1$. To begin, I used the Euclidean algorithm to observe that $7n^3+18n^2-n-2=7\left(n^3+3n+1\right)+\left(18n^2-22n-9\right)$, so $$\gcd(n^3+3n+1, 7n^3+18n^2-n-2)=\gcd(n^3+3n+1, 18n^2-22n-9).$$ From here, I got stuck however, since the next step of polynomial division involves rational numbers. I observed that the GCD cannot be a multiple of $3$, since if $3$ divides the term on the right, then $3\mid n$, however, then $3\nmid n^3+3n+1$. Similarly, by a parity argument, both terms are odd. Any suggestions for how to finish the problem from here?
 [/INST] HINT: Because both terms are odd, you know that
$$\gcd(n^3+3n+1,18n^2-22n-9)=\gcd(2(n^3+3n+1),18n^2-22n-9).$$
A similar argument works for the prime $3$, and perhaps for $3^2$. Can you take it from here?
</s>