Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares

Question

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares.

I started by: Assume $n=a^2+b^2$ a sum of two squares. Then $a^2,b^2\equiv 0,1,4,7 \pmod9$, and no combination these numbers can yield $3$ or $6$ so that $a^2+b^2\equiv 3,6 \pmod9$.

But then I would need to show the first result, but I don't know any results (and shouldn't need to apply) results for quadratic residues modulo a composite number. Otherwise, maybe I need to use the result that $n$ is a sum of two squares if $n \not\equiv 3\pmod4$.

Answer 1

$2$ is not a square mod $3$, so the only way for $0 = n = a^2 + b^2$ to be true mod $3$ is if $a,b$ are both $0$.

But then $a^2$ and $b^2$ are both $0$ mod $9$ since $3$ appears as a factor an even number of times. So $n$ must be $0$ mod $9$.

Answer 2

$$x^2 \equiv 0, 1, 4, 7 \pmod 9$$

Thus, sum of two squares can only be $0, 1, 2, 4, 5, 7, 8 \pmod 9$.

Hence, numbers $\equiv 3, 6 \pmod 9$ are not expressible as the sum of 2 squares.

Answer 3

It suffices to show that if $3\mid a^2+b^2$, then $3\mid a$ or $3\mid b$. There is a separate question about this: Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$. (And you might find something also in the questions which are linked there.) Unfortunately, that question is not in a very good state. It was edited, some of the answers address the original version, some of the answers address the current version of the question and some of the answers address a common generalization of both the original and the new version.

For this reason, I will summarize here things which are said in some answers to other posts.

---

Claim 1. If $3\mid a^2+b^2$, then $3\mid a$ and $3\mid b$.

Proof. By contrapositive. Let us assume $3\nmid a$ or $3\nmid b$. If $3\nmid a$, then we have $a^2\equiv 1\pmod 3$. For any $b$ we have $b^2\equiv 0,1\pmod 3$ This implies $a^2\equiv b^2\equiv 1 \pmod 3$. And now we get $$a^2+b^2 \equiv 1,2 \pmod 3$$ which means $3\nmid a^2+b^2$. $\square$

Claim 2. If $n\equiv 3,6 \pmod 9$, then $n$ is not sum of two squares.

Proof. By contradiction. Assume that $n=a^2+b^2$ and $n\equiv 3,6 \pmod 9$. Clearly, this implies $3\mid a^2+b^2$ and by Claim 1 we get $3\mid a$ and $3\mid b$. But this implies $a^2=(3k)^2=9k^2$, i.e. $9\mid a^2$. We get $9\mid b^2$ by the same argument. Together we get $9\mid a^2+b^2$, which means $$a^2+b^2\equiv 0 \pmod 9,$$ a contradiction. $\square$