Find, with proof, the smallest positive integer m ≥ 2 for which both of the following statements are true at the same time

Question

Find, with proof, the smallest positive integer m ≥ 2 for which both of the following statements are true at the same time:

• The equation 6x + 11y = m has no non-negative solutions.

• For any k > m, the equation 6x + 11y = k has at least one non-negative solution.

What I've got so far:

x = 2m + 11k

y = -m - 6k

my prof told me to solve for k first then find a range for m. x≥0 and y≥0 since no non-negative solutions 2m + 11k ≥ 0 and -m - 6k ≥ 0

not sure where to go from here.

Answer 1

First note that there is only one such $m$, there is no need to look for the smallest.

To show that all $k>m$ allow a non-negative solution, will be done by induction. But if we assume that we have a solution $6x+11y=k$ for some $k$, how can we show that there is a solution for $k+1$? If $y>0$, this is easy: just note that $2\cdot 6-11=1$, so letting $x'=x+2$ and $y'=y-1$, we find $6x'+11y'=k+1$. But if there is no solution with $y>0$, we must take $x'=x-u$ and $y'=v=y+v$ with $u,v>0$ and $11v-6u=1$. For example by trial and error, we find that the smallest suitable $u$ is $u=9$ (and then $v=5$). Thus

If $6x+11y=k$ is a solution for $k$ then we can find a solution $$6(x+2)+11(y-1)=k+1$$ if $y\ge 1$, and a solution $$6(x-9)+11(y+5)=k+1$$ if $x\ge 9$.

Also, as $6\cdot 8+0\cdot 11=48$, we have

If $k>48$ and there exists a solution $6x+11y=k$, then in this solution $x\ge 9$ or $y\ge1$

Hence for $k>48$ the induction step will always work. However, there is no solution for the first candidate $k=49$ because neither $49$, nor $38$, nor $27$, nor $16$, nor $5$ is a multiple of $6$. On the other hand, $50=6\cdot 1+4\cdot 11$. We conclude that $$m=49.$$