# Proof that squares are divisible by 3 when their sum is

In this proof, they write $3|a^2+b^2 \implies 3|a$, $3|b$. I tried using the same proof used to prove $3|a^2 \implies 3|a$, where $3$ being prime and writing $a^2 = a\cdot a$ suggests that $a$ is divisible by $3$. I'm not sure how to prove the $3|a^2+b^2$ case, though.

E9. There is no quadruple of positive integers $(x, y, z, u)$ satisfying $$x^2 + y^2 = 3(z^2 + u^2).$$

Solution. Suppose there is such a quadruple. We choose the solution with the smallest $x^2 + y^2$. Let $(a, b, c, d)$ be the chosen solution. Then $$a^2 + b^2 = 3(c^2 + d^2) \implies 3|a^2 + b^2 \implies 3|a, 3|b \implies a = 3a_1, b = 3b_1,\\a^2 + b^2 = 9(a^2_1 + b^2_1) = 3(c^2 + d^2) \implies c^2 + d^2 = 3(a^2_1 + b^2_1).$$

We have found a new solution $(c, d, a_1, b_1)$ with $c^2 + d^2 \lt a^2 + b^2$. Contradiction.

We have used the fact that $3|a^2 + b^2 \implies 3|a, 3|b$. Show this yourself. We will return to similar examples when treating infinite descent.

## 3 Answers

For a number $n$ we have

$n\equiv 0,1,2 \mod 3$ so we get $$n^2\equiv 0,1\mod 3$$ For $$a^2+b^2$$ we have

$$a^2+b^2\equiv 0 \mod 3$$ The only possibility is $$a^2=b^2\equiv 0 \mod 3$$

• Since we could verify that the only possibility was for $a^2=b^2=0$ by checking each case, as the other user did below, am I correct in assuming that there exists different, and might I say cleaner methods, for proving the general case $n|a^2+b^2$ ? – john fowles Jun 27 '18 at 11:52
• @johnfowles The general case doesn't hold. Take $n=2$, $a=1$, $b=1$. A potentially interesting question is for which $n$ it holds. – Solomonoff's Secret Jun 27 '18 at 13:01
• @Solomonoff'sSecret Ya, I tried to edit my answer because that's not what I meant but it was too late. What I meant to say was for those $n$ that satisfy the condition, is there a more efficient method of proving those cases. Or how could we determine those $n$ that would satisfy the relation? – john fowles Jun 27 '18 at 13:06
• @johnfowles The very general question you hint at in your last comment is old and famous and well studied. It's been answered, but the answer is reasonably complex. See en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares , proofwiki.org/wiki/Integer_as_Sum_of_Two_Squares – Ethan Bolker Jun 27 '18 at 13:53

It probably isn't the best solution, but you could try using congruence.

Since 3 is a pretty small number, you can test each case for

$$a,b\equiv 0,1,2\pmod 3$$

And for each one check if

$$a² + b² \equiv 0 \pmod 3$$

It gives you (all results given modulo 3):

$$\begin{matrix} a & b & a^2+b² \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 2 \\ 1 & 2 & 2 \\ 2 & 0 & 1 \\ 2 & 1 & 2 \\ 2 & 2 & 2 \\ \end{matrix}$$

As you can see:

$$a² + b² \equiv 0 \pmod 3$$ iff $$a \equiv 0\pmod 3 \land b\equiv 0\pmod 3$$

In $\mathbb{Z}/3$, $a^2=1$, or $a^2=0$, $b^2=1$ or $0$ implies that $a^2+b^2=0$ if and only if $a^2=b^2=0$.