Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
6  
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. –  Brian M. Scott Dec 31 '12 at 17:14
    
@xavierm02: $a$ and $b$ are required to be relatively prime. –  Brian M. Scott Dec 31 '12 at 17:19

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Gerry Myerson Dec 31 '12 at 23:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.