# Proof Verification: The number of positive integers divisible by $d$ and less than or equal to $x$ is $\big \lfloor{\frac{x}{d}} \big\rfloor$

Here is the problem:

The number of positive integers less than or equal to $x$, where $x$ is a positive real number, that are divisible by the positive integer $d$ equals $\big\lfloor{\frac{x}{d}}\big\rfloor$.

I was wondering if the following proof is valid. I made this proof prior to reading the book's proof, which is definitely shorter than the one I wrote, but seems to follow the same idea. However, I think the book's proof is less clear as to why the result $\big\lfloor{\frac{x}{d}}\big\rfloor$ is true. I provided the book's proof after my own.

Consider the sequence of integers $1, 2, \dots, \lfloor{x}\rfloor, x$ where $x$ is a positive real number. Divide the sequence into $q$-subsequences of length $d$ to get

$$1, 2, \dots, d$$ $$d+1, d+2, \dots, 2d$$ $$.$$ $$.$$ $$.$$ $$(q-1)d+1, \dots, qd$$

Since $qd$ is the largest multiple of $d$, we know that

$$\lfloor{x}\rfloor = qd + r$$

where $0 \leq r < d$.

By the division algorithm, we define $q$ explicitly as

$$q = \bigg\lfloor{\frac{\lfloor{x}\rfloor}{d}}\bigg\rfloor = \Big\lfloor{\frac{x}{d}}\Big\rfloor$$

Consequently, the set $\{d, 2d, \dots, qd\}$ has precisely $q = \Big\lfloor{\frac{x}{d}}\Big\rfloor$ terms, as desired.

Book's Proof. The positive integers divisible by the positive integer $d$ are those integers of the form $kd$ where $k$ is a positive integer. The number of these that are less than $x$ is the number of positive integers $k$ with $kd \leq x$, or equivalently with $k \leq \frac{x}{d}$. There are $\big\lfloor{\frac{x}{d}} \big\rfloor$ such integers.

## 1 Answer

First, you’re right in thinking that it’s essentially the same idea. It’s also basically correct, but it could stand a bit of reorganization. Specifically, it would be better to begin by applying the division algorithm to $\lfloor x\rfloor$ and $d$. And if I were giving a proof more detailed than the one in the book, I’d probably also go into a bit more detail about the manipulation of the floor function. Making those changes but otherwise trying to stay as close as possible to your basic approach, I might end up with something like this:

The positive integers less than or equal to $x$ are precisely the integers $1,2,\ldots,\lfloor x\rfloor$. By the division algorithm there are unique integers $q$ and $r$ such that $\lfloor x\rfloor=dq+r$, and $0\le r<d$, so we can split these $\lfloor x\rfloor$ positive integers into $q$ blocks of $d$ integers each, possibly with a short block of $r$ integers left over: \begin{align*}&1,2,\ldots,d,\\&d+1,d+2,\ldots,2d,\\ &2d+1,2d+2,\ldots,3d,\\&\qquad\qquad\vdots\\&(q-1)d+1,(q-1)d+2,\ldots,qd,\\&qd+1,\ldots,qd+r\end{align*} The multiples of $d$ here are the integers at the ends of the first $q$ lines, namely, $d,2d,3d,\ldots,qd$. Clearly there are $q$ of them, so we need to show that $q=\left\lfloor\frac{x}d\right\rfloor$.

Let $\alpha=x-\lfloor x\rfloor$, the fractional part of $x$; of course $0\le\alpha<1$. Then $0\le r+\alpha<d$, so $$\left\lfloor\frac{x}d\right\rfloor=\left\lfloor\frac{dq+r+\alpha}d\right\rfloor=\left\lfloor q+\frac{r+\alpha}d\right\rfloor=q+\left\lfloor\frac{r+\alpha}d\right\rfloor=q\;,$$ as desired.