# Floor of x+m over n

## Contents

## 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

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$

## 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

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $35$