# Confusion about sum of squares.

First, I want to declare that this problem have been solved by myself, I just want to share my work to everyone.

It has known that a prime has the form $4k+3$ cannot be sum of two squares, and also a composite number of the form $n=N^2m$, where $m$ is a square-free integer, admits a expression of sum of two squares when $m$ didn't have a prime factor of the form $4k+3$.

But then, I found that if two distinct prime $p,q$ both have the form $4k+3$, namely $p=4m+3,q=4n+3$, then their product $pq$ will be of the form $4k+1$, I believe it will have the expression of sum of two squares, but my textbook seems like disagree with it, even if it didn't actually wrote it down.

Therefore, I will prove that if $p,q$ are distinct primes have the form $4k+3$, then their product cannot be expressed as sum of two squares.

• The correct criterion is : A positive integer can be expressed as a sum of at most two squares, if and only if every exponent in the prime decomposition belonging to a prime of the form $4k+3$ is even. – Peter Apr 28 '18 at 7:55

Let $p=4m+3,q=4n+3,pq=16mn+12m+12n+9=4k+1$, and assume that $pq=a^2+b^2$ for some positive integers $a,b$, so

$$a^2+b^2\equiv 0 \pmod {pq}$$

If $p|a$ will leads to $p|b$, by letting $a=pr,b=ps$ will leads to $p^2(r^2+s^2)=pq$ which says $p|q$, contradiction. Thus, $p\nmid a$, same as $b$.

but this indicates that

$$\begin{cases}a^2+b^2\equiv0\pmod p\quad(1)\\\\a^2+b^2\equiv0 \pmod q\quad(2)\end{cases}$$

For equation $(1)$, because $\gcd(a,p)=1$, so there exist an integer $a_1$ which $$a_1a\equiv1\pmod p$$ By multiple $a_1^2$ on the equation $(1)$, we get $$(ba_1)^2\equiv-1 \pmod p$$ which can't occur because $p\equiv3 \pmod4$. Same as the equation $(2)$.

Therefore, $pq$ can't be sum of two squares.

This completes the proof.

• Your idea is basically correct, but exactly what justifies the assertion "which can't occur because $p\equiv3$ (mod $4$)" if all you know is that such a $p$ cannot be written as the sum of two squares? – Barry Cipra Apr 27 '18 at 13:05
• @BarryCipra I thought about it, but $a^2+b^2$ is equal to $pq$, not $p$, so I think the assertion is required because it didn't mean that $a^2+b^2=p$. – kelvin hong 方 Apr 27 '18 at 13:15
• Yes, the assertion is required. What I'm asking you is what justifies it. That is, how do you know that $-1$ is not a quadratic residue mod $p$ if $p\equiv3$ mod $4$? – Barry Cipra Apr 27 '18 at 13:24
• Should I need to add details to it? Because at this stage, one must know that $-1$ is not a quadratic residue of prime of the form $4k+3$. – kelvin hong 方 Apr 28 '18 at 2:52