Proof That [(x + n)/m] = [([x] + n)/m]

We can represent \(\frac{x+n}{m}\) as:

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

We can represent \(x\) as:

$$ x = \left\lfloor x \right\rfloor + \left\{ x \right\}$$

Adding \(n\) and dividing by \(m\):

$$\begin{gather} x + n = \lfloor x \rfloor + \left\{ x \right\} + n \\ \frac{x + n}{m} = \frac{\lfloor x \rfloor + \left\{ x \right\} + n}{m} \end{gather}$$

Using the floor function:

$$\begin{gather} \left\lfloor \frac{x + n}{m} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor + \left\{ x \right\} + n}{m} \right\rfloor \\ \left\lfloor \frac{x + n}{m} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor + n}{m} + \frac{\left\{ x \right\}}{m} \right\rfloor \end{gather}$$

Separating \( \frac{\lfloor x \rfloor + n}{m} \) into it's integer and fractinoal components:

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

Since \( \left\lfloor \frac{\lfloor x \rfloor + n}{m} \right\rfloor \) is an integer:

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

Since \(\lfloor x \rfloor + n\) is an integer, then the highest value for \(\left\{ \frac{\lfloor x \rfloor + n}{m} \right\}\) is \(\frac{m-1}{m}\). Since \(\{x\} \lt 1\), then \(\{x\}/m \lt 1/m\). This means:

$$\begin{gather} \left\{ \frac{\lfloor x \rfloor + n}{m} \right\} + \frac{\left\{ x \right\}}{m} \lt \left( \frac{m-1}{m} \right) + \frac{1}{m} \\ \left\{ \frac{\lfloor x \rfloor + n}{m} \right\} + \frac{\left\{ x \right\}}{m} \lt 1 \end{gather} $$

Which means:

$$\begin{align} \left\lfloor \frac{x + n}{m} \right\rfloor &= \left\lfloor \frac{\lfloor x \rfloor + n}{m} \right\rfloor + \left\lfloor \left\{ \frac{\lfloor x \rfloor + n}{m} \right\} + \frac{\left\{ x \right\}}{m} \right\rfloor \\ &= \left\lfloor \frac{\lfloor x \rfloor + n}{m} \right\rfloor + 0 \end{align}$$

Therefore \(\lfloor (x + n)/m \rfloor = \lfloor (\lfloor x \rfloor + n)/m \rfloor\).

Styles

(uses cookies)