# 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 '16 at 18:51
• Well it isn't recognised as a theorem? Or is it? – Taumen Sep 16 '16 at 18:52
• It is a theorem. I will provide a proof later if nobody else does – S. Y Sep 16 '16 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"... – Taumen Sep 16 '16 at 18:57
• Lemme is Lemma in English and German. It comes from the greek word $\lambda\eta\mu\mu\alpha$. – Dietrich Burde Sep 16 '16 at 19:01

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... – Taumen Sep 16 '16 at 19:00
• But it is a nice proof ;) – Taumen Sep 16 '16 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. – djechlin Sep 16 '16 at 19:03
• Ohhh... Ok I will take the time later to sit down and really try to understand it all... But thanks – Taumen Sep 16 '16 at 19:05
• I added another, arguably more elementary proof. – Ege Erdil Sep 16 '16 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.