Error in finding Solution for positive Diophantine equation

Question

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

Answer 1

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

Answer 2

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$

Answer 3

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.