4
$\begingroup$

This might sound trivial, but I am wondering why, for example if you do:

$\lfloor10/8\rfloor = 1 \implies 1$ number $[1,10]$ divisible by $8$: $\{8\}$
$\lfloor10/3\rfloor = 3 \implies 3$ numbers $[1,10]$ divisible by $3$: $\{3,6,9\}$
$\lfloor23/4\rfloor = 5 \implies 5$ numbers $[1,23]$ divisible by $4$: $\{4,8,12,16,20\}$
$\ldots$ etc.

Why is this true?

$\endgroup$
  • $\begingroup$ Hint: How many square numbers are $\le$ than $100^2$? How about $101^2 - 1$? $\endgroup$ – user1502040 Feb 28 '18 at 12:27
  • $\begingroup$ I wouldn't say the division in itself gives you the list of the divisible numbers, just their amount. (of course getting the numbers is trivial.) $\endgroup$ – ilkkachu Feb 28 '18 at 13:56
  • $\begingroup$ Well of course. I just added the set for the sake of the question. $\endgroup$ – udpcon Feb 28 '18 at 17:28
11
$\begingroup$

Let's make it general. If we are seeking the number of natural numbers divisible by say $y$ up to a number say $x$, then $\lfloor x/y\rfloor$ is the number that we are seeking because those numbers are $1y,\ 2y,\ 3y, ..., ay\ $ where $ay$ is the biggest number divisible by $y$ with $ay \le x$. Then notice that

  • If $ay = x$, we directly have $a = \frac{x}{y} = \lfloor x/y\rfloor$ so we have $a$ many such numbers (from $1y$ to $ay$).

  • If $ay < x$, we have $x-ay = k$ with $k < y$, implies $a = \frac{x-k}{y}$ so $a = \lfloor x/y\rfloor$ again because we know that $k < y$. So again, we have $a$ many such numbers (again from $1y$ to $ay$).

$\endgroup$
  • $\begingroup$ Very nice explanation, thank you. $\endgroup$ – udpcon Feb 28 '18 at 2:04
  • 1
    $\begingroup$ You're welcome :) $\endgroup$ – ArsenBerk Feb 28 '18 at 2:06
14
$\begingroup$

Because of division. What you're essentially doing when you do:

$$10\over 3$$

Is asking, how many times does $3$ go into $10$? The answer is $3.\bar3$, but the leading whole $3$ tells you that there were $3$ whole times plus some fractional part. Since $3$ went into $10$ three whole times, there must be $3$ numbers smaller than or equal to $10$ that are multiples of $3$. Flooring the division just gives you the whole part.

$\endgroup$
  • $\begingroup$ Very intuitive! thank you. $\endgroup$ – udpcon Feb 28 '18 at 17:30
4
$\begingroup$

Using the division lemma, the division $b/a$ gives us a sum

$$b = qa + r$$

with $0 \le r < a$. Now there are exactly $q$ multiples of $a$ less than or equal to $b$; namely, they are $a, 2a, 3a, \dots, qa$. Furthermore,

$$\lfloor \frac b a \rfloor = \lfloor q + \frac r a\rfloor = q$$ since $0 \le r/a < 1$.

$\endgroup$
1
$\begingroup$

Assume that $x$ and $y$ are positive integers. Then

$ 1y < 2y < \cdots < ny \le x < (n+1)y $ if and only if $\left \lfloor \dfrac xy \right \rfloor = n$

$\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.