7
$\begingroup$

I was playing around with a few numbers.I noticed the following:

Given two coprime naturals $a$ and $b$,we can express a lot of integers in the form $xa+yb=d$ for $x,y\ge0$ and $x$ and $y$ are integers.

However, there are some others which I could not express in the form I just described.For example, if $a=7$ and $b=5$, I could not express 1,2,3,4,6,8,9,11,13,16,18 and 23 as above.There might be more of them.That brought to my mind a question.

Given two coprime positive integers $(a,b),a>1,b>1$,is the number of natural numbers which cannot be expressed in the form above finite? Can we exactly calculate how many of them exist?.

$\endgroup$
2
  • 6
    $\begingroup$ Every $d\ge(a-1)(b-1)$ can be so expressed; exactly half of the non-negative integers less than $(a-1)(b-1)$ can be so expressed. $\endgroup$ Dec 31, 2012 at 17:14
  • $\begingroup$ @xavierm02: $a$ and $b$ are required to be relatively prime. $\endgroup$ Dec 31, 2012 at 17:19

1 Answer 1

4
$\begingroup$

This is a special case of the Frobenius coin problem, also sometimes called the postage-stamp problem (though that name also refers to another problem) or, more recently, the McNugget problem. Sylvester proved that every $d\ge(a-1)(b-1)$ can be so represented and that exactly half of the non-negative integers less than $(a-1)(b-1)$ have such representations. This web page gives a proof of the theorem.

$\endgroup$
1
  • $\begingroup$ Looking at the $a=7$, $b=5$ example, you'll see that $d$ can be expressed if and only if $23-d$ can't. This is where the "exactly half" in Brian's answer comes from. $\endgroup$ Dec 31, 2012 at 23:11

You must log in to answer this question.