<s>[INST] Theory number problem I need to prove that there are infinitely many natural numbers $n$ for which $2n^2+3$ and $n^2+n+1$ are relatively prime.
This is not true for every $n$ (for example, $n=4$), I tried to check for odd $n$ but can't find way to prove it (I tried induction). Any ideas?
 [/INST] Any common divisor of $2n^2+3$ and $n^2+n+1$ divides $2(n^2+n+1)-(2n^2+3)$, which is $2n-1$.
Any common divisor of $2n^2+3$ and $2n-1$ divides $2n^2+3-n(2n-1)$, which is $n+3$.
And any common divisor of $2n-1$ and $n+3$ divides $7$.
Now produce infinitely many numbers $2n^2+3$ that are not divisible by $7$. 
Remark: We have in essence used the Euclidean Algorithm for polynomials. If we chase down details, we find that the gcd is $1$ except when $n\equiv 4\pmod{7}$. 
</s>