# Seeking elementary proof: For prime $p$ such that $4\mid p -3$, the exponent of $p$ in the prime decomposition of $m^2+n^2$ is even

The theorem I am referring to is the following:

If $$m$$ and $$n$$ are integers, and $$p$$ is a prime number such that $$4 \mid p - 3$$, then the exponent of $$p$$ in the prime decomposition of $$m^2 + n^2$$ is even.

I can prove this using Fermat's Little Theorem (FLT), but I am looking for a more elementary proof.

This is because, in a book on (very) elementary number theory1, the reader is asked to prove this theorem as an exercise, and by this point the book has not covered anything remotely like FLT (or any modular arithmetic, for that matter).

In fact, by this point, this book has only covered the Euclidean algorithm, Bézout's identity, the uniqueness of prime decomposition, and some basic facts about Gaussian integers (including the uniqueness of the prime decomposition of Gaussian integers). The book has also stated, without proof, that an odd prime integer $$p$$ can be expressed as the sum of two squares if and only if $$4 \mid p - 1$$.

For what it's worth, at the point where I would otherwise apply FLT, I have reduced the problem to an equality of the form

$$a^2b = c^2 + d^2$$

...where, $$a$$, $$b$$, $$c$$, and $$d$$ are integers, $$\gcd(c, d) = 1$$, and $$b$$ is square-free, and I must show that no odd prime factor $$p$$ of $$b$$ can satisfy $$4 \mid p - 3$$.

1 Weissman's An illustrated theory of numbers.

• Does the reader know at this point that $x^2 \equiv -1\pmod p$ (or some equivalent without the congruence notation) has no solutions if $4\mid p-3$? If so, the exercise is not difficult. – FredH Mar 23 '19 at 12:52
• A suitable equivalent would be knowing that a prime $p$ such that $4\mid p-3$ remains prime in the Gaussian integers. – FredH Mar 23 '19 at 13:00
• I'd consider the Gaussian prime decomposition of $m+ni$. How do the primes of type (R), (I) and (S) contribute to the (ordinary) prime decomposition of $m^2 + n^2$? Good luck :) – Marty Mar 29 '19 at 5:26

Let $$p$$ be prime with $$p\equiv 3 \mod 4.$$

Consider the non-trivial case $$m\ne 0 \ne n.$$

(1). First we need to know that, for any $$u,v,$$ if $$p|(u^2+v^2)$$ then $$p|u$$ and $$p|v.$$ Equivalently, if $$p$$ does not divide both $$u,v$$ then $$p\not | \;u^2+v^2.$$

(2). Take $$a,b\ge 0$$ and $$m',n'$$ where $$m',n'$$ are not divisible by $$p,$$ and $$m=m'p^a$$ and $$n=n'p^b.$$ WLOG (without loss of generality) $$a\ge b.$$ Then $$m^2+n^2=p^{2b}(m'^2p^{2a-2b}+n'^2)=p^{2b}(\,(m'p^{a-b})^2+n'^2\,).$$ Now $$p\not |\; n'$$ so by (1), $$\;p\not | \;(m'p^{a-b})^2+n'^2.$$ So the largest power of $$p$$ that divides $$m^2+n^2$$ is $$p^{2b}.$$

• counterexample 5 divides $1^2+2^2=5$ but 5 doesn't divide into 1 or 2. – user645636 Mar 23 '19 at 16:03
• OK, I see it now (I think). Thank you. Still, I think you should include a proof of (1), since it's the essence of the theorem. – kjo Mar 23 '19 at 16:21
• can you prove a false thing ? I gave a counterexample, as is $3^2+4^2=5^2$ – user645636 Mar 23 '19 at 16:23
• @RoddyMacPhee: $5 \not \equiv 3 \mod(4)$ – kjo Mar 23 '19 at 16:24
• @kjo . The proposer has accepted my A and there are very likely to be proofs of (1) on this site already so I'm inclined to leave it as is. – DanielWainfleet Mar 28 '19 at 5:08

Here I'll use only some of the results that are listed in the body of the question as being known, with the exception that I make implicit use of the result (surely also known?) that irreducibles in $$\mathbb{Z}[i]$$ are prime.

First, I give two proofs that if $$p \equiv 3 \pmod4$$ then $$p$$ is a prime in $$\mathbb{Z}[i]$$.

