For each of the following values of ($a,b$), find the largest number that is not of the form $ax+by$ with $x\geq 0$ and $y \geq 0$.

Question

For each of the following values of ($a,b$), find the largest number that is not of the form $ax+by$ with $x\geq 0$ and $y \geq 0$.

$(i) (a,b) = (3,7)$

$(ii) (a,b) = (5,7)$

$(iii) (a,b) = (4,11)$

I know how to compute numbers of these forms (clear), but have no idea how to generate one that is not of that form. Then, of those, which is the largest? More importantly, how do I prove its the largest?

Answer 1

To help you, let us have a look on how it works with the first example. With $x\geq0$ and $y\geq0$, what are the smallest numbers $3x+7y$ that you can generate ?

• Clearly 0
• The next smallest one is 3, using $x=1$ and $y=0$
• you can't generate 4 or 5 so the next one is $6=3\times2+7\times0$
• the next one is obviously 7
• 8 is not possible (check it out) so next one is $9=3\times3+7\times0$
• $10=3\times1+7\times1$
• 11 is not possible (you should now see why)
• $12=3\times4+7\times0$, $13=3\times2+7\times1$ and $14=3\times0+7\times2$ are 3 consecutive numbers, therefore every number from this point can be generated (do you see why ? and in particular do you understand why it is important to find 3 consecutive numbers one can generate ?).

The answer for point (i) is thus 11. You should manage with (ii) and (iii) easily.

Answer 2

For the first one, for example, you can see that if $n$ is an integer, $n$, $n-7$ or $n-14$ is a multiple of 3 (by looking what happens modulo 3). So, if $n\geq 14$, you can write $n-7.x=3.y$ with $x=0, 1,$ or $2$ and $y\geq 0$. Then, the number you look for is between $1$ and $13$ and you can look one by one and take the largest.

For the other cases, you can try the same method, there will just be more cases to consider, I think (because a is larger).

I have an other idea, I write it in a few minutes.

(After verification, the idea is correct, but it is too much difficult to be interesting for this question).