Prove that $a^2 + 1$ cannot have prime factor of the form $4k + 3$

Question

What I have done: (not sure if it's right)

$a^2 + 1\equiv 1\pmod 4$ or $2\pmod 4$

But if it has two prime factors in the form $4k + 3$, it will be $1\pmod4$, and I don't know where to go from here

Answer 1

If you can use Lagrange's theorem of group theory, this is easy:

• $a^2 \equiv -1 \bmod p$ implies that $a \bmod p$ has order $4$ and so $4$ divides $p-1$.

If you want to avoid Lagrange's theorem, argue as follows:

• $a^2 \equiv -1 \bmod p$ implies $1 \equiv a^{p-1} \equiv (a^2)^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{2}} \bmod p$. Therefore, $\frac{p-1}{2}$ must be even.

Answer 2

If $$a^2\equiv -1 \pmod{p}$$ then $-1$ is a quadratic residue modulo $p$. Thus $$\left( \frac{-1}{p}\right)=1$$

Use the Formula for the Legendre symbol $\left( \frac{-1}{p}\right)$.