# Question about prime factors of $c$ in Primitive Pythagorean Triples

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!

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.

• 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) – bjge_ptrf Apr 6 '13 at 15:42
• 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. – André Nicolas Apr 6 '13 at 16:01
• no, that is very helpful, thanks. i understand perfectly now. – bjge_ptrf Apr 6 '13 at 16:06