$a^{2} + b^{2}+ ab = c^{2} + d^{2} + cd$. Is it possible that $a+b+c+d$ be prime number?

what I get is

$$ a = - p r + qs $$ $$ b = pq + 3 rs + 2 p r + q s $$ $$ c = 3 rs + p r + q s $$ $$ d = pq + p r + q s $$

after which $$ a+b+c+d = (p+2s)(2q+3r). $$

I picked this one as having the fewest available minus signs.

The remaining part is why we never get $p+2s = \pm 1$ or $2q+3r = \pm 1$ and the other factor prime. The rules are: $a,b,c,d$ positive, $\gcd(a,b,c,d) = 1,$ $(c,d) \neq (a,b)$ and $(c,d) \neq (b,a)$ and probably others. Since I am demanding $a^2 + ab + b^2$ have at least two essentially different expressions with positive variables, it cannot be a prime or three times a prime. I see: it can be a prime cubed but not a prime squared, properties of Gauss composition following from class number one.

SLOGGING through: we want to rule out any chance of the product $ (p+2s)(2q+3r)$ being prime, using the conditions above in a minimal way. For example, if $p+2s = 1,$ we cannot have $a,b,c,d$ all positive, as then $a+c= (2q+3r)s$ while $b+d = (2q+3r)(1-s).$ As $a+b+c+d \neq 0,$ we know $(2q+3r) \neq 0.$ Either $s \leq 0$ or $(1-s) \leq 0,$ so either $a+c \leq 0$ or $b+d \leq 0,$ not allowed. We have shown that $p+2s \neq 1.$

