Show that prime factors of $n^2+1$ are congruent to $1 \bmod 4$
Solution:
I think that if I denote $g$ as a primitive root, I know that the order of $g=p-1$
In other words, since $g^{p-1}\equiv 1\bmod p $ and $p$ is odd, I know that $(p-1)/2$ exists. Now we know that $g^{(p-1)/2} \equiv -1 \bmod p$. So $-1$ will infact be a quadratic residue if $g^{(p-1)/4}$ exists.
Since $(p-1)/4$ can be any number from the set ${1,2,3,...,p-1}$ I can conclude that the number I'm looking for is of the form $p=4k+1$
The product of any primes of the form $4k+1$ is also of the form $4m+1$.
Is this proof correct? It seems to me that I magically land on the $-1$ congruence out of the blue. I think what I'm missing is to use somehow that $n^2+1$ factors always contain $-1$ as a residue or something.
You kinda have the right idea, but explained it badly.
If $p |n^2+1$ you get that $$n^2 \equiv -1 \pmod{p}$$
This shows that $-1$ is a quadratic residue modulo $p$. If you are familiar with Legendre symbol just calculate $\left( \frac{-1}{p} \right )$ otherwise, it is kinda the idea you tried:
Write $n =g^a$ where $g$ is a primitive root and $0 \leq a < p-1$. Then $$n^2=-1$$ implies $$g^{2a} =-1 =g^{\frac{p-1}{2}}$$ implies that $p-1| 2a-\frac{p-1}{2}$. Use this and $0 \leq a < p-1$ to deduce that $2a=\frac{p-1}{2}$.