5
$\begingroup$

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

  • 0
    @MichaelHardy: I fail to see your point. Read the question. It says *positive integers* that cannot be expressed... Since $0$ *can* be expressed as $ax+by$, its presence or absence is irrelevant, as it is not one of the numbers that should be counted. So it's either the cardinality of $\mathbb{N}\setminus\{ax+by: x,y \text{ non-negative integers not both null}\}$, or the cardinality of $(\mathbb{N}\cup\{0\})\setminus\{ax+by: x,y \text{ non-negative integers}\}$: it's the same.2012-02-29

3 Answers 3

3

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.

  • 0
    (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?2012-02-25
2

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.

  • 0
    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.2012-02-23
1

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.

  • 1
    @Sam: You don't have to apologize!2012-02-23