Why is $(a⋅b - c⋅d)$, $(a⋅c-b⋅d)$, $(a⋅d-b⋅c)$ ALL either divisible by $3$ or ALL not divisible by $3$ for the following?

Question

Assuming I am correct,

For $a,b,c,d$ as positive odd integers and where $a,b,c,d$ are not multiples of $3$, Why is $(a⋅b - c⋅d)$, $(a⋅c-b⋅d)$, $(a⋅d-b⋅c)$ ALL either multiples of $3$ or ALL not multiples of $3$?

As a self learner I noticed that happening and I have no idea how to approach it. If either $a,b,c,d$ is a multiple of $3$, I can understand why they ALL are not multiples of $3$. However, $a,b,c,d$ can also be different prime numbers and the condition still works.

Example 1:

$13⋅23- 31⋅47 = -1158$ , $-1158 \bmod 3=0$ , $-1158 / 3 = -336$

$13⋅31- 23⋅47 = -678$ , $-678 \bmod 3=0$ , $-678 / 3 = -226$

$13⋅47- 23⋅31 = -102$ , $-102 \bmod 3=0$ , $-102 / 3 = -34$

Example 1:

$43⋅79 - 103 ⋅ 131 = -100968$ , $-10096 \bmod 3 ≠ 0$ , $-1158 / 3 = -3365.333...$

$43⋅103- 79⋅131 = -5920$ , $-5920 \bmod 3≠0$ , $-5920 / 3 = -1973.333...$

$43⋅131- 79⋅103 = -2504$ , $-2504 \bmod 3≠0$ , $-2504 / 3 = -834.666...$

*Edit, per one of the comments: The condition doesn't hold when: any $,,,$ such that exactly two are multiples of $3$

Answer 1

This is by far easiest to see by using modular arithmetic. It is not neccessary that $a,b,c,d$ are odd, but your claim does depend on none of them being multiples of $3$.

This assumption means that each of them is congruent to either $1$ or $-1$ modulo $3$.

This means that the product of two of them (still modulo 3) is $1$ if they are equal, but $-1$ if they are different.

Now if the four numbers are all equal modulo 3, then then the results of multiplying them pairwise will be $1$ no matter how you assign the four factors to two multiplications. Therefore their difference is $0$ modulo $3$ -- in other words the difference is a multiple of $3$.

If two of the factors are $1$ and the other two are $-1$, then again the two products will always be equal, though depending on how you distribute the inputs they might be either both $1$ or both $-1$. Again the difference is $0$ modulo $3$ for all the choices.

Finally, if one of the factors is different from the other three, then you always end up with one of the products being $1$ and the other being $-1$. Their difference is then $\pm 2$ modulo $3$ -- that is, not a multiple of $3$ in either case.

---

An alternative, less ad hoc but also more abstract way to see this is:

• When $x$ and $y$ are both known to be $\pm 1$ modulo $3$, then so is $xy$, and $xy\equiv -1$ exactly when $x\equiv -1$ XOR $y\equiv -1$.

• When $x$ and $y$ are both known to be $\pm 1$ modulo $3$, then $x-y\not\equiv 0$ exactly when $x\equiv -1$ XOR $y\equiv -1$.

The combination of these two facts tell us that $ab-cd\not\equiv 0$ iff $$ (a\equiv -1 \mathrel{\mathrm{XOR}} b \equiv -1) \mathrel{\mathrm{XOR}} (c\equiv -1 \mathrel{\mathrm{XOR}} d \equiv -1) $$ and because XOR is commutative and associative, it doesn't matter how you permute $a,b,c,d$.

Answer 2

A nice thing about asking whether expressions like these are divisible by a certain number (in this case, $3$) is that you only have to try a few possible values. Specifically, for divisibility by $3,$ you only have to consider numbers that are equal to $0,$ $1,$ or $2$; and since you have ruled out numbers $a,b,c,d$ that are themselves divisible by $3,$ you can skip the $0.$ You can work out all the possibilities using only the numbers $1$ and $2.$

A reason why you can do this is that adding or subtracting $3$ from any of the numbers $a,b,c,d$ is just going to add or subtract a multiple of $3$ from each of the expressions $ab−cd,$ $ac-bd,$ and $ad−bc.$ So if they are all divisible by $3$ the all stay divisible by $3$; if none are divisible by $3$ they all stay non-divisible by $3.$

Moreover, $cd - ab$ is or is not divisible by $3$ precisely when $ab - cd$ is or is not divisible by $3.$ So what you are trying to prove is equivalent to proving that either all or none of $\lvert ab−cd\rvert,$ $\lvert ac-bd\rvert,$ and $\lvert ad−bc\rvert$ are divisible by $3.$

Notice that this is just partitioning the four numbers $a,b,c,d$ into two groups of two and taking the absolute difference of the two products. You can exchange values between two of the numbers and you will still get the same answer. So we can reduce the number of cases to look at even further by only looking at the numbers in increasing sequence.

First case: all numbers the same, either all equal to $1$ or all equal to $2.$ Clearly all three differences are zero, divisible by $3.$

Second case: $a=b=c=1,$ $d=2.$ The differences are $-1,-1,1$ respectively, none divisible by $3.$

Third case: $a=b=1,$ $c=d=2.$ The differences are $-3,0,0$ respectively, all divisible by $3.$

Fourth case: $a=1,$ $b=c=d=2.$ The differences are $-2,-2,-2$ respectively, none divisible by $3.$

And there are no other possibilities, so that concludes the proof.

---

Note that $2-3=-1,$ so an alternative set of numbers to choose from is $\{-1,0,1\}.$ This makes the calculations even simpler, and if you notice that changing the sign of every number has no effect on the three differences of products, you will realize that if the case $a=b=c=-1,$ $d=1$ is OK then so is the case $a=b=c=1,$ $d=-1$ (and likewise the case $a=-1,$ $b=c=d=1$).

If you also notice that changing the signs of exactly two numbers changes the signs of some of the differences but does not affect divisibility by $3,$ you may realize that the case $a=b=-1,$ $c=d=1$ produces the same answer as all numbers equal (namely, the differences are all zero).

---

Using only a small set of numbers like this also makes it easy to determine when the conclusion is true (all differences divisible by $3$ or none divisible by $3$) in cases where we allow multiples of $3$ among $a,b,c,d.$ And even simpler if we select all of our four numbers from the set $\{-1,0,1\}.$

One multiple of $3$ means we always have a difference between $0$ and $\pm1,$ so none of the differences is divisible by $3.$

Three or four multiples of $3$ means both products are always zero, so all of the differences are divisible by $3.$

Finally, two multiples of $3,$ for example $a=b=0,$ $c=\pm1,$ $d=\pm1$ means we have one difference (e.g. $ab-cd$) that is non-zero, whereas all the other products are one of $a$ or $b$ with one of $c$ or $d,$ hence all zero. So two differences are divisible by $3$ and one is not.