# If a prime divides the hypotenuse of a primitive Pythagorean triple, then $p \equiv 1$ (mod 4)

As the title implies.

I'm proving it by contradiction and I've already ruled out $p \equiv 0$ and $2$ (mod $4$).

I'm having trouble proving that it cannot be $\equiv 3$ (mod $4$). Namely, if $p \equiv 3$ (mod 4), then $m^2 + n^2 \equiv 1$ or $3$ (mod $4$). I know that $m^2 + n^2$ cannot be congruent to $3$ (mod $4$); but what about $1$?

Thank you.

-
$m^2+n^2 \equiv 0, 1$ or $2 \pmod 4$, never $3$ For a primitive Pythagorean triple, one of $m,n$ is even and one is odd, so $m^2+n^2 \equiv 1 \pmod 4$ –  Ross Millikan Apr 9 '13 at 23:19
I figured that out. I just can't prove that $m^2 + n^2$ cannot be congruent to $1$ (mod $4$). If I can prove that then $p \not\equiv 3$ (mod $4$), finishing my proof by contradiction. –  Yuxin David Huang Apr 9 '13 at 23:24
But it can, @YuxinDavidHuang! For example, $\,3^2+4^2=5^2=1\pmod 4\,$ , and the triple $\,(3,4,5)\,$ is primitive... –  DonAntonio Apr 9 '13 at 23:33
But $5 \equiv 1$ (mod $4$). What I want to prove is that there are no primes $p \equiv 3$ (mod $4$) such that $p|(m^2+n^2)$. –  Yuxin David Huang Apr 9 '13 at 23:41
The result $n$ is the hypotenuse of a primitive Pythagorean triple iff all its prime factors are of the form $4k+1$ is cited as theorem 3.4 of this paper, referring to page $13$ of Hardy and Wright, 4th ed. Hardy and Wright, 6th ed then send you to section $20.3$ –  Ross Millikan Apr 10 '13 at 0:02

The appropriate proof depends on how much you know. We will use the fact that if $p$ is a prime of the form $4k+3$, then the congruence $x^2\equiv -1\pmod{p}$ does not have a solution.
Now suppose that the prime $p$ divides $s^2+t^2$, where $s$ and $t$ are relatively prime. The prime $p$ cannot divide $s$, else it would divide $t$,
So $s$ has an inverse modulo $p$, say $w$.
We have $s^2+t^2\equiv 0\pmod{p}$. Multiplying by $w^2$, we get that $(ws)^2+(wt)^2\equiv 0\pmod{p}$. Since $ws\equiv 1\pmod p$, it follows that $(wt)^2\equiv -1\pmod{p}$. Since the congruence $x^2\equiv -1\pmod{p}$ does not have a solution if $p$ is of the form $4k+3$, it follows that $p$ cannot be of that form.
Assuming that fact is true, yes. But why is the fact true? I'm thinking this has something to do with the order of a number mod $p \equiv 3$ (mod $4$)? –  Yuxin David Huang Apr 10 '13 at 0:49
Yhere are many proofs. Basically depends in what order one does things. If you approach things group-theoretically, if $p$ is an odd prime then a solution of $x^2\equiv -1\pmod{p}$ has order $4$. But if $p$ is of the form $4k+3$, there is no element of order $4$, since $4$ does not divide the order $p-1$ of the group, –  André Nicolas Apr 10 '13 at 2:05