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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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