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