3. Show that there do not exist positive integers $a$, $b$, $c$ and $d$, pairwise co-prime, such that $ab+cd$, $ac+bd$ and $ad+bc$ are odd divisors of the number $(a+b-c-d)(a-b+c-d)(a-b-c+d)$.
Problem
Source: Problem 3
Tags: symmetry, number theory, relatively prime, number theory proposed
SebP
04.11.2012 00:30
Solution.
Suppose by a way of contradiction that such integers $a,b,c,d$ exist. Let $P=(a+b-c-d)(a-b+c-d)(a-b-c+d)$. First note that the problem is symmetric with respect to $a,b,c,d$. Indeed, on exchanging any two of the variables $a,b,c,d$, $|P|$ does not change, nor do the three numbers $ab+cd$, $ac+bd$ and $ad+bc$.
We claim that $ab+cd$, $ac+bd$ and $ad+bc$ must be pairwise relatively prime. Suppose otherwise for a contradiction, and let $p$ be a prime number dividing, without loss of generality (because of the symmetry) both $ac+bd$ and $ad+bc$; $p$ must be odd. We have $p|(ac+bd)+(ad+bc)=(a+b)(c+d)$ and $p|(ac+bd)-(ad+bc)=(a-b)(c-d)$. If $p|a+b,a-b$, then $p|(a+b)+(a-b)=2a$ and $p|(a+b)-(a-b)=2b$. But since $a$ and $b$ are relatively prime, we should have $p=2$, contradiction. The same happens if $p|c+d,c-d$. Therefore, $p$ must divide both $a+b$ and $c-d$ or $a-b$ and $c+d$. Suppose it is the first case; the second is analogous. Since $p|P$ it follows that $P=(a+b-c-d)(a-b+c-d)(a-b-c+d)\equiv(-c-d)(a-b)(a-b)\equiv 0$ (mod $p$). As a consequence, $p|c+d$ or $p|a-b$. But then we once again have $p|a+b,a-b$ or $p|c+d,c-d$ which leads to $p=2$, contradiction. This way, we conclude that $ab+cd$, $ac+bd$ and $ad+bc$ must be pairwise relatively prime.
But now, since $ab+cd$, $ac+bd$ and $ad+bc$ are pairwise relatively prime divisors of $P$, their product $Q$ should divide $P$, $Q|P$. However, it is easy to check that $ab+cd> |a+b-c-d|$ and so on ciclically with $ac+bd$ and $ad+bc$. Indeed, if without loss of generality $a+b\ge c+d$ then $ab+cd-|a+b-c-d|=ab+cd-a-b+c+d=(a-1)(b-1)+[(c+1)(d+1)-2]>0$. This way, we obtain that $|P|<|Q|$ and since $P$ is odd, because for the three numbers $ab+cd$, $ac+bd$ and $ad+bc$ to be all odd we must have that exactly one of $a,b,c,d$ is even, we conclude that $0<|P|<|Q|$, a contradiction. So our initial assumption was wrong, and such numbers cannot exist.
Letteer
16.11.2019 16:12
Here’s a sketch of the proof, which relies on the following two properties of division:
Fact 1: If $n$ divides $k$ , $m$ divides $k$ and $\gcd(n,m)=1$ then $nm$ divides $k$.
Fact 2: If $n$ divides $k$ and $k \neq 0$ then $|n| \leq |k|$.
Assume such integers exist, the first step of the proof consists of showing that the three divisors are relatively prime, which can be done using a proof by contradiction:
Assume, for example, $gcd(ab+cd, ac+bd) > 1$ , then there exists an *odd* prime $p$ that divides $ab+cd$ and $ac+bd$. It follows that $p$ divides:
$ab+cd+ac+bd=(a+d)(b+c)$
Which is to say $p$ divides $a+d$ or $b+c$. WLOG $p$ divides $a+d$, from which we can show that $p$ divides $b-c$, but $p$ also divides one of :
$\begin{cases}
a + b - c - d\\
a - b + c - d\\
a - b - c + d \\
\end{cases}$
We can easily show that every possibility yields a contradiction. Hence:
$\gcd(ab+cd, ac+bd)= \gcd(ab+cd, ad+bc)=gcd(ad+bc, ac+bd)=1 $
Combining this with Fact 1, we conclude that:
$(ab+cd)(ac+bd)(ad+bc)$
divides :
$ (a + b - c - d)(a - b + c - d)(a - b - c + d)$
Now, to use Fact 2, we need to show that the expression above is non-zero. This can be done by proving that each of the three factors is odd (hence it can’t be zero).
However, we have the following:
$ \begin{cases}
|a + b - c - d| < max(a+b,c+d) \leq ac+bd \\
|a - b + c - d| < max(a+c,b+d) \leq ad+cb \\
|a - b - c + d| < max(a+d,b+c)\leq ab+cd \\
\end{cases}$
Multiplying those $3$ inequalities and using Fact 2 yields a contradiction and finishes the proof.