Three more to go, $p+2s \neq -1,$ $2q+3r \neq 1,$ $2q+3r \neq -1$

  a^2 + ab + b^2  a  b  c  d
  91 =  7 13 ;    1  9  6  5 sum    21 =  3 7 pqrs    1  2  1  1
  91 =  7 13 ;    5  6  9  1 sum    21 =  3 7 pqrs    1 -2 -1 -2
  91 =  7 13 ;    6  5  1  9 sum    21 =  3 7 pqrs    1  5 -1  1
  91 =  7 13 ;    9  1  5  6 sum    21 =  3 7 pqrs    1 -5  1 -2
 133 =  7 19 ;   11  1  4  9 sum    25 =  5^2 pqrs    1 -4  1 -3
 133 =  7 19 ;    1 11  9  4 sum    25 =  5^2 pqrs    1  1  1  2
 133 =  7 19 ;    4  9 11  1 sum    25 =  5^2 pqrs    1 -1 -1 -3
 133 =  7 19 ;    9  4  1 11 sum    25 =  5^2 pqrs    1  4 -1  2
 147 =  3 7^2 ;    2 11  7  7 sum    27 =  3^3 pqrs    1  3  1  1
 147 =  3 7^2 ;    7  7 11  2 sum    27 =  3^3 pqrs    1 -3 -1 -2
 217 =  7 31 ;    3 13  8  9 sum    33 =  3 11 pqrs    1  4  1  1
 217 =  7 31 ;    9  8 13  3 sum    33 =  3 11 pqrs    1 -4 -1 -2
 247 =  13 19 ;   11  7  3 14 sum    35 =  5 7 pqrs    1  5 -1  2
 247 =  13 19 ;   14  3  7 11 sum    35 =  5 7 pqrs    1 -5  1 -3
 247 =  13 19 ;    3 14 11  7 sum    35 =  5 7 pqrs    1  2  1  2
 247 =  13 19 ;    7 11 14  3 sum    35 =  5 7 pqrs    1 -2 -1 -3
 259 =  7 37 ;   13  5  2 15 sum    35 =  5 7 pqrs    1  4 -1  3
 259 =  7 37 ;   15  2  5 13 sum    35 =  5 7 pqrs    1 -4  1 -4
 259 =  7 37 ;    2 15 13  5 sum    35 =  5 7 pqrs    1  1  1  3
 259 =  7 37 ;    5 13 15  2 sum    35 =  5 7 pqrs    1 -1 -1 -4
 273 =  3 7 13 ;    1 16 11  8 sum    36 =  2^2 3^2 pqrs    1  3  2  1
 273 =  3 7 13 ;    1 16  8 11 sum    36 =  2^2 3^2 pqrs    2  3  1  1
 273 =  3 7 13 ;   11  8 16  1 sum    36 =  2^2 3^2 pqrs    2 -3 -1 -3
 273 =  3 7 13 ;    8 11 16  1 sum    36 =  2^2 3^2 pqrs    1 -3 -2 -2
 301 =  7 43 ;   11  9 15  4 sum    39 =  3 13 pqrs    1 -5 -1 -2
 301 =  7 43 ;    4 15  9 11 sum    39 =  3 13 pqrs    1  5  1  1
 343 =  7^3 ;    1 18 14  7 sum    40 =  2^3 5 pqrs    2  1  1  3
 343 =  7^3 ;   14  7  1 18 sum    40 =  2^3 5 pqrs    2  4 -1  3
 343 =  7^3 ;   18  1  7 14 sum    40 =  2^3 5 pqrs    2 -4  1 -5
 343 =  7^3 ;    7 14 18  1 sum    40 =  2^3 5 pqrs    2 -1 -1 -5
 399 =  3 7 19 ;   10 13 17  5 sum    45 =  3^2 5 pqrs    1 -3 -1 -3
 399 =  3 7 19 ;    5 17 13 10 sum    45 =  3^2 5 pqrs    1  3  1  2
 403 =  13 31 ;   14  9 19  2 sum    44 =  2^2 11 pqrs    2 -4 -1 -3
 403 =  13 31 ;    2 19  9 14 sum    44 =  2^2 11 pqrs    2  4  1  1
 427 =  7 61 ;   17  6  3 19 sum    45 =  3^2 5 pqrs    1  4 -1  4
 427 =  7 61 ;   19  3  6 17 sum    45 =  3^2 5 pqrs    1 -4  1 -5
 427 =  7 61 ;    3 19 17  6 sum    45 =  3^2 5 pqrs    1  1  1  4
 427 =  7 61 ;    6 17 19  3 sum    45 =  3^2 5 pqrs    1 -1 -1 -5
 469 =  7 67 ;   12 13 20  3 sum    48 =  2^4 3 pqrs    1 -5 -2 -2
 469 =  7 67 ;    3 20 13 12 sum    48 =  2^4 3 pqrs    1  5  2  1
 481 =  13 37 ;   16  9  5 19 sum    49 =  7^2 pqrs    1  5 -1  3
 481 =  13 37 ;   19  5  9 16 sum    49 =  7^2 pqrs    1 -5  1 -4
 481 =  13 37 ;    5 19 16  9 sum    49 =  7^2 pqrs    1  2  1  3
 481 =  13 37 ;    9 16 19  5 sum    49 =  7^2 pqrs    1 -2 -1 -4
 507 =  3 13^2 ;    1 22 13 13 sum    49 =  7^2 pqrs    3  2  1  2
 507 =  3 13^2 ;   13 13  1 22 sum    49 =  7^2 pqrs    3  5 -1  2
 507 =  3 13^2 ;   13 13 22  1 sum    49 =  7^2 pqrs    3 -2 -1 -5
 507 =  3 13^2 ;   22  1 13 13 sum    49 =  7^2 pqrs    3 -5  1 -5
 553 =  7 79 ;   11 16 23  1 sum    51 =  3 17 pqrs    1 -4 -3 -2
 553 =  7 79 ;    1 23 16 11 sum    51 =  3 17 pqrs    1  4  3  1
 559 =  13 43 ;   17 10 22  3 sum    52 =  2^2 13 pqrs    2 -5 -1 -3
 559 =  13 43 ;    3 22 10 17 sum    52 =  2^2 13 pqrs    2  5  1  1
 589 =  19 31 ;   13 15 20  7 sum    55 =  5 11 pqrs    1 -4 -1 -3
 589 =  19 31 ;    7 20 15 13 sum    55 =  5 11 pqrs    1  4  1  2
 637 =  7^2 13 ;   12 17 23  4 sum    56 =  2^3 7 pqrs    2 -2 -1 -5
 637 =  7^2 13 ;   17 12  4 23 sum    56 =  2^3 7 pqrs    2  5 -1  3
 637 =  7^2 13 ;   21  7  4 23 sum    55 =  5 11 pqrs    1  4 -1  5
 637 =  7^2 13 ;   23  4 12 17 sum    56 =  2^3 7 pqrs    2 -5  1 -5
 637 =  7^2 13 ;    4 23 17 12 sum    56 =  2^3 7 pqrs    2  2  1  3
 637 =  7^2 13 ;    4 23 21  7 sum    55 =  5 11 pqrs    1  1  1  5
 651 =  3 7 31 ;    1 25 10 19 sum    55 =  5 11 pqrs    3  4  1  1
 651 =  3 7 31 ;    1 25 19 10 sum    55 =  5 11 pqrs    3  1  1  4
 651 =  3 7 31 ;   19 10  1 25 sum    55 =  5 11 pqrs    3  4 -1  4
 651 =  3 7 31 ;   19 10 25  1 sum    55 =  5 11 pqrs    3 -4 -1 -4
 679 =  7 97 ;   13 17 25  2 sum    57 =  3 19 pqrs    1 -5 -3 -2
 679 =  7 97 ;    2 25 17 13 sum    57 =  3 19 pqrs    1  5  3  1
 703 =  19 37 ;    1 26 23  6 sum    56 =  2^3 7 pqrs    1  1  2  3
 703 =  19 37 ;    6 23 26  1 sum    56 =  2^3 7 pqrs    1 -1 -2 -4
 741 =  3 13 19 ;   11 20 25  4 sum    60 =  2^2 3 5 pqrs    1 -3 -2 -3
 741 =  3 13 19 ;    4 25 20 11 sum    60 =  2^2 3 5 pqrs    1  3  2  2
 763 =  7 109 ;   22  9  3 26 sum    60 =  2^2 3 5 pqrs    2  4 -1  5
 763 =  7 109 ;    3 26 22  9 sum    60 =  2^2 3 5 pqrs    2  1  1  5
 777 =  3 7 37 ;   13 19 23  8 sum    63 =  3^2 7 pqrs    1 -3 -1 -4
 777 =  3 7 37 ;    8 23 19 13 sum    63 =  3^2 7 pqrs    1  3  1  3
 793 =  13 61 ;   11 21 24  7 sum    63 =  3^2 7 pqrs    1 -2 -1 -5
 793 =  13 61 ;   21 11  7 24 sum    63 =  3^2 7 pqrs    1  5 -1  4
 793 =  13 61 ;   24  7 11 21 sum    63 =  3^2 7 pqrs    1 -5  1 -5
 793 =  13 61 ;    7 24 21 11 sum    63 =  3^2 7 pqrs    1  2  1  4
 817 =  19 43 ;   16 17 23  9 sum    65 =  5 13 pqrs    1 -5 -1 -3
 817 =  19 43 ;    9 23 17 16 sum    65 =  5 13 pqrs    1  5  1  2
 871 =  13 67 ;    1 29 15 19 sum    64 =  2^6 pqrs    2  5  2  1
 871 =  13 67 ;   19 15 29  1 sum    64 =  2^6 pqrs    2 -5 -2 -3
 903 =  3 7 43 ;    2 29 11 23 sum    65 =  5 13 pqrs    3  5  1  1
 903 =  3 7 43 ;    2 29 23 11 sum    65 =  5 13 pqrs    3  1  1  5
 903 =  3 7 43 ;   23 11  2 29 sum    65 =  5 13 pqrs    3  4 -1  5
 903 =  3 7 43 ;   23 11 29  2 sum    65 =  5 13 pqrs    3 -5 -1 -4
 931 =  7^2 19 ;    1 30 21 14 sum    66 =  2 3 11 pqrs    1  5  4  1
 931 =  7^2 19 ;    1 30 25  9 sum    65 =  5 13 pqrs    1  2  3  2
 931 =  7^2 19 ;   14 21 30  1 sum    66 =  2 3 11 pqrs    1 -5 -4 -2
 931 =  7^2 19 ;    9 25 30  1 sum    65 =  5 13 pqrs    1 -2 -3 -3
