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?.

  • 0
    @xavierm02: $a$ and $b$ are required to be relatively prime.2012-12-31

1 Answers 1

4

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.

  • 0
    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.2012-12-31