<s>[INST] How to eliminate these extra solutions? (finding the gcd of two expressions) 
Prove that for any integer $n$, $\gcd (3n^2+5n+7, n^2+1)=1$ or $41$.

The following answer is convoluted because I've intentionally created excess solutions. However, I can't figure out how to eliminate them! Anyone?
Let $$d=\gcd (3n^2+5n+7, n^2+1).$$
Then $$d|[(3n^2+5n+7)-3(n^2+1)]$$
$$d |(5n+4)$$
And
$$d | [5(3n^2+5n+7)-3n(5n+4)]$$
$$d |(13n+35)$$
And
$$d |[5(13n+35)-13(5n+4)]$$
$$d |123$$
Therefore, $d= 1$ or $3$ or $41$ or $123$.
 [/INST] From your last step, we get that $d = 1,3,41,123$.
Recall that $$n^2 \equiv 0,1 \pmod{3} \text{      (Why?)}$$ Hence, $3$ (or) $123$ does not divide $n^2+1$.
EDIT
Note that any $n$ is either $0 \pmod{3}$ or $\pm1 \pmod{3}$.
Hence, $n^2 \equiv 0,1 \pmod{3}$. (Recall that if $x \equiv y \pmod{a}$, then $x^k \equiv y^k \pmod{a}$.)
Hence, $n^2 + 1 \equiv 1,2 \pmod{3}$. This means that $3$ does not divide $n^2+1$. Hence, $3$ cannot divide any divisor of $n^2+1$. This enables us to rule  out $d=3$ and $d=123$.
</s>