2
$\begingroup$

I need to find minimum value of c above which there always exists a non-negative solution for the equation

$$4x + 7y = c$$ I tried using Diophantine equation but I am not able to find the mistake in my approach, could someone please point out? :

$$4x + 7y = c$$ where $x,y\geq 0$ and $GCD(x,y) = 1$.

$x = 2c$ and $y = -c$ satisfies the above equation.

Now $x_0 = 2c - 7t$ and $y_0 = -c + 4t$ (Diophantine equation solution)

$$2c - 7t \geq 0\implies t \leq 2c/7$$

Similarly

$$t\geq c/4$$

therefore $2c/7 - c/4 \geq 0$ which gives $c \geq 28$ but I know the answer for this is $18$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Just a language note: "Diophantine equation" is not a technique, it is a class of problems. $\endgroup$ – Thomas Andrews Feb 28 '13 at 16:49
  • 1
    $\begingroup$ I think it should $\frac{2c}7-\frac c4\ge 1$ Also, $c=4x+7y\ge 4+7=11?$ $\endgroup$ – lab bhattacharjee Feb 28 '13 at 16:54
  • $\begingroup$ But you really just need an integer between $c/4$ and $2c/7$, which can happen if their difference is between $0$ and $1$, too. It's certainly the case that for $c\geq 28$ you can always find a solution. $\endgroup$ – Thomas Andrews Feb 28 '13 at 16:55
  • $\begingroup$ @ThomasAndrews yes there always exist a solution for c>= 28 but it looks it also holds for c>= 18, so does this approach not necessarily give the minimum value or am I doing something wrong? $\endgroup$ – Rishabh Feb 28 '13 at 17:01
  • 1
    $\begingroup$ The standard argument about the largest number not representable is not manipulation of the inequalities for $t$. Those are too coarse: a gap of $1$ is sufficient but not necessary. The argument above can be supplemented by checking numbers $27, 26,\dots$. Or one can use a different proof that does not come from the inequalities. $\endgroup$ – André Nicolas Feb 28 '13 at 17:31
1
$\begingroup$

Lemma: If $x,y$ are real and $y-x>1$ then there is an integer $t$ such that $x<t<y$.

I'll let you prove that.

So your argument actually shows that if $c\geq 29$ then $2c/7-c/4>1$, and therefore there is a solution to $4x+7y=c$ with $x,y>0$. Then $4(x-1)+7(y-1)=c-11$ has a solution, and hence if $c\geq 18$, solve $4x_0+7y_0=c+11$ with $x_0,y_0>0$, and then $x=x_0-1$ and $u=y_0-1$ is a non-negative solution to $4x+7y=c$.

Note, this does not prove that $18$ is the smallest - to do that, you have to show that $4x+7y=17$ has no non-negative solution, or, equivalently, that there is no integer in the range $[17/4,34/7]$.

This also shows you how you get the coin problem result. If $a,b$ are relatively prime, first show that if $c\geq ab+1$, then $ax+by = c$ has a positive solution. But that means that if $c\geq ab+1 - a - b = (a-1)(b-1)$ then $ax+by=c$ has a non-negative solution.

And then, again, you need to show that there is no solution when $c=(a-1)(b-1)-1=ab-a-b$. But that can be done as follows. We can quickly show that $$a(b-1) + b(-1)= ab-b-a$$ so any integer solution to $ax+by=ab-b-a$ must be of the form: $$x_0 = b-1 - bt, y_0=-1+at$$

But if $x_0=b-1-bt\geq 0$ then $t<1$ and if $y_0=-1+at\geq 0$ then $t>0$. There is no integer between $0$ and $1$, so there is no non-negative solution to $ax+by= ab-a-b$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ shouldn't it be 4(x-1) + 7(y-1) = c - 11? $\endgroup$ – Rishabh Feb 28 '13 at 18:20
  • $\begingroup$ yes I think its a typo, you wrote 7(x-1) instead of 7(y-1). $\endgroup$ – Rishabh Feb 28 '13 at 18:30
  • $\begingroup$ (Fixed, and added the last step to the general answer.) @rishabh $\endgroup$ – Thomas Andrews Feb 28 '13 at 18:52
  • $\begingroup$ Thanks a lot. also a small typo in: "that there is no integer in the range [17/4,34/4]" must be [17/4,34/7] while proving that 18 is the smallest number. $\endgroup$ – Rishabh Feb 28 '13 at 19:00
