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

  • 2
    Note that the question requires $ax+by$ to be positive and $x,y$ to be nonnegative.2012-02-22
  • 0
    @anon $x,y$ must be non-negative.2012-02-22
  • 0
    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.)2012-02-23
  • 0
    @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.2012-02-23
  • 0
    @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... "2012-02-23
  • 0
    Please don't yell. Using all caps is considered yelling.2012-02-23
  • 0
    @MartinArgerami : $x=0$ and $y=0$ are indeed allowed. Read the question. It said $a$ and $b$ are positive and $x$ and $y$ are _non-negative_.2012-02-29
  • 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
    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)2012-02-23
  • 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
    Thanks Brian. I like your explanation.2012-02-23
  • 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.

  • 0
    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$$ form2012-02-23
  • 0
    @Sam: I think I am reading it properly (I consider NOT REPRESENTED only). What mistake did you find?2012-02-23
  • 0
    Sorry Aryabhata.2012-02-23
  • 1
    @Sam: You don't have to apologize!2012-02-23