# 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$?

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

• @B.Goddard $a, b$ are assumed to be relatively prime. Also, the linear combinations here are assumed to have non-negative coefficients. That changes the problem quite a bit from the one you describe. – Arthur Jun 20 '18 at 13:11
• The most explicit I can get is a summation. If $a\lt b$ then there are: $$\sum_{k=1}^{a-1}\left\lfloor\frac{bk}{a}\right\rfloor$$ such numbers. Although you should definitely double-check this result. – N. Shales Jun 20 '18 at 16:19
• Having thought a bit more I further conjecture that the result simplifies to $$\frac{1}{2}(a-1)(b-1)\, .$$ – N. Shales Jun 20 '18 at 17:16
• @N.Shales your conjecture is correct: \begin{align*} R &= \sum_{k=1}^{a-1} \left\lfloor \frac{bk}{a} \right \rfloor\\ &= \sum_{k=1}^{a-1} \left\lfloor \frac{(a-k)b}{a} \right\rfloor \\ &= \sum_{k=1}^{a-1} b+\left\lfloor \frac{-kb}{a} \right\rfloor \\ &= \sum_{k=1}^{a-1} b-1-\left\lfloor \frac{kb}{a} \right\rfloor \\ &= (a-1)(b-1) - \sum_{k=1}^{a-1} \left\lfloor \frac{kb}{a} \right\rfloor \\ &= (a-1)(b-1) - R \end{align*} So that $2R = (a-1)(b-1)$. The key is the equality $\lfloor (-kb)/a\rfloor = -\lfloor kb/a \rfloor - 1$ which holds when $a$ does not divide $kb$. – Yong Hao Ng Jun 28 '18 at 8:20
• @N.Shales I saw it a few days ago but it took me a while before I found a not very involved solution to the floor-sum. – Yong Hao Ng Jun 29 '18 at 13:11

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