# 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. – Meitar Abarbanel Mar 13 '15 at 22:36
• @Meitar The original claim it true for all primes of form $\, p = 4k+3,\,$ see my answer. – Bill Dubuque Mar 13 '15 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 – Meitar Abarbanel Mar 13 '15 at 22:18
• ...and why you should do some sanity checks early on. They can help you with the proof either way. – Simon S Mar 13 '15 at 22:20
• I am so sorry. I misread the date. – Meitar Abarbanel Mar 13 '15 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. – Meitar Abarbanel Mar 13 '15 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 '15 at 23:16
• @Soke See here. – Bill Dubuque Mar 13 '15 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. – Joffan Mar 13 '15 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. – vudu vucu Mar 13 '15 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$? – Meitar Abarbanel Mar 13 '15 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. – Joffan Mar 13 '15 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