# Prove for $n = a^2+b^2$ with $n=2^{e}p_{1}p_{2}...p_rM^2$ (where $p_1, p_2, ...p_r$ are distinct odd primes, e = 0 or 1), then $p_i=1 mod 4$.

Prove for an integer $$n = a^2+b^2$$ with prime factorization $$n=2^{e}p_{1}p_{2}...p_rM^2$$ (where $$p_1, p_2, ...p_r$$ are distinct odd primes and e = 0 or 1), then $$p_i=1 mod 4$$ for all i. My first thought is to use quadratic reciprocity but other than that i cannot think of anything else. Any hints?

• This might be helpful. en.wikipedia.org/wiki/… Commented Jun 9, 2020 at 5:58
• @dust05 thx! But here n is not a prime though. Any further hints? Commented Jun 9, 2020 at 6:00
• Maybe here math.uga.edu/~pete/4400twosquares.pdf. Pag. 4-5 Commented Jun 9, 2020 at 6:07
• The main point is that $p_is$ can be written as a sum of two squares. Moreover stuff like $(a^2+b^2)(c^2+d^2)$ can also be written as sum of two squares Commented Jun 9, 2020 at 6:10
• Remember of course that for $e=1$, then $2=1^2+1^2$ Commented Jun 9, 2020 at 6:27

You have $$n\equiv 0\mod p_i$$. So, $$a^2+b^2\equiv 0\mod p_i$$.

If $$b$$ is invertible mod $$p_i$$: This implies that $$-1=(ab^{-1})^2\mod p_i$$, i.e. $$-1$$ is quadratic residue mod $$p_i$$. This only happens when $$p_i\equiv 1\mod 4$$.

If $$b$$ is divisible by $$p_i$$: Then $$a$$ is also divisible by $$p_i$$. So, $$(a')^2+(b')^2=n'$$, where $$a'=a/p_i$$, $$b'=b/p_i$$ and $$n'=n/p_i^2$$. Note that $$n'\equiv 0\mod p_i$$, so you can repeat the same argument.

If you know some modern algebra, one can see this via:

Lemma. If $$p \mid a^2 + b^2$$ and $$p \equiv 3 \pmod4$$ then $$p \mid a, b$$ in $$\mathbb{Z}[i]$$.

Proof. Since $$p \mid a^2 + b^2 = (a+bi)(a-bi)$$ and $$p$$ is prime in $$\mathbb{Z}[i]$$. (If $$p$$ is not prime then $$p = \epsilon (A+Bi)(A-Bi)$$ form for $$A, B \in \mathbb{Z}$$ and $$\epsilon = \pm1, \pm i$$, which leads us to $$p = A^2 + B^2$$ ) So $$p \mid a+bi$$ or $$p \mid (a-bi)$$, and either cases give the conclusion.

With the lemma one have $$p^2 \mid a^2 + b^2$$ for $$p$$ prime factor of sum of two squares and of the form $$4k+3$$, which was what we wanted.