11
$\begingroup$

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

$\endgroup$

5 Answers 5

14
$\begingroup$

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$).

$\endgroup$
1
  • 1
    $\begingroup$ I think that we may well have the same solution "under the hood", but I like your spin on it better. $\endgroup$ Jun 9, 2018 at 14:35
8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)}$ .

$\endgroup$
1
  • $\begingroup$ For $(a,b,c,d)=(4,35,7,20)$, the lemma says $4=7$. $\endgroup$
    – robjohn
    Jun 9, 2018 at 18:56
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.