$a,b,c,d$ are positive integers such that $ad=bc$. Prove that $n=a+b+c+d$ cannot be prime

Question

The question is from Round $1$ of $1996/97$ Iranian National Mathematical Olympiad. My attempt at a solution is as below:

$a,b,c,d$ cannot all be odd because then their sum would be even and therefore not prime. So, at least one of $a,b,c,d$ is even. Given that $ad=bc$, at least two of $a,b,c,d$ are even. If only two of $a,b,c,d$ are even, then $a+b+c+d$ is even and is not prime. Therefore, the only possibility is that three of $a,b,c,d$ are even.

Without loss of generality, let $a,b,c$ be even. Using $ad=bc$, we can prove that (after cancelling out any higher powers of $2$ that $a,b,c$ might share), $a\equiv 0\pmod 4$, $b\equiv 2\pmod 4$ and $c\equiv 2\pmod 4$, basically that $a$ has one extra power of $2$ than $b,c$.

I am stuck after this and do not know how to proceed

Answer 1

Since $d = bc/a$ is an integer, we can factor $d = (b/x)(c/y)$ for some positive integers $x,y$ such that $b/x$ and $c/y$ are integers and $xy=a$. (This is intuitively clear and can be made rigorous by playing around with prime factorizations of $a,b,c$.)

Then $$ a + b + c + d = xy + b + c + (b/x)(c/y) = (x + c/y)(y + b/x) $$ which is always a nontrivial factorization, so $a+b+c+d$ cannot be prime.

Answer 2

I'm not sure how to end your solution, but I have another one if you are interested:

Suppose $a+b+c+d=p\in \mathbb{P}$. Since $d=p-a-b-c$ we get $$a(p-a-b-c)=bc$$ so $$ ap = (a+b)(a+c) \implies p\mid a+b \;\;\;\;{\rm or }\;\;\;\;p\mid a+c$$

A contradiction (since $p>a+b$ and $p>a+c$).

Answer 3

If $ad=bc$, then $$ \begin{align} an &=a(a+b+c+d)\\ &=(a+b)(a+c)\tag1 \end{align} $$ Use Bezout's Identity to write $(a,b)=ax_b+by_b$ and $(a,c)=ax_c+cy_c$. Then $$ \begin{align} \frac{(a,b)(a,c)}a &=ax_bx_c+cx_by_c+bx_cy_b+dy_by_c\\ &\in\mathbb{Z}\tag2 \end{align} $$ Thus, $$ n=\frac{(a,b)(a,c)}a\overbrace{\ \ \frac{a+b}{(a,b)}\ \ }^{\ge2}\overbrace{\ \ \frac{a+c\vphantom{b}}{(a,c)}\ \ }^{\ge2}\tag3 $$

Answer 4

Here's one way to do it. Maybe not the best.

Let $w = \gcd(a,b)$ so that $a = a'w$ and $b=b'w$ so we have

Let $v = \gcd(c,d)$ so that $c =c'v$ and $d=d'v$ so we have

$ad = bc$

$a'd'wv = b'c'wv$ so $a'd' =b'c'$. So we have $b'|a'd'$ but as $a',b'$ are relatively prime $b'|d'$. And we also have $d'|b'c'$ but as $d',c'$ are relatively prime we have $d'|b'$.

So $b'|d'$ and $b'|d'$ and (these are positive values) so $d' = b'$. And so

$a'd' = d'c'$ so $c'= a'$.

And... that's it really.

$a + b + c + d= a'w + b'w + c'v + d'v = a'w+ d'w + a'v + d'v= (a'+d')(v + w)$

As we assumed $a,b,c,d> 0$ then $a',d',v,w \ge 1$ and $(a'+d'), (v+w)\ge 2$. Thus it's a composite number.

All the posted answers are more or less the same. It's just a matter of which tack seems clearer and straight forward. Mine isn't the fastest but it "falls out" pretty nicely.

It also gives us a useful lemma:

If $ab = cd$ then $\frac a{\gcd(a,b)} = \frac c{\gcd(c,d)}$ and $\frac b{\gcd(a,b)} = \frac d{\gcd(c,d)}$ .

Answer 5

Let $e$ be the highest common factor of $a$ and $b$; $f=a/e$; $g=b/e$. Then $f$ and $g$ are coprime. Let $h=c/f$. Then $h=bc/efg=ad/efg=d/g$. $h$ is rational. If some prime $p$ divides the denominator of $h$, then $p\mid f$ and $p\mid g$. (This is because $h$ and $ph$ have the same numerator, so therefore do $c/f$ and $pc/f$, so $p\mid f$; likewise $g$.) So $pe\mid a$ and $pe\mid b$, contradicting the definition of $e$. Thus $h$ is an integer. Then $$n=a+b+c+d=ef+eg+fh+gh=(e+h)(f+g).$$ As each of $e, f, g, h\geqslant 1$, the factors are non-trivial, so $n$ is composite.

Answer 6

Using the 4 number lemma, you will get the solution. It says that if $ab=cd,$ you can find positive integers $p,q,r,s$ such that

$a=pq$

$b=rs$

$c=ps$

$d=qr$

Now, $a+b+c+d = pq+ps+rs+qr=(p+q)(r+s)$ which is a composite number.