3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – Arthur Jun 20 '18 at 13:11
  • 1
    $\begingroup$ 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. $\endgroup$ – N. Shales Jun 20 '18 at 16:19
  • 1
    $\begingroup$ Having thought a bit more I further conjecture that the result simplifies to $$\frac{1}{2}(a-1)(b-1)\, .$$ $\endgroup$ – N. Shales Jun 20 '18 at 17:16
  • 2
    $\begingroup$ @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$. $\endgroup$ – Yong Hao Ng Jun 28 '18 at 8:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Yong Hao Ng Jun 29 '18 at 13:11
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy