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.

Prove that there are exactly

$$\displaystyle{\frac{(a-1)(b-1)}{2}}$$

positive integers that cannot be expressed in the form

$$ax\hspace{2pt}+\hspace{2pt}by$$

where $x$ and $y$ are non-negative integers, and $a, b$ are positive integers such that $\gcd(a,b) =1$.

share|improve this question
2  
Note that the question requires $ax+by$ to be positive and $x,y$ to be nonnegative. –  Martin Argerami Feb 22 '12 at 23:48
    
@anon $x,y$ must be non-negative. –  azarel Feb 22 '12 at 23:49
    
In other words, if you have 3-coins and 5-cent coins, there are exactly four positive numbers of cents that you can't pay. (Apparently 1, 2, 4, and 7.) –  Michael Hardy Feb 23 '12 at 0:14
    
@MartinArgerami : What must be positive is $a$ and $b$, not $ax+by$. In other words, the denominations of the coins are positive, but the number of coins of a particular denomination used in a particular payment may be zero. –  Michael Hardy Feb 23 '12 at 0:16
    
@Michael Hardy: since zero is not a positive integer, it shouldn't be counted (i.e. $x=y=0$ is not allowed, as per the question): "Prove that there are exactly ... positive integers that cannot be expressed... " –  Martin Argerami Feb 23 '12 at 0:41
show 3 more comments

3 Answers

Hints: Prove

If $ax+by=c$, and $ax'+by'=c$, then $b$ divides $x-x'$, and $a$ divides $y-y'$, and $(x-x')/b=(y'-y)/a$.

$n$ can be expressed if and only if $((a-1)(b-1)/2)-1-n$ can't.

share|improve this answer
    
I could prove that $$ab \hspace{2pt}-\hspace{2pt}a\hspace{2pt}-\hspace{2pt}b$$ is the largest integer which cannot be expressed as $$ax\hspace{2pt}+\hspace{2pt}by$$ But cannot do the second part (I still don't understand Gerry's Hint) –  Sam Feb 23 '12 at 0:56
    
(1) If you want me to see your comment, you have to put @Gerry in it. (2) I gave two hints. Which one don't you understand? –  Gerry Myerson Feb 25 '12 at 5:24
add comment

It is well known that any number $\ge (a-1)(b-1)$ is representable.

The number of numbers $c$ such that $0 \lt c \lt ab$ which are representable correspond exactly to the number of lattice points in the region

$ax + by \lt ab$, $x \ge 0$, $y \ge 0$

This is because if $ax + by = ax' + by'$, then $x-x'$ is divisible by $b$, which cannot happen in the region, so two lattice points represent different numbers (and vice-versa).

A straigthforward counting argument now gives what you seek. Note, you would need to do some subtraction to get the count of numbers that are not representable, since the above lattice points count the numbers that are representable.

share|improve this answer
    
You are not reading the question properly, it is not saying $$\frac{(a-1)(b-1)}{2}$$ to be represented. It says THERE ARE EXACTLY $$\frac{(a-1)(b-1)}{2}$$ positive integers that cannot be represented as $$ax+by$$ form –  Sam Feb 23 '12 at 1:27
    
@Sam: I think I am reading it properly (I consider NOT REPRESENTED only). What mistake did you find? –  Aryabhata Feb 23 '12 at 1:27
    
Sorry Aryabhata. –  Sam Feb 23 '12 at 1:43
1  
@Sam: You don't have to apologize! –  Aryabhata Feb 23 '12 at 1:45
add comment

Call an integer bad if it cannot be represented as an integer combination of $a$ and $b$ with non-negative coefficients. There are $(a-1)(b-1)$ non-negative integers less than $(a-1)(b-1)$, and you know that all of the of the bad integers are among them. Take a look at a simple example. Suppose that $a=4$ and $b=7$, so that the bad integers must lie between $0$ and $17$ inclusive.

$$\begin{array}{r|c} \text{Good}:&0&16&15&14&4&12&11&7&8\\ \hline \text{Bad}:&17&1&2&3&13&5&6&10&9 \end{array}$$

Notice that the numbers in each column add up to $17=(a-1)(b-1)-1$. A little experimentation will suggest that this is a general phenomenon: if $b=(a-1)(b-1)-1$ is the largest bad integer, and $0\le n\le b$, then exactly one of $n$ and $b-n$ is bad. If you can prove this, you’ll have as an immediate consequence that $\frac12(b+1)=\frac12(a-1)(b-1)$ integers are bad.

It’s easy to see that $n$ and $b-n$ cannot both be good: that would make $b$ good. Thus, you want to show that they also cannot both be bad. For this you’ll probably want to use what you know about the general solution to the Diophantine equation $c=ax+by$. If you get stuck, take a look at the proof of Lemma 3 in this paper by Mike Spivey; it isn’t exactly what you want, but it’s very close and should give you the ideas that you need to complete the argument.

share|improve this answer
    
Thanks Brian. I like your explanation. –  Sam Feb 23 '12 at 1:31
    
I think I understand Aryabhata's statement. Originally I posted the question correctly, someone pointed out it should be be positive not non-negative. Therefore I edited the question back to the correct form. I understand there is more than one way to solve a Mathematical problem, but some like one approach and some would prefer other ways. I like Brian's suggestion anyways. –  Sam Feb 23 '12 at 1:41
add comment

Your Answer

 
discard

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

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