This is for no better reason than that I only thought of the shorter proof after writing out the longer one! :(

Both proofs begin with an arbitrary odd prime $$p$$.

The first proof can of course be skipped without loss.

## Stupidly long proof

We know that $$p$$ is a product of primes in $$\mathbb{Z}[i]$$.

If $$\pi$$ is a prime factor of $$p$$ in $$\mathbb{Z}[i]$$, then so is $$\overline{\pi}$$.

If $$\overline{\pi} = \pi$$, i.e., if $$\pi$$ is real, then $$\pi$$ is a factor of $$p$$ in $$\mathbb{Z}$$; but $$\pi \ne 1$$, therefore $$\pi = p$$.

Therefore, either $$p$$ is a prime in $$\mathbb{Z}[i]$$, or else none of the prime factors of $$p$$ in $$\mathbb{Z}[i]$$ are real.

If $$\pi$$ is a non-real factor of $$p$$ in $$\mathbb{Z}[i]$$, then $$\pi$$ and $$\overline{\pi}$$ cannot be associates, because then they would both be associates of $$1 + i$$, and $$p$$ could only be $$2$$, contradicting the postulate that $$p$$ is odd.

Therefore, either $$p$$ is a prime in $$\mathbb{Z}[i]$$, or else $$p$$ is a product of the form: \begin{align*} \pi_1\pi_2\cdots\pi_n\overline{\pi_1}\overline{\pi_2}\cdots\overline{\pi_n} & = \alpha\overline{\alpha} \\ & = a^2 + b^2 \\ & \equiv 0 \text{ or } 1 \pmod4, \end{align*} where $$\alpha = \pi_1\pi_2\cdots\pi_n = a + ib$$.

Therefore, either $$p$$ is a prime in $$\mathbb{Z}[i]$$, or else $$p \equiv 1 \pmod4$$.

That is, if $$p \equiv 3 \pmod4$$, then $$p$$ is a prime in $$\mathbb{Z}[i]$$. $$\square$$

(We have not needed to use the non-trivial result that a prime $$\equiv 1 \pmod4$$ is a sum of two squares.)

## More sensible proof

As usual, denote the norm of a Gaussian integer $$\alpha = a + ib$$ by: $$\operatorname{N}(\alpha) = a^2 + b^2 \equiv 0 \text{ or } 1 \pmod4.$$

If $$p = \alpha\beta$$ in $$\mathbb{Z}[i]$$, and neither $$\alpha$$ nor $$\beta$$ is a unit, then: $$p^2 = \operatorname{N}(p) = \operatorname{N}(\alpha)\operatorname{N}(\beta),$$ where $$\operatorname{N}(\alpha) \ne 1$$, $$\operatorname{N}(\beta) \ne 1$$. Therefore, $$\operatorname{N}(\alpha) = \operatorname{N}(\beta) = p$$. Therefore, $$p \equiv 1 \pmod4$$.

So, if $$p \equiv 3 \pmod4$$, then either $$\alpha$$ nor $$\beta$$ must be a unit. That is, $$p$$ is a prime in $$\mathbb{Z}[i]$$. $$\square$$

(I use the word "prime" in this way because the word "irreducible" is not used in the question.)

## Main result

From now on, we assume that $$p \equiv 3 \pmod4$$.

Given integers $$m$$ and $$n$$, we have: $$m + in = p^r\beta,$$ where $$r$$ is a non-negative integer, and $$\beta$$ is a product of primes $$\ne p$$ in $$\mathbb{Z}[i]$$.

Therefore, $$m - in = p^r\overline{\beta}$$, where $$\overline{\beta}$$ is also a product of primes $$\ne p$$ in $$\mathbb{Z}[i]$$.

Therefore, the exponent of $$p$$ in the prime factorisation of $$m^2 + n^2$$ in $$\mathbb{Z}[i]$$ is $$2r$$.

But if $$m^2 + n^2 = p^{2r}h$$, where $$h = \beta\overline{\beta}$$, we cannot have $$p | h$$ in $$\mathbb{Z}$$, because then either $$p | \beta$$ or $$p | \overline{\beta}$$ in $$\mathbb{Z}[i]$$, contradicting the definition of $$\beta$$.

Therefore, the exponent of $$p$$ in the prime factorisation of $$m^2 + n^2$$ in $$\mathbb{Z}$$ is also $$2r$$. $$\square$$

• I hope I haven't overelaborated this. I'm just starting to revise some basic number theory myself - never having studied the subject systematically - and I'm not at all sure what I know or don't know! Please let me know if the proof can be shortened further (or if it is wrong ...). – Calum Gilhooley Mar 23 '19 at 23:44