1027 =  13 79 ;   19 18  2 31 sum    70 =  2 5 7 pqrs    4  5 -1  3
1027 =  13 79 ;    2 31 19 18 sum    70 =  2 5 7 pqrs    4  2  1  3
1029 =  3 7^3 ;   17 20 28  7 sum    72 =  2^3 3^2 pqrs    2 -3 -1 -5

well, why not. Using C++ with GMP, here is the active part of the program:

    mpz_class   bound = 5;

  for(mpz_class p = 0; p <= bound; ++p){
  for(mpz_class q = -bound; q <= bound; ++q){
  for(mpz_class r = -bound; r <= bound; ++r){
  for(mpz_class s = -bound; s <= bound; ++s){

    mpz_class a =                    q * s - p * r;
    mpz_class b = p*q + 3 * r*s + 2 * p * r + q * s ;
    mpz_class c =       3 * r*s +   p * r + q * s ;
    mpz_class d = p*q           +    p * r + q * s ;

  if ( a > 0 && b> 0 && c>0 && d > 0 && !( (a == c && b == d) || (a == d && b == c) ) && mp_coprime4(a,b,c,d)  )
  {
     cout << setw(8) << a *a+a*b+b*b<< " = " << mp_Factored(a*a+a*b+b*b) << " ;  " << setw(3) << a  << setw(3) << b  << setw(3) << c  << setw(3) << d    << " sum  " << setw(4) << a +b+c+d << " = " << mp_Factored(a+b+c+d)<< " pqrs  " << setw(3) << p  << setw(3) << q << setw(3) << r  << setw(3) << s  << endl;
    if (mp_PrimeQ(a+b+c+d) ) cout <<  "  WOE  " << endl;
  }

  }}}}

We work in the principal ideal domain $\mathbb Z [\omega]$, where $\omega = \frac{-1 + \sqrt3 i}{2}$ (which we view as an element of $\mathbb C$).

Without loss of generality, assume that $a \geq b$ and $c \geq d$, and that we don't have equality at the same time.

