17
$\begingroup$

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite.
I have my own solution for this (As posted) and i want to see if there is any other good proofs.

$\endgroup$
8
  • 2
    $\begingroup$ Is this homework? What have you tried? $\endgroup$ Commented May 6, 2013 at 15:38
  • 10
    $\begingroup$ I vote against closing this question. $\endgroup$
    – MJD
    Commented May 6, 2013 at 15:45
  • $\begingroup$ Let the OP respond before closing the question. The question seems pretty good. $\endgroup$
    – Inceptio
    Commented May 6, 2013 at 15:48
  • 2
    $\begingroup$ I, too, find this question interesting. Nevertheless I downvoted it for the way it was asked: No context was given, no own effort is shown and only in the comments it turns out it was merely asked to see if someone will come up with a better solution and that the questioner already has solutions. So my read on it is that it’s basically a test to see whether other people are as clever as the questioner which I find rude. But maybe I misinterpret this? At the very least, I think you, CODE, should add your intentions to the question. $\endgroup$
    – k.stm
    Commented May 6, 2013 at 16:10
  • 4
    $\begingroup$ Note this does not work if you include 0 in the natural numbers. (Obvious counterexample: a = 0, b=3, c=0, d=4, so ab = cd = 0, but a+b+c+d=7 which is prime). $\endgroup$
    – dr jimbob
    Commented May 6, 2013 at 18:49

7 Answers 7

25
$\begingroup$

By the Four Number Theorem (a consequence of unique prime factorization), it follows that $ab=cd$ implies $a=xy, b=zt, c=xz, d=yt$ for some integers $x,y,z,t$. Hence $$ a+b+c+d=(x+t)(y+z). $$

$\endgroup$
7
  • $\begingroup$ This may be nitpicking, but $2 \cdot 3 = 3 \cdot 2$ does not imply $2 = xy$. $\endgroup$
    – orlp
    Commented May 6, 2013 at 19:08
  • $\begingroup$ @nightcracker: Sorry, I didn't understand. Do you consider the case $a=d=2, b=c=3$? $\endgroup$ Commented May 6, 2013 at 19:16
  • 1
    $\begingroup$ @nightcracker: $a=2$, $b=3$, $c=3$, $d=2$, $x=1$, $y=2$, $z=3$, $t=1$ works. $\endgroup$
    – fgrieu
    Commented May 6, 2013 at 19:59
  • $\begingroup$ Of course, pesky $1$ :D Nevermind. $\endgroup$
    – orlp
    Commented May 6, 2013 at 20:07
  • 2
    $\begingroup$ @nightcracker: Still this answer is more that a bit sketchy, for the construction of $x$, $y$, $z$, $t$ is left as an exercise to the reader. $\endgroup$
    – fgrieu
    Commented May 6, 2013 at 20:53
14
$\begingroup$

From $ab=cd$ you have $$(a+b)^2-(a-b)^2=(c+d)^2-(c-d)^2\Rightarrow(a+b)^2-(c+d)^2=(a-b)^2-(c-d)^2$$ Hence we have $$(a+b+c+d)(a+b-c-d)=(a-b+c-d)(a-b-c+d)$$ Now note that $|a+b+c+d|>|a-b+c-d|$ and $|a-b-c+d|$. If $(a+b+c+d)$ was prime then it must divide one of $(a-b+c-d)$ or $(a-b-c+d)$, which is not possible.

$\endgroup$
5
  • 2
    $\begingroup$ +1. Beautiful. Though this argument won't work (as it is) for $a,b,c,d \in \mathbb{Z}^+$. $\endgroup$
    – user17762
    Commented May 6, 2013 at 15:51
  • 4
    $\begingroup$ It's not hard to show a slightly simpler identity: $a(a+b+c+d)=(a+c)(a+d)$, with the result following from there by a similar size argument. $\endgroup$ Commented May 6, 2013 at 16:01
  • $\begingroup$ @user17762 It's not clear to me what is wrong with the proof in your eyes. $\endgroup$ Commented May 6, 2013 at 16:39
  • 1
    $\begingroup$ @ThomasAndrews I think he was getting at the fact that one (or both) of $a-b+c-d$ or $a-b-c+d$ may be $0$, in which case $a+b+c+d$ would divide it even if it were prime. Of course, in that case $a,b$ is the same as $c,d$ modulo reordering, so the sum is divisible by 2 and the result still holds. $\endgroup$
    – jerry
    Commented May 6, 2013 at 21:08
  • $\begingroup$ Yeah, if $a+b-c-d=0$ then $a+b+c+d=2(a+b)$ is not prime. @jerry $\endgroup$ Commented May 6, 2013 at 21:33
