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

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$.

• You should start by saying that If $a,b$ are any integers then each of $a^2$ and $b^2$ is congruent to one of $0,1,4,7$ modulo $9$. Then the observation about sums of these finishes things. – André Nicolas May 21 '16 at 16:55
• That's what I meant in the first place, forgot to add the squares – George May 21 '16 at 16:56
• @George: It very much seems to me you already have it. What do you mean by "I would need to show the first result". Which result did you not show? – String May 21 '16 at 16:58
• The fact that a square is congruent to one of $\dots$ modulo $9$ is fully proved by squaring all of $0,1,\dots,8$. In fact by symmetry squaring $0$ to $4$ is enough. – André Nicolas May 21 '16 at 16:59
• This question might be useful for you: Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$. – Martin Sleziak May 22 '16 at 8:06

$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$.

$$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.

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$