2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.