6
$\begingroup$

From $ab=cd$, We may assume $a=\frac{cd}{b}$. So $M=a+b+c+d = \frac{cd}{b}+b+c+d = \frac{(b+c)(b+d)}{b}$ and so $bM=(b+c)(b+d)$ and $M|(b+c)(b+d)$. We assume that $M$ is not composite, so it is prime. Now we may know that either $b+c$ or $b+d$ is divisible by $M$. So $M\leq b+c$ or $M\leq b+d$ which both result in contradiction because $M=a+b+c+d > b+c$ or $b+d$. So our assumption was wrong and $M$ is a composite number.

$\endgroup$
2
$\begingroup$

Hint: Plug $a=\frac{cd}{b}$ into the sum to get

$$\frac{(b+c)(b+d)}{b}$$

which cannot be prime.

$\endgroup$
5
  • 1
    $\begingroup$ Why can you assume that? $\endgroup$ Commented May 6, 2013 at 15:57
  • $\begingroup$ It may not be correct if $b+d$ was not divisible by $b$. $\endgroup$
    – CODE
    Commented May 6, 2013 at 16:00
  • $\begingroup$ @CODE: See the edit. $\endgroup$ Commented May 6, 2013 at 16:04
  • $\begingroup$ Dear @Thomas Andrews: I added the word hint into the body. $\endgroup$ Commented May 6, 2013 at 16:09
  • $\begingroup$ @Thomas Andrews: thanks, edited! $\endgroup$ Commented May 6, 2013 at 17:44
2
$\begingroup$

Write $p=a+b+c+d$ and say $p$ is prime. Then we have $$ab=c(p-a-b-c)$$ so $$(a+c)(b+c) = cp$$ which means that $$p\mid a+c\;\;\;\;{\rm or}\;\;\;\;p\mid b+c$$ in 1st case we get $p=a+b+c+d\leq a+c$ a contradiction. The same contradiction we get in the second case. So $p$ must be composite.

$\endgroup$
1
  • $\begingroup$ Duplicate of answer posted 5 years prior. Please check other answerS before posting. $\endgroup$ Commented Jun 14 at 18:00
2
$\begingroup$

Call the sum $\,f.\ $ Then $\ af = a^2 + \!\overbrace{ab}^{\Large cd}\!+ac+ad = \overbrace{(a+c)}^{\large M}\,\overbrace{(a+d)}^{\large N}\,$

By unique factorization $\, a\mid MN\,\Rightarrow\,a = mn,\,\ m\mid M,\, n\mid N,\,$ thus

$\ f = \dfrac{MN}a = \dfrac{M}m\dfrac{N}n.\ $ Each factor is $>1\,$ by $\,m,n \le a < M,N$.

$\endgroup$
1
  • $\begingroup$ Imported from a deleted question, where $\,f = a^2+b^2+c^2+d^2,\,$ so $\,a^2f = (a^2+c^2)(a^2+d^2)\,$ so the same proof as above works. $\endgroup$ Commented Jan 9, 2022 at 13:07
1
$\begingroup$

Hint:

$ab$ has to have at least $3$ prime factors.(If $a,b,c,d$ are distinct naturals)

$ab=p_1p_2p_3\dots p_n=cd$

$a=p_1p_2 \dots p_j$

$b=p_{j+1} \dots p_n$

$c=p_kp_{k+1} \dots p_l$

$d=p_1p_2 \dots p_{k-1}p_{l+1}p_{l+2} \dots p_n$

$\endgroup$
2
  • $\begingroup$ Who says they have to be distinct? Take, for example, $a=b=2, c=4, d=1$. $\endgroup$
    – jerry
    Commented May 6, 2013 at 21:29
  • $\begingroup$ None says they have to be distinct. You have a more general case if you distinct numbers. $\endgroup$
    – Inceptio
    Commented May 7, 2013 at 3:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .