Quantity of Positive Integers Divisible by Particular Integer
Jump to navigation
Jump to search
Theorem
Let $d$ be a positive integer.
Let $x \ge 1$ be a real number.
Then:
- $\ds \sum_{n \le x, \, d \divides n} 1 = \floor {\frac x d}$
That is:
- there are $\floor {\dfrac x d}$ natural numbers less than or equal to $x$ that are divisible by $d$.
Proof
Consider the sum:
- $\ds \sum_{n \le x, \, d \divides n} 1$
Note that a natural number $n \le x$ is divisible by $d$ if and only if:
- there exists a natural number $k$ such that $n = d k$.
So we are counting the natural numbers $k$ such that $d k \le x$.
That is, the natural numbers $k$ such that:
- $k \le \dfrac x d$
So:
\(\ds \sum_{n \le x, \, d \divides n} 1\) | \(=\) | \(\ds \sum_{k \le x/d} 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \floor {\frac x d}\) |
$\blacksquare$