# Error in finding Solution for positive Diophantine equation

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

• Just a language note: "Diophantine equation" is not a technique, it is a class of problems. Feb 28, 2013 at 16:49
• I think it should $\frac{2c}7-\frac c4\ge 1$ Also, $c=4x+7y\ge 4+7=11?$ Feb 28, 2013 at 16:54
• 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. Feb 28, 2013 at 16:55
• @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? Feb 28, 2013 at 17:01
• 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. Feb 28, 2013 at 17:31

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

• shouldn't it be 4(x-1) + 7(y-1) = c - 11? Feb 28, 2013 at 18:20
• yes I think its a typo, you wrote 7(x-1) instead of 7(y-1). Feb 28, 2013 at 18:30
• (Fixed, and added the last step to the general answer.) @rishabh Feb 28, 2013 at 18:52
• 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. Feb 28, 2013 at 19:00

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$

• 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? Feb 28, 2013 at 17:28

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.

• 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. Mar 1, 2013 at 13:41