GCD of $n^3+3n+1$ and $7n^3+18n^2-n-2$ is always $1$

Question

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?

Answer 1

It appears the problem fails for $n=309$. WolframAlpha says so here. See discussion on AoPS here on how to find $n=309$.

Answer 2

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?