# Prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$.

For elements $a$ and $b$ in the ring $\Bbb{Z}$ prove that if $3\mid a^2+b^2$ then $3\mid a$ and $3\mid b$.

I tried proving it but I just don't manage to. Maybe I am missing some basic claims in the number Theory?

I would appreciate hints and, generally, your help.

I am sorry, there was another data I was given, I was fixed and resent to me.

The original question was to prove that $c\mid a^2+b^2$ implies $c\mid a$ and $c\mid b$, which as many answers show isn't true.

But this is true if you take the assumption that there isn't a square root of $-1$ mod $c$. Take mod $c$ of the equation to get that

$$a^2 = - b^2 \mod c$$

which can only have a solution $a \neq 0$ or $b \neq 0$ if $-1$ has a square root mod $c$. I.e., there is a number $x$ such that $x^2 = -1 \mod c$.

Indeed, assuming $a$ and $b$ are both relatively prime to $c$, then we can take $b^{-1}$ to get

$$(b^{-1}a)^2 = -1 \mod c.$$

But if no solution exists, our assumption of co-primality cannot hold. If we take the prime factors of $c$ and use modular arithmetic, then we can show $\gcd(a,p) \geq p$ for each prime factor. (Note that $x^2=-1 \mod p$ has a solution if it does mod $c$.) Now this only means $\prod p_i$ divides $a$ and $b$, but if we cancel out these common factors we should be able to repeat the procedure to get full divisibility.

Seeing your edit, the solution follows from my answer by showing mod $3$ that no solution $x^2=-1$ exists. It's a simpler case since $3$ is prime. Sorry I didn't make the above argument tighter, but you should be able to work out the specific (and easier) case from the above.

It's not hard to see the general claim is if and only if as well.

• What a thorough approach. Thank you. Mar 13, 2015 at 22:36
• @Meitar The original claim it true for all primes of form $\, p = 4k+3,\,$ see my answer. Mar 13, 2015 at 23:01

This is not true. Take, for example, $a=3$, $b=4$ and $c=5$.

• I wonder why my teacher gave it... :< That's why I just wouldn't solve it Mar 13, 2015 at 22:18
• ...and why you should do some sanity checks early on. They can help you with the proof either way. Mar 13, 2015 at 22:20
• I am so sorry. I misread the date. Mar 13, 2015 at 22:27

That's not true. Take $a=3$, $b=4$ and $c=5$.

• You are correct. I got the data wrong. I am deeply sorry. Mar 13, 2015 at 22:26

To answer your original question: if prime $\,\color{#c00}{p = 4k\!+\!3}\,$ then $\,p\mid a^2+b^2\,\Rightarrow\, p\mid a,b.$

Proof $\$ If not, wlog $\,p\nmid b,\,$ so $\, {\rm mod}\ p\!:\ b^{-1}$ exists so $\ {-}b^2\equiv a^2\,\Rightarrow\, -1 \equiv (ab^{-1})^2\equiv c^2$

therefore $\ {\rm mod}\ p\!:\,\ \left[-1\,\equiv\, c^{\large \color{#c00}2}\right] \!{\phantom{}}^{\large \color{#c00}{2k+1}}\Rightarrow\ {-1}\equiv c^{\, \color{#c00}{\large p-1}}\overset{\rm Fermat}\equiv 1\,\Rightarrow\, p\mid 2\ \Rightarrow\!\Leftarrow$

• What can be said about the converse?
– MCT
Mar 13, 2015 at 23:16
• @Soke See here. Mar 13, 2015 at 23:21

It's not true. $5$ divides $25 = 3^2 + 4^2$ but $5$ does not divide $9$, nor $16$.

Question is: If $3|a^2+b^2$ then $3|a$ or $3|b$ (Same condition!). This is natural trick of $3$.

We can prove contrapositive:

If $3 \not | a,b$, this means $a^2 \equiv b^2 \equiv 1 \: \text{mod} \: 3$. Therefore, $a^2+b^2 \equiv 2 \: \text{mod} \: 3$. Hence $3 \not | a^2+b^2$.

• It's not "or", it's "and" - If $3 \mid a^2+b^2$ then $3 \mid a$ and $3\mid b$. Your argument can still work but needs a little more added. Mar 13, 2015 at 23:15
• I supposed we are trying to help. I also wanna showed a different perspective. On the other hand, there is too many solution. But you are right! This is not changing that this prove needs a little more added. Mar 13, 2015 at 23:34

We know $n^2 \equiv \{0,1\} \bmod 3$,

thus for $(a^2+b^2) \equiv 0 \bmod 3$ we require $a^2 \equiv 0 \bmod 3$ and $b^2 \equiv 0 \bmod 3$

which gives $\{a,b\} \equiv 0 \bmod 3$ as required.

• How does it follow, formally, that $x^2\equiv (0,1) \mod 3$? What about $2\mod 3$? Mar 13, 2015 at 22:47
• $x\equiv 2 \bmod 3 \implies x^2 \equiv 4\equiv 1\bmod 3$ ... I changed the answer slightly to clarify that I'm talking about alternative values, not a range. Mar 13, 2015 at 23:06

very simple: given a quadratic form $$f(x,y) = a x^2 + b xy + c y^2,$$ with "discriminant" $$\Delta = b^2 - 4 a c.$$

Theorem: given an odd prime $q$ that does not divide $\Delta$ and for which Legendre symbol $$(\Delta | q ) = -1,$$ whenever $q$ divides $a x^2 + b x y + c y^2,$ then $q$ divides both $x$ and $y.$

PROOF: Note that the hypotheses demand that $q$ not divide $4a.$ Complete the square and some other stuff.

Here, we see that $$(a^2 + b^2, 2ab) = ((a + b)^2, 2ab)$$ .
By the elementary definition of the gcd of two numbers, we can safely assume that $$gcd = 3$$ or $$3$$ is a common divisor. In doing so, we get $$3$$ divides $$ab$$ and also divides $$(a + b)^2$$. Any square number divisible by $$3$$ must be of the form $$3q$$. So any case of "$$a$$" being even or "$$b$$" being even automatically gets removed and there we have the final answer