Supongamos que $$ (3n^2+5n+7,n^2+1)=(5n+4,n^2+1)\ne1\tag{1} $$ entonces $$ (5n+4,n+i)=(4-5i,n+i)\ne1\tag{2} $$ o $$ (5n+4,n-i)=(4+5i,n-i)\ne1\tag{3} $$ Desde $4-5i$ es un primo gaussiano, $(2)\Rightarrow4-5i\,|\,n+i$ . Es decir, $$ \frac{n+i}{4-5i}=\frac{(4n-5)+(5n+4)i}{41}\in\mathbb{Z}[i]\tag{4} $$ que es verdadera si y sólo si $n\equiv32\pmod{41}$ .
Desde $4+5i$ es un primo gaussiano, $(3)\Rightarrow4+5i\,|\,n-i$ . Es decir, $$ \frac{n-i}{4+5i}=\frac{(4n-5)-(5n+4)i}{41}\in\mathbb{Z}[i]\tag{5} $$ que es verdadera si y sólo si $n\equiv32\pmod{41}$ .
Así, $(1)$ implica $$ (2)\Rightarrow4-5i\,|\,(5n+4,n^2+1)\text{ iff }n\equiv32\pmod{41}\tag{6} $$ o $$ (3)\Rightarrow4+5i\,|\,(5n+4,n^2+1)\text{ iff }n\equiv32\pmod{41}\tag{7} $$ Por lo tanto, $$ (1)\Rightarrow n\equiv32\pmod{41}\tag{8} $$ Es fácil comprobar que $$ n\equiv32\pmod{41}\Rightarrow41\,|\,(3n^2+5n+7,n^2+1)\tag{9} $$
Otra vez, $(1)$ implica $$ (2)\Rightarrow4-5i\,|\,(3n^2+5n+7,n^2+1)\Rightarrow4+5i\,|\,(3n^2+5n+7,n^2+1)\tag{10} $$ o $$ (3)\Rightarrow4+5i\,|\,(3n^2+5n+7,n^2+1)\Rightarrow4-5i\,|\,(3n^2+5n+7,n^2+1)\tag{11} $$ Por lo tanto, $$ (1)\Rightarrow41=(4-5i)(4+5i)\,|\,(3n^2+5n+7,n^2+1)\tag{12} $$ Por último, como señala Pambos, el Algoritmo Euclidiano da como resultado $$ (15n+13)(n^2+1)-(5n-4)(3n^2+5n+7)=41\tag{13} $$ Por lo tanto, $$ (3n^2+5n+7,n^2+1)\,|\,41\tag{14} $$