0

There is a discussion in my book that, despite my best efforts, I was unable to understand. The problem asks:

Let $n$ and $d$ be positive integers. How many positive integers not exceeding $n$ are divisible by $d$?


enter image description here

I understood everything except the part where the floor function is applied. I know that if an integer is divisble by $d$, then it is of the form $dk$ for some integer $k$ by definition of divisibility. I also understand that because $n$ and $d$ are positive integers, $k$ must be a positive integer, so $dk > 0$. "Not exceeding $n$" translates to $\leq n$.

But what is the logic behind the floor function? I know what it does: it returns the greatest integer less than or equal to the input. But how does using it allow us to determine how many such positive integers fit the given criteria?

Please try to keep your answer as simple as possible. I know most of you guys are professional mathematicians and/or experts, but I'm easily confused :)

Aleksandr Hovhannisyan
  • 2,983
  • 4
  • 34
  • 59

3 Answers3

4

Let's do a simple example

Suppose $n=16$ and $d=3$. Then $16/3$ is not a whole number, but if we take the floor, then it is $5$. And indeed, there are $5$ positive integers not exceeding $7$ that are divisible by $3$: $3,6,9,12,15$. That is, you get: $3,6,9,12,15,18$ (oh no, wait, $18$ exceeds $16$, so it stops at $15$). Put differently, you get $1\cdot 3, 2\cdot 3, 3\cdot 3, 4\cdot 3, 5\cdot 3$, and that's it, since $6 \cdot 3$ exceeds $16$. But the $5$ is exactly what the floor of $16/3$ gives you.

A little more general: the positive integers not exceeding $n$ but divisible by $d$ are $d,2d,3d,...$. Now, if $n=kd$ for some whole number $k$, then it ends nicely in $n$: $d,2d,3d,...,kd$. But if $n/d$ is not a whole number, then $n=kd+s$ with $s$ some number between $0$ and $d$, so you still you get $d,2d,3d,...,kd$, as the next one $(k+1)d$ would exceed $n$. So you get $k$ divisors, and $\lfloor n/d \rfloor = k$

Bram28
  • 100,612
  • 6
  • 70
  • 118
0

Hint: Consider $n=100$ and $d=7$. One can ask to find the number of multiples of $7$ between $0$ and $100$. How would you find it?

farruhota
  • 31,482
0

Expanding on some of the previous answers, again let $k$,$d$, and $n$ be positive integers and consider the positive multiples of $d$ not exceeding $n$: $d, 2d, ..., kd$ where $kd$ is the largest multiple of $d$ not exceeding $n$. Then, $kd\le n$. Now, it helps to look at the exact definition of the greatest integer function (i.e. the floor function). Let $x$ be any real number and $m$ be an integer. Then $m = \lfloor x \rfloor \iff m\leq x \lt m+1$. Well, we said $kd$ is the largest integer multiple of $d$ not exceeding $n$ so surely $(k+1)d$, also an integer multiple of $d$, is strictly greater than $n$, or else we would have a contradiction. So then we have $kd\leq n \lt(k+1)d$. Now divide each term in the inequality by $d$ and you get $k\leq n/d\lt (k+1)$. By the definition of the greatest integer function, it follows that $k=\lfloor n/d\rfloor$.

Display name
  • 829