# $a^2−ab+b^2=c^2$. Show prime factors of $c$ are of the form $6k + 1$

I encountered this question in Number Theory by Naoki Sato.

Let a, b, and c be positive integers that are pairwise relatively prime, and that satisfy $a^2−ab+b^2=c^2$. Show that every prime factor of c is of the form $6k + 1$.

Attempt:

Since primes are either of the form $6k+1$ or $6k-1$, I tried to show $p \equiv 1 \pmod6$ by showing $p \equiv 1 \pmod2$ and $p \equiv 1 \pmod3$ but I am unable to show $p \equiv 1 \pmod3$.

Another direction I tried was to assume there exist a prime factor $p$ of $c$ with $p=6k-1$. By brute force I know that $a^2−ab+b^2 \equiv 0, 1, 3$, or $4 \pmod6$ but I can't see how to get a contradiction from here.

I am not sure how to use the condition that all 3 numbers are pairwise coprime.

Any help is much appreciated!

• math.stackexchange.com/questions/1351994/… – individ Jul 18 '18 at 17:00
• Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers. – Steven Stadnicki Jul 18 '18 at 17:00
• @individ thanks for the link! ill check it out – eatfood Jul 19 '18 at 3:19
• @StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with – eatfood Jul 19 '18 at 3:20

Here is a proof based on quadratic reciprocity.

Suppose $p=3k-1|a^2-ab+b^2$ with $a,b$ relatively prime. Neither $a$ nor $b$ can have zero residue $\bmod p$, else they both would which the hypothesis denies. Thus there exists a nonzero residue $r\equiv ab^{-1}\bmod p$ such that $r^2-r+1\equiv 0$. Multiplying by $4$ and completing the square gives $(2r-1)^2\equiv -3$. Therefore the Legendre symbol $(-3|p)=+1$ if $p$ is as assumed above.

But $(p|3)=(3k-1|3)=-1$ and $-3\equiv +1\bmod 4$, so QR forces the contradictory conclusion $(-3|p)=-1$.

The case $p=3$ remains and this is a bit tricky. There are multiples of $3$ having the form $a^2-ab+b^2$ where $a$ and $b$ are relatively prime. We just need $a\equiv -b\bmod 3$ because $a^2-ab+b^2\equiv (a+b)^2\bmod 3$. But, if $a\equiv -b\bmod 3$ with the common residue being $1$ or $2$, we find that $c^2\equiv 3\bmod 9$ which doesn't work.

• Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 \equiv 0 \pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot! – eatfood Jul 19 '18 at 3:15
• So more generally, for $p \ne 2$ prime (and $a \not\equiv 0 \pmod{p}$), $ar^2 + br + c \equiv 0 \pmod{p}$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.) – Daniel Schepler Jul 19 '18 at 15:32
• One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1\equiv 0\bmod 5$ where $b^2-4ac=5\equiv 0$ has a solution $x\equiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately. – Oscar Lanzi Jul 19 '18 at 21:20

Suppose $p \mid c$, so that $a^2 - ab + b^2 \equiv 0 \pmod{p}$. That implies that $a^3 + b^3 \equiv 0 \pmod{p}$. By the assumption that $a$ and $b$ are each relatively prime to $c$, we have that $p \nmid a, b$, so $-a b^{-1}$ has cube equal to 1 in $\mathbb{Z} / p \mathbb{Z}$. Also, if it were the case that $a \equiv -b \pmod{p}$, then we would have $3 a^2 \equiv a^2 - ab + b^2 \equiv 0 \pmod{p}$, giving a contradiction (as long as $p\ne 3$; but in this case, for example if $a = 3m+1$ and $b=3n-1$, then $a^2 - ab + b^2 = 9m^2 - 9mn + 9n^2 -9m + 9n + 3 \equiv 3 \pmod{9}$ contradicting the fact that $3 \mid c^2$ implies $9 \mid c^2$). Therefore, $-a b^{-1}$ has order exactly three in the group of units of $\mathbb{Z} / p \mathbb{Z}$, implying that 3 divides $|(\mathbb{Z} / p \mathbb{Z})^*| = p-1$.

• Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 \equiv 0 \pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still! – eatfood Jul 19 '18 at 3:12

Here is an algebraic theoretical proof parallel to the "gaussian" proof of Fermat's theorem on sums of squares. You may find it too complicated, but actually the general trend in math is to try to embed particular questions into larger and larger general theories in order to solve in one stroke whole families of problems which are of the same nature (*)

First replace the Gauss ring $\mathbf Z[i]$ by the Eisenstein ring $E=\mathbf Z[j]$, which is the ring of integers of the quadratic field $\mathbf Q(j)$, where $j$ is a primitive 3rd root of unity. It is classically known that $E$ is a principal ideal ring, so the theory of division in $E$ for ideals and for elements is the same up to the units of $E$, which are plainly the powers of $\pm j$. The prime elements (ideals) of $E$ are deduced from those of $\mathbf Z$ in the following manner : a prime $p$ of $\mathbf Z$ does not necessarily remain prime in $E$, but it can decompose only in 3 possible ways : (1) $p$ is inert, i.e. remains prime, iff $p\equiv 2$ mod $3$ ; (2) $p$ splits, i.e. $p=\pi\bar\pi$ (where $\pi$ is a prime of $E$) iff $p\equiv 1$ mod $3$ ; (3) $p$ ramifies in $E$, i.e. $p=\pi^2$ iff $p=3$ (see any textbook in ANT).

Now the equation $a^2-ab+b^2=c^2$ in $\mathbf Z$ reads $(a+bj)(a+bj^2)=c^2$ in $E$, where the UFD property implies that the prime divisors $\pi$ of $c$ are exactly such that $\pi$ divides $a+bj$, say, and the conjugate $\bar \pi$ divides $a+bj^2$. By uniqueness again, $\pi\bar \pi$ will divide $c$, i.e. the rational primes $p$ which divide $c$ must split.

(*) An archetypical example lies in the attempts to solve FLT by the same approach as above. Actually Kummer showed FLT along these lines - but of course with more involved arguments - in the so called regular case, i.e. when the ring $\mathbf Z[\zeta_p]$ (where $\zeta_p$ is a primitive $p$-th root of unity) is principal.