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

  • 2
    $\begingroup$ Have you heard about quadratic residues? $\endgroup$ – Seewoo Lee Mar 5 '17 at 11:22
  • $\begingroup$ Odd prime factors, maybe? $\endgroup$ – Oscar Lanzi Mar 5 '17 at 11:29
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Mar 5 '17 at 11:40
  • $\begingroup$ correct to match one part of the answer $\endgroup$ – mmath Mar 5 '17 at 11:40
  • $\begingroup$ @mmath: Sorry, what do you mean by part of the answer? I don't think there is anything missing :-) $\endgroup$ – Jyrki Lahtonen Mar 5 '17 at 11:42
  • $\begingroup$ ok, my apologise . everything is there $\endgroup$ – mmath Mar 5 '17 at 11:45
  • 1
    $\begingroup$ Correct, @Student. Sorry about that. I edited the comment (one of the diamond superpowers is the ability to edit old comments). $\endgroup$ – Jyrki Lahtonen Mar 5 '17 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.