Let $k,n\in \mathbb Z$ with $n=k^2+1$ and let $p$ be an odd prime with $p\mid n$. Prove that $p\equiv1\text{ mod }4$.
I found out that $\bar{n}\in\left\{ \bar{1},\bar{2}\right\} $ (denoting $r+4\mathbb{Z}$ by $\bar{r}$) but there it stops for me.
Actually I suspect that it can be used as a step in proving that infinitely primes with $p\equiv1\text{ mod }4$ exist, but here I am only interested in the step itself.
Thank you in advance.
On
You can also prove this by passing to $\mathbb{Z}[i]$ as follows :
If $p\mid k^2+1$, then $p$ is composite in $\mathbb{Z}[i]$ :
If $p$ were irreducible in $\mathbb{Z}[i]$, then $p\mid (k+i)(k-i)$, whence $p\mid (k-i)$ or $p\mid (k+i)$ in $\mathbb{Z}[i]$, and so $p\mid \pm 1$ in $\mathbb{Z}$, which is absurd.
Hence, $p$ is composite in $\mathbb{Z}[i]$
If $p$ is composite in $\mathbb{Z}[i]$, then $p =a^2 + b^2$ for some $a,b\in \mathbb{Z}$
If $p = \alpha\cdot \beta$ be a non-trivial decomposition in $\mathbb{Z}[i]$, then with $d(\alpha) = |\alpha |^2$, one has $$ p^2 = d(\alpha)d(\beta) $$ Hence, $d(\alpha) = p$, and so $p = a^2 + b^2$ where $\alpha = a + bi$
If $p$ is composite in $\mathbb{Z}[i]$, then $p \equiv 1\pmod{4}$
If $p = a^2+b^2$, then consider the cases where $a, b$ are even/odd. In each case, you can see that $p$ cannot be $\equiv 3\pmod{4}$.
Modulo $p$ we have $1 \equiv k^{p-1} \equiv (k^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2}$ and hence $p \equiv 1 \pmod 4$.