# prime factors of $n^{2}+4$ is congruent to 1 or 5 (mod 8)

prove that the prime factors of $n^{2}+4$ , $n \in \mathbb{N}$ are congruent to $1 \ or \ 5 \ (mod \ 8)$.  I can that the statement holds for n=1,2,3 , so can i use induction principle ? If there is any other way to solve this? Thanks

• Have you heard about quadratic residues? – Seewoo Lee Mar 5 '17 at 11:22
• Odd prime factors, maybe? – Oscar Lanzi Mar 5 '17 at 11:29
• If you seek yo prove it directly, that is a proof that constructs the result for all of them. If it is true for infinite $n$ then you require induction or contradiction. For contradiction it would be like assuming there exists an $n$ such that the premis isnt true or factors not congruent to 1 or 5. Then deducing a contradiction would show that they must at least be congruent to 1 or 5. Just to explain that if it helps. Induction would also work. – marshal craft Mar 5 '17 at 12:10

If $p$ is a prime factor of $n^2+4$ then $n^2\equiv-4\pmod p$, and $-4$ is a quadratic residue modulo $p$. Because $4$ is a square this is equivalent to $-1$ being a quadratic residue modulo $p$. It is well known that this is so if and only if $p\equiv1\pmod4$ (with the obvious exception $p=2$).
Therefore $p$ is congruent to either $1$ or $5$ modulo $8$, or $p=2$.
• In case you have never seen it, the fact that $-1$ being a quadratic residue modulo $p$ implies $p\equiv1\pmod4$ is explained e.g. here. Probably also earlier, that is one of the most often used tricks in elementary number theory. – Jyrki Lahtonen Mar 5 '17 at 11:40