0
$\begingroup$

Complete Question:

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$

$\implies ar-b(n+1)=0$

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?

Many Thanks!

$\endgroup$
1
$\begingroup$
  1. I don't see why $nb\equiv -b+1 \mod a$ and $nb\equiv -b \mod a$ imply $b(n+1)-ar=1$ and $b(n+1)-ar=0$ for some $r$. It should be $b(n+1)-ar=1$ and $b(n+1)-as=0$ for some $r,s$ with $r$ and $s$ not necessarily equal.

  2. Yes, the Frobenius number for two numbers $a$ and $b$ is exactly $ab-a-b$, as you said. This is the case $n=2$ at the wikipedia page. This formula was discovered by James Joseph Sylvester in 1884.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.