Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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
Actually, I got it. Thanks. – Yuxin David Huang Apr 10 '13 at 1:54
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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