1
$\begingroup$

You are correct that $x=2c, y=-c$ is a solution, but then when you say $x_0=2c-7t, y_0=-c+4t$ you are adding in the same number of $4$'s that you remove $7$'s

The coin problem shows the maximum unrepresentable number is $4\cdot 7 -4-7=17$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Actually I am reading "Elementary Number Theory" by David Burton and it has a theorem which stated the solution (if it exists) for ax + by = c is x = x0 + (b/d) t, y = y0 - (a/d) t, given x0 and y0 is any particular solution of the equation. Am I missing here something? $\endgroup$ – Rishabh Feb 28 '13 at 17:28
0
$\begingroup$

Here is a simple proof. By the theorem you quote in your comment to Ross's answer, we know that all of the solutions of $\rm\:N\ =\ 4\ X + 7\ Y\:$ arise from adding or subtracting multiples of $\rm\:(-7,4)\:$ to any particular solution $\rm\:(X,Y).\:$ Thus we may normalize any representation $\rm\ N\ =\ 4\ X + 7\ Y\ $ so that $\rm\ 0 \le X \le 6,\: $ by adding some integral multiple of $\rm\ (-7,4)\ $ to $\rm\:(X,Y),\:$ i.e. by choosing $\rm\,K\,$ so that $\rm\:(X,Y)+K(-7,4)\, =\, (X\!-\!7K,\,Y\!+\!4K)\:$ has $\rm\:0\le X\!-\!7K \le 6.\:$ Then we observe

Lemma $\rm\ \ N \,=\, 4\, X\! + 7\, Y\ $ for some integers $\rm\ X,Y \ge 0\, $ $\iff$ its normalization has $\rm\: Y \ge 0\:$.

Proof $\rm\ \ (\Rightarrow)\ \ $ If $\rm\ X,Y \ge 0\ $ then normalization adds $\rm\:(-7,4)\:$ zero or more times (in order to get $\rm\:0 \le X \le 6),\ $ and this preserves the condition $\rm\: Y \ge 0\:.\ $ $\ (\Leftarrow)\ \ $ Conversely if the normalization has $\rm\: Y < 0\:,\ $ then $\rm\:N\:$ has no representation with $\rm\ X, Y \ge 0\:,\: $ because to shift $\rm\: Y > 0\: $ requires adding $\rm\ (-7,4)\ $ at least once, which (since $\rm\:0\le X\le 6),\:$ shifts $\rm\: X < 0\:.\ $ QED

Finally, since $\rm\ 4\,X\! + 7\, Y\ $ is increasing in both $\rm\: X,Y\:,\ $ it is clear that the largest non-representable number $\rm\: N\:$ has normalization $\rm\: (X,Y)\ =\ (6,-1)\:,\: $ corresponding to $\rm\ N\ =\ 4\cdot 6 - 1\cdot 7\, =\, 17.$

Precisely the same argument works also for the general case. This classic problem is known by a great variety of aliases, e.g. postage stamp problem, Sylvester/Frobenius problem, Diophantine problem of Frobenius, Frobenius conductor, money changing, coin changing, change making problems. See also: h-basis and asymptotic bases in additive number theory, integer programming algorithms and Gomory cuts, knapsack problems and greedy algorithms, etc.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Could you please explain this point "since 4X+7Y is increasing in both X,Y, it is clear that the largest non-representable number N has normalization (X,Y) = (6,−1)".I can't understand how to find normalization. $\endgroup$ – Rishabh Mar 1 '13 at 13:41

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.