Is it possible that $n^2+1$ has some divisor of the form $4k+3$? Given an integer $n$, we are asked to investigate about the existence of integer divisors of $n^2+1$ of the form $4k+3$. Can you provide some insights about it?
 A: If you don't yet know quadratic reciprocity then you can instead use little Fermat. Suppose the prime $\,p = 4k\!+\!3\mid \color{#c00}{n^2\!+1}.\,$ Then $\,p\!-\!1 = 2(2k\!+\!1),\,$ and $\,{\rm mod}\ p\!:\ \color{#c00}{n^2\equiv -1},\,$ so $\,n\not\equiv 0,\,$ so
$${\rm mod}\ p\!:\,\ 1\equiv n^{\large p-1}\equiv (\color{#c00}{n^{\large 2}})^{\large 2k+1}\equiv (\color{#c00}{-1})^{\large 2k+1}\equiv -1$$
Thus $\, 1\equiv -1\,\Rightarrow\,p\mid 2,\,$ contra $\,p = 4k+3\,$ is an odd prime.
A: Assume that $n^2+1$ has some divisor $d$ of the form $4k+3$. 
Then there is some prime $p\mid d$ that is also of the form $4k+3$, and from $p\mid n$ we have:
$$ n^2 + 1 \equiv 0\pmod{p} $$
but that is absurd, since it implies that $-1$ is a quadratic residue $\!\!\pmod{p}$, while the Legendre symbol
$$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = -1 $$
tells us the opposite.
A: $n^2+1$ has no algebraic factorization, (meaninig we cannot conclude any factors of $n^2+1$ just yet) the best way to look at this is to find an odd prime $p$ $=$ $3 \pmod 4$, and find a solution to $n^2$ $=$ $-1$ $\pmod p$, which is false since $-1$ is a quadratic nonresidue to any prime $p$ $=$ $3$ $\pmod 4$, on the other hand if $p$ $=$ $1$ $\pmod 4$, then there is a solution to $n^2$ $=$ $-1$ $\pmod p$, and $p$ divides $n^2+1$.    
