1
$\begingroup$

On the wikipedia article about Primitive Pythagorean Triples, it says:

All prime factors of $c$ are primes of the form $4n + 1$

Where does this come from? Is there a formal proof I can read about this? I'm having trouble understanding why this must be true, so an explanation would be really helpful. Thanks!

$\endgroup$
1
$\begingroup$

It is a theorem that the sum of two relatively prime squares cannot be divisible by a prime of the form $4k+3$.

The result may be more familiar to you as the assertion that $-1$ is not a quadratic residue of such a prime.

To see the connection, suppose $s$ and $t$ are relatively prime, and $s^2+t^2$ is divisible by the prime $p$.

Then $s^2+t^2\equiv 0\pmod{p}$. We cannot have $t$ divisible by $p$, else $s$ would be, contradicting relative primality. Thus $t$ has an inverse $u$ modulo $p$.

Then $u^2(s^2+t^2)\equiv 0\pmod{p}$, which implies that $(us)^2\equiv -1\pmod{p}$.

The congruence $x^2\equiv -1\pmod{p}$ does not have a solution if $p$ is of the form $4k+3$. So $p$ cannot divide $s^2+t^2$ if $s$ and $t$ are relatively prime.

$\endgroup$
  • $\begingroup$ Is there a place I can read about this theorem? Also how are those two results connected? (i.e. how does -1 not being a quadratic residue imply the theorem) $\endgroup$ – bjge_ptrf Apr 6 '13 at 15:42
  • $\begingroup$ I have written out a proof of the implication. The fact that the congruence $x^2\equiv -1\pmod{p}$ is not solvable if $p$ is of the form $4k+3$ is in every beginning number theory book. It is often proved using Wilson's Theorem. Sorry I do not have an explicit online reference, but the proof must be in many such places. It is not long, if you have real trouble finding I will add it. $\endgroup$ – André Nicolas Apr 6 '13 at 16:01
  • $\begingroup$ no, that is very helpful, thanks. i understand perfectly now. $\endgroup$ – bjge_ptrf Apr 6 '13 at 16:06

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.