Let $a$ and $b$ be co-prime positive integers. What is the largest integer that cannot be expressed in the form $ma+nb$ with $m,n$ non-negative integers? Prove this.
Hi everyone, I know that this question has technically been asked before, but I have answered it myself (i think) and would just like to get some feedback on whether there are holes in my answer and to perhaps deepen my understanding of the question. So thanks in advance!
My lecturer basically gave me the hint to start me off, that I basically needed to prove for two co-prime integers $a,b$ that $ \space ab-a-b+1$ can be expressed with $\space m,n$ non-negative integers and that this cannot be done with $ \space ab-a-b$.
So with this hint, I have that:
$ma+nb = ab-a-b+1$
$\implies ma+nb = ab-a-b+1 (mod \space a)$
$\implies nb = -b+1 (mod \space a)$
$\implies ar = nb+b-1 $, rearranging gives:
$b(n+1)-ar = 1$
Now essentially repeating the above,
$ma+nb = ab-a-b$
$\implies ma+nb = ab-a-b (mod \space a)$
$\implies nb = -b (mod \space a)$
$\implies ar = nb+b = b(n+1) $, rearranging gives:
$b(n+1)-ar = 1$
But if $n=0$, we see that $an=b$, which is a contradiction. So $ab-a-b$ is the largest integer that cannot be expressed in the form $ma+nb$ with $m,n$ non-negative.
I have a few questions regarding my attempted solution.
1) Is the solution valid?
2) I am a little unclear on whether $b(n+1)-ar = 1$, can be considered in the form $ma+nb$ (since I have the minus in the middle, is this still valid?)
3) How the heck would I have even attempted the solution without the lecturer's hint? It seems to be related to http://en.wikipedia.org/wiki/Coin_problem , so is this just something that can be taken for granted?