Floor of x+m over n

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


Corollary

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

Let $x \in \R$.


Then:

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

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


Proof 1

Let:

$y = x - \floor x$
$M = m + \floor x$

We now have:

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

and

$\floor y = 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 + y < n - 1 + 1 = n$


We have:

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


Substituting $y$ and $M$, we obtain:

\(\displaystyle \floor {\dfrac {x - \floor x + m + \floor x} n }\) \(=\) \(\displaystyle \floor {\dfrac {x + m} n }\)
\(\displaystyle \) \(=\) \(\displaystyle \floor {\dfrac {m + \floor x} n}\)

and the result follows.

$\blacksquare$


Proof 2

Let $f: \R \to \R$ be the real function defined as:

$\forall x \in \R: f \left({x}\right) = \dfrac {x + m} n$

It is clear that $f$ is both strictly increasing and continuous on the whole of $\R$.

Let $\dfrac {x + m} n \in \Z$.

Then:

\(\displaystyle \exists s \in \Z: \dfrac {x + m} n\) \(=\) \(\displaystyle s\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x + m\) \(=\) \(\displaystyle n s\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle n s - m\)
\(\displaystyle \) \(\in\) \(\displaystyle \Z\)

Thus:

$\forall x \in \R: f \left({x}\right) \in \Z \implies x \in \Z$

So the conditions are fulfilled for McEliece's Theorem (Integer Functions) to be applied:

$\left \lfloor{f \left({x}\right)}\right \rfloor = \left \lfloor{f \left({\left \lfloor{x}\right \rfloor}\right)}\right \rfloor \iff \left(f \left({x}\right) \in \Z \implies x \in \Z)\right)$

Hence the result.

$\blacksquare$


Sources