The questions goes as follows:

Let $a$ , $b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc - ab - bc - ca$ is the largest integer which cannot be expressed in the form $xbc + yca + zab$, where $x, y, z$ are non-negative integers.

My solution is something like this:

If $2abc - ab - bc - ca$ is expressible in the given form, then $2abc$ must be expressible in the same form $xbc + yca + zab$, but instead where $x, y, z$ are positive integers. Since a,b,c are arbitrary numbers which specify some conditions, assuming $a>b>c$ does not cause any loss in generality (or should it?) . So, now $2abc=c \times ab+b \times ca$. We must break $c$ and $b$ into smaller numbers to express $2abc$ in the required form, or in other words, we must have the relation $z_1 \times bc=x_1 \times ab+y_1 \times ca$ for some $x_1,y_1,z_1 \in N$. But both $ab,ac$ are greater than $bc$. Hence no such representation of $2abc$ exists. And since no such representations exist, $2abc - ab - bc - ca$ cannot be expressed in the form $xbc + yca + zab$, where $x, y, z$ are non-negative integers (because then it would imply $2abc$ be expressed in some form of our own,i.e., with natural numbers).

So is my solution correct? If not, then where does the fault lie in this proof? And please clear the doubt above (italicised above).

  • $\begingroup$ You actually showed the opposite of what you were trying to prove—the question asks to show that $2abc-ab-bc-ca$ is the largest non-representable number, and you showed that there is an even larger non-representable number, $2abc$. Clearly, a few things have gone wrong here. $\endgroup$ – Slade Oct 4 '14 at 13:07
  • $\begingroup$ Try $a=b=c=1$. Then $2abc$ is a combination of $ab$, $bc$, $ca$, so follow your proof through with those numbers to see where it goes wrong. $\endgroup$ – Slade Oct 4 '14 at 13:08
  • $\begingroup$ No. It seems that you misunderstood my process. I showed that $2abc$ cannot be expressed in the form $xab+ybc+zca$ where $x,y,z$ are positive integers. In the question we had to prove that $x,y,z$ are non-negative integers (for $2abc-ab-bc-ca$). Please go through the steps again. $\endgroup$ – user117913 Oct 4 '14 at 14:48
  • $\begingroup$ Your proof is unlikely to be correct since you never used the fact that $a$, $b$, and $c$ are pairwise relatively prime. Also, even if it were correct, you didn't show that the given number was the largest nonrepresentable number. $\endgroup$ – rogerl Oct 13 '14 at 16:44
  • $\begingroup$ For example, if $a=b=2$ and $c=1$, then $2abc-ab-bc-ac = 0$, which is clearly a linear combination of $ab$, $bc$, $ac$ with nonnegative coefficients. $\endgroup$ – rogerl Oct 13 '14 at 16:46

Your Answer

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

Browse other questions tagged or ask your own question.