Floor of x+m over n/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m, n \in \Z$ such that $n > 0$.

Let $x \in \R$.


Then:

$\left\lfloor{\dfrac {x + m} n}\right\rfloor = \left\lfloor{\dfrac {\left\lfloor{x}\right\rfloor + m} n}\right\rfloor$

where $\left\lfloor{x}\right\rfloor$ denotes the floor of $x$.


Proof

First of all, subtract $\floor x$ from $x$ and add $\floor x$ to $m$.

This does not change either side of the claimed equality.



We now have:

$(1): \quad 0 \le x < 1$

and

$\floor x = 0$

Write:

$(2): \quad m = k n + r$

with $k \in \Z$ and $0 \le r \le n - 1$.

By $(1)$ and $(2)$:

$(3): \quad 0 \le r + x < n - 1 + 1 = n$


We have:

\(\displaystyle \floor {\dfrac {x + m} n}\) \(=\) \(\displaystyle \floor {\dfrac {x + r} n + k}\)
\(\displaystyle \) \(=\) \(\displaystyle k + \floor {\dfrac {r + x} n}\)
\(\displaystyle \) \(=\) \(\displaystyle k\) from $(3)$
\(\displaystyle \) \(=\) \(\displaystyle \floor {\dfrac m n}\)

as claimed.



$\blacksquare$


Sources