Write the equation as $(a + b \omega)(a + b\overline\omega) = (c + d \omega)(c + d\overline\omega)$. Let $u$ be the greatest common divisor of $a + b\omega$ and $c + d\omega$. It is well defined up to multiplication by a sixth root of unity, i.e. $\pm 1, \pm \omega, \pm \omega^2$.

Write $a + b\omega = u v$ and $c + d\omega = u v'$, with $v, v'$ coprime. We then have $v\overline v = v' \overline {v'}$, which implies (since $v, v'$ coprime) that $v \mid \overline{v'}$ and $v'\mid \overline v$. But taking complex conjugation gives $\overline{v'}\mid v$, hence $v' = \varepsilon v$ for some sixth root of unity $\varepsilon$.

We therefore have $a + b\omega = uv$, $c + d\omega = u\overline v \varepsilon$. By replacing $u, v, \varepsilon$ with $u\delta^{-1}, v\delta, \varepsilon\delta^2$ for some sixth root of unity $\delta$, we may assume without loss of generality that $\varepsilon = \pm 1$.


Case 1: $\varepsilon = 1$.

We have $a + b\omega = uv$. Taking complex conjugation gives $a + b\overline \omega = \overline u\overline v$. Solving this linear equation, we get $a + b = -\omega u v - \overline \omega \overline u \overline v$.

Similarly, we get $c + d = -\omega u \overline v - \overline \omega \overline u v$.

Hence in the end $a + b + c + d = -(\omega u + \overline {\omega u})(v + \overline v)$.

Since both $(\omega u + \overline {\omega u})$ and $v + \overline v$ are integers, if the product is prime, then one of them must be $\pm 1$.

Now observe the fact that, for any element $x \in \mathbb Z[\omega]$, $x + \overline x = \pm 1$ will imply that $\arg x$ lies in either $[60^\circ, 120^\circ]$ or $[-120^\circ, -60^\circ]$.

It follows that $v + \overline v$ cannot be $\pm 1$. This is because both $a + b\omega$ and $c + d\omega$ lives in the region $\{z \in \mathbb C: 0 < \arg z \leq 60^\circ\}$, hence the number $v/\overline v$, being their quotient, must have $\arg$ in the range $(-60^\circ, 60^\circ)$.

But $\omega u + \overline{\omega u}$ cannot be $\pm 1$ either. The reasoning is similar: since $a + b\omega$ and $c + d\omega$ cannot both attain $60^\circ$ of $\arg$, the number $u^2 v \overline v$, being their product, must have $\arg$ in the range$(0^\circ, 120^\circ)$. This means $u$ must have $\arg$ in the range $(0^\circ, 60^\circ)$ or $(-180^\circ, -120^\circ)$, hence $\omega u$ has $\arg$ in the range $(120^\circ, 180^\circ)$ or $(-60^\circ, 0^\circ)$.

This completes the proof that $a + b + c + d$ cannot be a prime number in the case $\varepsilon = 1$.


Case 2: $\varepsilon = -1$.

Same as above, we work out the formula $a + b + c + d = -(v - \overline v)(\omega u - \overline{\omega u})$.

This case is now significantly easier, since the product must be a multiple of $3$. So if it is a prime, then we have $a + b + c + d = 3$ and it's already impossible.


If $ \{ a, b \} = \{c, d \}$ then $a+b+c+d = 2(a+b)$ is not a prime.

Henceforth, we have distinct pairs. If $ a = c$, then $b \neq d$ are roots to $x^2 + ax + a^2 = 0$, so $b+d = -a$ contradicting the requirement that all of the terms are positive.
WLOG, $ a > c \geq d > b$.

Observe that $$ -(a-b+c-d)(a-b-c+d) = -\left((a-b)^2 - (c-d)^2\right) = 3(ab-cd) = 3\left( (a+b)^2 - (c+d)^2\right) = 3 (a+b-c-d)(a+b+c+d).$$

Since $ a+b+c+d > a-b+c-d \geq a-b-c+d > 0$, we can rewrite the above as a product of positive integers,

$$ (a-b+c-d)(a-b-c+d)= 3 (c+d-a-b)(a+b+c+d)$$

If $a+b+c+d$ is prime, then the LHS can never be a multiple of $a+b+c+d$ since both terms are smaller, hence we have a contradiction. So $ a+b+c+d$ is composite.


Notes:

  1. This problem/solution is very reminiscent of 2001/6 IMO. There we had $a^2+ab+b^2 = c^2 -cd+d^2$.
  2. I do not know a direct way to show that $cd > ab$. Any thoughts? This seems obvious.
  3. This being a contest problem suggests that there is a non "abstract algebra approach", even though it is very tempting. E.g. The equation in my solution can also be derived from WhatsUp's characterization (which is a stronger requirement).