# For what primes $p \nmid \gcd(a,b,c)$ does $p \mid a+b+c \implies p \nmid a^2+b^2+c^2$?

Let us have prime $$p$$ such that $$p \nmid \gcd(a,b,c)$$ and $$p \mid a+b+c$$. For what primes is it then impossible for $$p \mid a^2+b^2+c^2$$ ?

One example of such a prime is $$p=5$$:

If $$5 \mid a^2+b^2+c^2$$ ; then $$5 \mid abc$$ as the quadratic residues modulo $$5$$ are only $$1,0,-1$$. WLOG, let $$5\mid a$$. Then, $$5 \mid b+c$$ and $$5 \mid b^2+c^2$$ which shows that $$5 \mid bc$$ and thus, $$5 \mid b$$ and $$5\mid c$$. Contradiction.

It is probable that $$5$$ might be the only prime that shows the above characteristics. Are there any other primes or an infinite set of primes that share these properties due to the structure of their quadratic residues?

• All primes of the form $p=6k-1$ has this property, because they are represented by the binary quadratic form $X^2+XY+Y^2$. – user10354138 Dec 9 '18 at 9:28
• Are they the only primes that satisfy the property? – Haran Dec 9 '18 at 9:32
• Oops, I meant not represented by $X^2+XY+Y^2$. The cases $p=2,3$ are easily eliminated, and all primes of the form $6k+1$ are represented by $X^2+XY+Y^2$ and $6k-1$ are not (recall representability is equivalent to the discriminant $d=-3$ being a quadratic residue $\mod 4p$, since $h(-3)=1$). – user10354138 Dec 9 '18 at 9:35
• Could we speak in chat? – Haran Dec 9 '18 at 9:41

Here is a hint to prompt further exploration.

We can eliminate $$p=2$$ from consideration.

Just setting $$c=kp-a-b$$ for arbitrary $$a$$ and $$b$$ gives, with an easy calculation, the test that $$a^2+ab+b^2$$ is/is not divisible by $$p$$ for some choice of $$a,b$$ - or alternatively whether $$(2a+b)^2+3b^2$$ is ever divisible by $$p$$.

Just to add from various comments to the question and this answer, this form can be reduced to saying that $$x^2+3$$ is divisible by $$p$$, and this in turn means $$x^2\equiv -3\bmod p$$ or that $$-3$$ is a quadratic residue mod $$p$$.

This is true for $$p\equiv 1 \bmod 6$$ but not for $$p\equiv -1 \bmod 6$$ (quite easy to prove using quadratic reciprocity)

You can also go via theorems about which primes are represented by quadratic forms.

The important point here is to note how a question which seems to involve three squares and all the quadratic residues, can be reduced to a question about a single quadratic residue - and how this relates to the coincidences which seem to have to occur if - given all the residues there are - the sum of the three squares never comes out divisible by $$p$$.

This kind of manipulation is quite common for this type of problem, and the results which come out can look and feel like a kind of magic.

• True, we can also eliminate the values of $p=3,7$ – Haran Dec 9 '18 at 9:10
• In fact, we can multiply $c^2$ such that $bc \equiv 1 \pmod{p}$ and $ac \equiv x \pmod{p}$ to make the equation $p \mid x^2+x+1$. – Haran Dec 9 '18 at 9:19
• @Haran Or you can perform the same trick with the form $(2a+b)^2+3b^2$ to get the form $x^2+3$ which may be easier to use if you are thinking of quadratic residues, since it takes you down to just one unknown square. – Mark Bennet Dec 9 '18 at 11:55