Let $m$ be a positive integer. Show that for every real number $x \ge 1$, the number of multiples of $m$ in the interval $[1, x]$ is $\lfloor \frac{x}{m} \rfloor$; in particular, for every integer $n \ge 1$, the number of multiples of $m$ among $1, ..., n$ is $\lfloor \frac{n}{m} \rfloor$.

First, every real number $x$ can be formulated as the sum of an integer and an $\epsilon \in \mathbb{R} \text{ where } 0 \le \epsilon \lt 1$. Using the "division with remainder property" (which says for every $a, b \in \mathbb{Z}$ with $b > 0$, there exist unique $q, r \in \mathbb{Z}$ such that $a = b \cdot q + r$ and $0 \le r < b$), there exist $q,r \in \mathbb{Z}$ such that:

$$\begin{aligned} x = q \cdot m + r + \epsilon \end{aligned}$$

where $q \ge 0$ and $0 \le r < m$

Obviously, $q$ is the number of multiples of $m$ in the interval $[1, x]$. To find $q$, we can start with dividing both sides by $m$:

$$\begin{aligned} \frac{x}{m} &= q + \frac{r + \epsilon}{m} \\ \lfloor \frac{x}{m} \rfloor &= \lfloor q + \frac{r + \epsilon}{m} \rfloor \\ \end{aligned}$$

Observe $0 \le r + \epsilon < m$, so

$$\begin{aligned} \lfloor \frac{x}{m} \rfloor &= q \\ \end{aligned}$$

Since every integer $n$ is also a real number, the second statement is obviously true by substituting $x$ by $n$ in the first statement.

$\Box$

# posted by rot13(Unafba Pune) @ 12:30 AM