Given relatively prime positive integers $a,b>1$, how many positive integers are there which are not non-negative integer combination sum of $a,b$?

Question

Let $a,b>1$ be relatively prime positive integers. I know that $ab-a-b$ is the largest positive integer which can not be written as a sum of non-negative integer combination of $a,b$. My question is : can we explicitly determine how many positive integers are there which can not be written as a non-negative integer combination of $a,b$ ?

Answer 1

Let $N = ab$, we count the number of integers $0\leq t \leq N$ that can be written as $$ t = ma+nb $$ such that $m,n\geq 0$. Let there be $R$ such numbers. Since the largest non-representable (positive)-integer is $ab-a-b$, all non-representable numbers are in $[0,N]$ and hence we know there are $N+1 - R$ of them.

If $n\geq a$, then we replace it with $$ ma+nb = (m+b)a + (n-a)b = m'a+n'b $$ So with repeated application we may assume that $0\leq n < a$. We require $$ 0 \leq ma+nb \leq N \implies 0 \leq ma \leq N-nb = (a-n)b $$ Hence we get the bounds of $m$ as $$ 0 \leq m \leq \left \lfloor \frac{(a-n)b}{a}\right \rfloor $$ This means the number of integers we can represent for a given $n$ is $ \left \lfloor \frac{(a-n)b}{a} \right \rfloor + 1 $. Now summing this over all possibilities $n=0,1,\dots a-1$, the number of representable integers $R$ is $$ \begin{align*} R = \sum_{k=0}^{a-1} \left\lfloor \frac{(a-k)b}{a} \right\rfloor +1 &= \left\lfloor \frac{(a)b}{a} \right\rfloor + \left\lfloor \frac{(a-1)b}{a} \right\rfloor + \cdots + \left\lfloor \frac{(2)b}{a} \right\rfloor + \left\lfloor \frac{(1)b}{a} \right\rfloor + a\\ R &= a + b + \sum_{k=1}^{a-1} \left\lfloor \frac{kb}{a} \right\rfloor \\ \end{align*} $$ Next we observe that if $a$ does not divide $kb$, then for some integer $t$ $$ t < \frac{kb}{a} < t+1 \Longleftrightarrow -t-1 < \frac{-kb}{a} < -t $$ In particular this applies for $1\leq k\leq a-1$, since $\gcd(a,b)=1$ and $a>1$. We use the inequalities to obtain $$ \left \lfloor \frac{-kb}{a}\right \rfloor = -t-1 = - \left \lfloor \frac{kb}{a}\right \rfloor -1, $$ This lets us get another equation of $R$ as $$ \begin{align*} R = \sum_{k=0}^{a-1} \left\lfloor \frac{(a-k)b}{a} \right\rfloor +1 &= \sum_{k=0}^{a-1} \left\lfloor \frac{-kb}{a} \right\rfloor + b + 1 \\ &= a(b+1) + \sum_{k=0}^{a-1} \left\lfloor \frac{-kb}{a} \right\rfloor\\ &= a(b+1) + \sum_{k=1}^{a-1}\left\lfloor \frac{-kb}{a} \right\rfloor \\ &= a(b+1) + \sum_{k=1}^{a-1}-\left\lfloor \frac{kb}{a} \right\rfloor -1\\ R &= ab + 1 - \sum_{k=1}^{a-1}\left\lfloor \frac{kb}{a} \right\rfloor \end{align*} $$ Therefore adding both equations of $R$, we have $$ 2R = ab + a + b + 1 = (a+1)(b+1) $$ giving us $R=(ab+a+b+1)/2$. Notice that $R$ is not an integer if and only if $a,b$ are both even, which is not possible since $\gcd(a,b)=1$.

Finally, the number of integers considered is $ab+1$, so the number of integers not representable is $$ ab+1 - \frac{ab+a+b+1}{2} = \frac{ab -a - b+1}{2} = \frac{(a-1)(b-1)}{2} $$

Answer 2

Proposition. Let $a,b$ be relatively prime integers greater than $1,$ and let $m=ab-a-b.$
If $x\in\{0,1,2,\dots,m\},$ then exactly one of the two numbers $x$ and $m-x$ can be expressed as a linear combination of $a$ and $b$ with nonnegative integer coefficients.

It follows that exactly half the elements of $\{0,1,2,\dots,m\}$ can be expressed as nonnegative integral linear combinations of $a$ and $b;$ that is, there are exactly $\frac{m+1}2=\frac{(a-1)(b-1)}2$ numbers which cannot be so expressed.