Prove ${a^2+ac-c^2=b^2+bd-d^2}$ and $a > b > c > d \implies ab + cd$ is not prime

Question

Let $a>b>c>d$ be positive integers and suppose that $${a^2+ac-c^2=b^2+bd-d^2}$$

Prove that $ab+cd$ is not prime? I don't know if this problem is true.

I found that this same problem has also been posted on AOPS.

But I can't prove this problem. Can anyone help me?

Answer 1

Rewrite as:

$$a^2-b^2+ac-bc=bd-bc+c^2-d^2$$ $$(a-b)(a+b+c)=(c-d)(c+d-b)$$

Since $a>b>c>d$, each of $a-b, a+b+c, c-d, c+d-b$ is positive. By factoring lemma (excerpted below) there exists $w, x, y, z \in \mathbb{Z}^+$ s.t.

$$a-b=wx, a+b+c=yz, c-d=wy, c+d-b=xz$$

Solving for $a, b, c, d$, we get:

\begin{align} 5a=3wx+2yz-wy-xz \\ 5b=-2wx+2yz-wy-xz \\ 5c=-wx+yz+2wy+2xz \\ 5d=-wx+yz-3wy+2xz \end{align}

Thus:

\begin{align} & 25(ab+cd) \\ & =(3wx+2yz-wy-xz)(-2wx+2yz-wy-xz) \\ & +(-wx+yz+2wy+2xz)(-wx+yz-3wy+2xz) \\ & =5(z^2-wz-w^2)(x^2+y^2) \end{align}

$$5(ab+cd)=(z^2-wz-w^2)(x^2+y^2)$$

Since $b>c$,

$$-2wx+2yz-wy-xz=5b>5c=-wx+yz+2wy+2xz$$ $$yz>wx+3wy+3xz$$

In particular, $yz>wx+3wy+3xz>3xz$ implies $y>3x$ and $yz>wx+3wy+3xz>3wy$ implies $z>3w$.

Thus $$x^2+y^2>x^2+9x^2>5$$ $$z^2-wz-w^2=(z-\frac{w}{2})^2-\frac{5w^2}{4}>(3w-\frac{w}{2})^2-\frac{5w^2}{4}=5w^2 \geq 5$$

If $ab+cd$ is a prime, then $ab+cd \geq 4(3)+2(1)>5$, then $5(ab+cd)=(z^2-wz-w^2)(x^2+y^2)$ implies that $ab+cd$ divides exactly 1 of $z^2-wz-w^2$ and $x^2+y^2$. However, the term not divisible by $ab+cd$ must necessarily divide $5$, and thus be $\leq 5$. Since both $z^2-wz-w^2>5$ and $x^2+y^2>5$, we obtain a contradiction.

Therefore $ab+cd$ is not prime.

---

Below is the linked "factoring lemma".

Answer 2

The key observation is:

$$ (ac-bd) ( a^2 + ac - c^2) = (ab+cd) ( bc - ad). $$

This can be shown by expanding the LHS as $(ac)(b^2+bd-d^2) - (bd) (a^2 + ac - c^2)$, noticing that $abcd$ cancels out, and factoring.

Proof by contradiction. Suppose $ab+cd$ is prime.

• Because $ac-bd > 0, a^2+ac-c^2 > 0, ab+cd > 0,$ hence we can conclude that $bc-ad > 0$.
• Since $0 < ac - bd < ab + cd$, so $\gcd(ac-bd, ab+cd) = 1$, hence $ ac-bd \mid bc-ad$.
• This implies that $ ac-bd \leq bc-ad$.
• However, $(a-b)(c+d) > 0 \Leftrightarrow ac - bd > bc - ad $.

We have a contradiction, so $ ab+cd$ is not prime.

---

Notes

I came up with the key observation because I was working on similar problems like

1. IMO 2001/6,
2. If $a^2+ab+b^2 = c^2 + cd+d^2$, then $a+b+c+d$ is not prime, and
3. If $ a>b>c >d > 0 $ such that $a^2-ab+b^2 = c^2 - cd + d^2 $ then $ ab+cd $ is not prime.

In all of them, there's an approach that similarly finds a nice algebraic expression involving the variables, then argues about primality.