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$.
 A: 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$.
A: Or, you can write
$$(-5n+4)(3n^2+5n+7)+(15n+13)(n^2+1)=41 \ .$$
A: Hint $\, $ Let $\rm\:d = gcd$, so $\rm\:d\:|\ i^2\!+1,\, 7+5\,i+3\,i^2.\:$ Then, like  taking norms of Gaussian integers, $$\rm\:mod\ d\!:\,\ i^2\equiv -1\ \Rightarrow\ 0\equiv 7+5\,i+3\,i^2\equiv 4+5\,i\ \Rightarrow\ 0\equiv (4+5\,i)(4-5\,i)\equiv 4^2\!+5^2\equiv 41$$
A: Suppose that
$$
(3n^2+5n+7,n^2+1)=(5n+4,n^2+1)\ne1\tag{1}
$$
then either
$$
(5n+4,n+i)=(4-5i,n+i)\ne1\tag{2}
$$
or
$$
(5n+4,n-i)=(4+5i,n-i)\ne1\tag{3}
$$
Since $4-5i$ is a Gaussian prime, $(2)\Rightarrow4-5i\,|\,n+i$. That is,
$$
\frac{n+i}{4-5i}=\frac{(4n-5)+(5n+4)i}{41}\in\mathbb{Z}[i]\tag{4}
$$
which is true if and only if $n\equiv32\pmod{41}$.
Since $4+5i$ is a Gaussian prime, $(3)\Rightarrow4+5i\,|\,n-i$. That is,
$$
\frac{n-i}{4+5i}=\frac{(4n-5)-(5n+4)i}{41}\in\mathbb{Z}[i]\tag{5}
$$
which is true if and only if $n\equiv32\pmod{41}$.
Thus, $(1)$ implies either
$$
(2)\Rightarrow4-5i\,|\,(5n+4,n^2+1)\text{ iff }n\equiv32\pmod{41}\tag{6}
$$
or
$$
(3)\Rightarrow4+5i\,|\,(5n+4,n^2+1)\text{ iff }n\equiv32\pmod{41}\tag{7}
$$
Therefore,
$$
(1)\Rightarrow n\equiv32\pmod{41}\tag{8}
$$
It is easy to verify that
$$
n\equiv32\pmod{41}\Rightarrow41\,|\,(3n^2+5n+7,n^2+1)\tag{9}
$$

Again, $(1)$ implies either
$$
(2)\Rightarrow4-5i\,|\,(3n^2+5n+7,n^2+1)\Rightarrow4+5i\,|\,(3n^2+5n+7,n^2+1)\tag{10}
$$
or
$$
(3)\Rightarrow4+5i\,|\,(3n^2+5n+7,n^2+1)\Rightarrow4-5i\,|\,(3n^2+5n+7,n^2+1)\tag{11}
$$
Therefore,
$$
(1)\Rightarrow41=(4-5i)(4+5i)\,|\,(3n^2+5n+7,n^2+1)\tag{12}
$$
Finally, as Pambos points out, the Euclidean Algorithm yields
$$
(15n+13)(n^2+1)-(5n-4)(3n^2+5n+7)=41\tag{13}
$$
Therefore,
$$
(3n^2+5n+7,n^2+1)\,|\,41\tag{14}
$$
