Let $p$ be a prime so $p\equiv3\pmod4$. If $p|a^2+b^2$, then $p|a,b$

Let $p$ be a prime so $p\equiv3\pmod4$. If $p| a^2+b^2$, then $p| a,b$

How do I prove this small theorem? I know that it's quite useful. Are there other small theorems like this one? I am mostly searching elementary proofs, so not involving to complicated stuff...

• This isn't small. :-)
– S. Y
Sep 16, 2016 at 18:51
• Well it isn't recognised as a theorem? Or is it? Sep 16, 2016 at 18:52
• It is a theorem. I will provide a proof later if nobody else does
– S. Y
Sep 16, 2016 at 18:55
• Ok Thanks... In french, (I am french ;)) we have something that is called "lemme"... I don't know if that exists in English or something similar, but this one is recognised as a "lemme"... Sep 16, 2016 at 18:57
• Ohhh... Well I learned something today at least :D Sep 16, 2016 at 19:09

I hope I didn't miss something and I think it is pretty elementar:

Using Fermats Little Theorem: $a^p\equiv a\mod{(p)}$ and $b^p\equiv b\mod{(p)}$. Now we get that $a^{p+1}+b^{p+1}\equiv a^2+b^2 \equiv 0 \mod{(p)}$. Because $4\mid p+1$ we can write $p+1=4k$ , for some $k\in\mathbb{N}$. Now we get: $0\equiv a^{4k}+b^{4k}\equiv a^{4k}+(-a^2)^{2k}\equiv a^{4k}+a^{4k}\equiv 2a^{4k} \mod{(p)}$. So now that means $p$ divides $2a^{4k}$, but bcs $p>2$ it cant divide the 2 so it has to divide $a^{4k}$, and if it is a factor of it, it has to be also a factor of $a$, in other words $p\mid a\Rightarrow p\mid b$.

The ring $\mathbf Z[i]$ is a principal ideal domain, and any prime that is 3 modulo 4 is inert in this ring. Indeed, writing $p = (a+bi)(a-bi) = a^2 + b^2$ and looking at this modulo 4, we find that $p$ cannot be $3$ modulo $4$. Now, assume that $p$ divides $a^2 + b^2 = (a+bi)(a-bi)$, then $p$ divides one of the factors on the right hand side. Hence, $p$ divides both $a$ and $b$.

Another approach: if we have $a^2 + b^2 \equiv 0 \pmod{p}$ with $a, b \neq 0$, then $(a/b)^2 \equiv -1 \pmod{p}$, so $a/b$ has order $4$ in the group $(\mathbf Z/p \mathbf Z)^{\times}$, which has order $p - 1$. This is not divisible by $4$ as $p \equiv 3 \pmod{4}$, contradicting Lagrange's theorem.

• Is there a possibility to prove it without rings and complex numbers? I am searching an elementary proof that is not to complicated... Sep 16, 2016 at 19:00
• But it is a nice proof ;) Sep 16, 2016 at 19:00
• @DanielCortild your theorem means same as if $(a+bi)(a-bi) \cong 0 \mod p$ then $a+bi \cong 0 \mod p$ or $a-bi \cong 0 \mod p$. It's equivalent to Z[i] being a UFD for the special case of primes in Z[i] that are in Z. So there may not be a simpler proof since the algebra of Z[i] really is involved here. Sep 16, 2016 at 19:03
• Ohhh... Ok I will take the time later to sit down and really try to understand it all... But thanks Sep 16, 2016 at 19:05
• I added another, arguably more elementary proof. Sep 16, 2016 at 19:05

Your assertion can be restated in terms of the quadratic form $$q(x,y) = x^2+y^2$$ defined over the finite field $$\mathbb{F}_p$$ of order $$p$$ (for a prime number $$p$$): if $$p \equiv 3 \pmod{4}$$ then for all $$(x,y) \in \mathbb{F}^2$$, if $$q(x,y) = 0$$ then $$x = y= 0$$.

You ask for a generalization, so here is a (useful) one: let $$F$$ be any field of characteristic different from $$2$$. For $$a,b,c \in F$$ consider the binary quadratic form

$$q(x,y) = ax^2 + bxy + cy^2$$.

We say that $$q$$ is isotropic if there is $$(x,y) \in F^2 \setminus (0,0)$$ such that $$q(x,y) = 0$$ and otherwise anisotropic. And here we go:

(Small but Useful) Theorem: The binary form $$q(x,y) = ax^2 + bxy + c y^2$$ is isotropic over $$F$$ if and only if its discriminant $$\Delta = b^2-4ac$$ is a square in $$F$$ (meaning $$\Delta = d^2$$ for some $$d \in F$$).

Let me sketch the proof: feel free to ask if you want details. Since the characteristic is not $$2$$, we can diagonalize $$q$$ just by "completing the square". Moreover, replacing $$q$$ by $$(1/a)*q$$ changes the discriminant from $$\Delta$$ to $$\frac{\Delta}{a^2}$$ -- so does not affect whether it is a square. So we reduce to the case

$$q'(x,y) = x^2 - \frac{\Delta}{4} y^2$$, where the result is pretty clear: if $$x,y \in F$$ are not both $$0$$ and $$q'(x,y) = 0$$, then $$x \neq 0$$ and $$y \neq 0$$ and $$\Delta = (2x/y)^2$$. Conversely, if $$\Delta = d^2$$ then $$q'(d/2,1) = 0$$.

For the form $$q(x,y) = x^2 + y^2$$, the discriminant is $$-4$$, which is a square in $$F$$ iff $$-1$$ is a square in $$F$$. By (very) elementary number theory, when $$F = \mathbb{F}_p$$ for an odd prime $$p$$, we have that $$-1$$ is a square iff $$p \equiv 1 \pmod{4}$$.

To see why this is useful, now let $$a,b,c \in \mathbb{Z}$$ and consider the binary quadratic form $$q(x,y) = ax^2 + bxy + cy^2$$, of discriminant $$\Delta$$, and suppose that for a prime number $$p$$ not dividing $$\Delta$$ we have

$$q(x,y) = p$$. Then $$x$$ and $$y$$ are not both divisible by $$p$$: if $$x = pX$$, $$y = pY$$, then $$q(x,y) = p^2 q(X,Y) = p$$ is a contradiction. So we find that (the reduction modulo $$p$$ of) $$q(x,y)$$ is isotropic over $$\mathbb{F}_p$$ and thus that $$\Delta$$ is a square modulo $$p$$. Using quadratic reciprocity, this translates in every case to congruence conditions on $$p$$ modulo $$\Delta$$.

This is really the first step of the arithmetic study of binary quadratic forms over $$\mathbb{Z}$$. See for instance this lovely book of Cox and these notes based on the book, in particular the first handout. In the latter reference, I call this fact the "fundamental congruence": it appears (in the special case $$x^2 + ny^2$$) on the very first page of the notes.

Notice $$\frac{p-1}{2}= 2k+1$$ is an odd integer. Let $$p|a^2+b^2$$. If $$p\not | a$$ and $$p \not| b$$, we must have (by raising to the $$\frac{p—1}{2}$$ power and using Fermat's little theorem):

$$a^2 \equiv -b^2\Rightarrow a^{p-1} \equiv -b^{p-1} \Rightarrow 1 \equiv -1 \mod{p}$$

This is absurd as $$p\not=2$$. Therefore it must be $$p$$ divides one of them. Say $$p|a$$. But then $$p|b$$.