# Number of positive integers that cannot be expressed as $ax+by$

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

-
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

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.

-
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

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.

-
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

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.

-
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
@Sam: You don't have to apologize! –  Aryabhata Feb 23 '12 at 1:45