Find the number of pairs of integers $(a,b)$ such that...

Question

Find the number of pairs of integers $(a,b)$ with $1\le a,b\le 2015$ such that $b+1$ divides $a$, and $b$ divides $2016-a$.

I have literally no idea of what to do with this problem, please help!

Answer 1

This may ultimately not prove to be terribly useful, but I thought I'd describe how I went about attacking the problem, report a formula I found, and do some examples that suggest a strikingly simple answer that I found a bit surprising.

To get started, $b+1\mid a$ implies $a=(b+1)k$ for some $k$, which means $b\mid2016-a$ implies $2016-k=bh$ for some $h$. Putting these together leads to

$$a=(b+1)(2016-bh)$$

The inequality $a\le2015$ is equivalent to

$${2015\over b+1}+{1\over b}\le h$$

and because $h$ is required to be an integer while the left hand side is never an integer, this is equivalent to

$$\Big\lfloor{2015\over b+1}+{1\over b}\Big\rfloor\lt h$$

On the other hand, the inequality $a\ge1$ requires $k\gt0$, which means $h\lt2016/b$. It's convenient, however, to allow $a=0$ as well, because this makes it possible to avoid cases while writing a single inequality with the floor function: $h\le\lfloor2016/b\rfloor$. Allowing $a=0$ adds only $\tau(2016)-1$ extra solutions, where $\tau(N)$ is the number of divisors of $N$ (the bound $b\le2015$ disallows the divisor $2016$).

All in all, we get a solution $(a,b)$ out of any pair $(b,h)$ with $1\le b\le2015$ and

$$\Big\lfloor{2015\over b+1}+{1\over b}\Big\rfloor\lt h\le\Big\lfloor{2016\over b}\Big\rfloor$$

This means the total number of solutions (including those with $a=0$) can be calculated as the sum

$$\sum_{b=1}^{2015}\left(\Big\lfloor{2016\over b}\Big\rfloor-\Big\lfloor{2015\over b+1}+{1\over b}\Big\rfloor\right)$$

This is an impressive-looking formula, but it's clearly almost completely worthless, because it offers no alternative but to compute all $2015$ terms and add them up. Nonetheless, it's worth looking at some small versions of the obvious generalization,

$$S(N)=\sum_{b=1}^{N}\left(\Big\lfloor{N+1\over b}\Big\rfloor-\Big\lfloor{N\over b+1}+{1\over b}\Big\rfloor\right)$$

Starting with the nearly trivial $S(1)=\lfloor2/1\rfloor-\lfloor((1/2)+(1/1)\rfloor=2-1=1$, we get

$$\begin{align} S(2)&=(3-2)+(1-1)=2\\ S(3)&=(4-2)+(2-1)+(1-1)=3\\ S(4)&=(5-3)+(2-1)+(1-1)+(1-0)=4\\ S(5)&=(6-3)+(3-2)+(2-1)+(1-1)+(1-1)=5\\ S(6)&=(7-4)+(3-2)+(2-1)+(1-1)+(1-1)+(1-0)=6 \end{align}$$

Hmm....

If this pattern holds up, then the answer to the OP's question is

$$2015-(\tau(2016)-1)=2016-\tau(2^9\cdot3^2\cdot7^1)=2016-10\cdot3\cdot2=1956$$

It'd be nice to prove that $S(N)=N$ for all $N$, and maybe it's not that hard to prove (if indeed it's true), but I, for one, have no idea how to go about it. Maybe someone else will -- or find some better answer altogether.