Expressing n mod m in terms of floor values?

Question

I'm trying to prove the expression:

$$\left\lceil\frac{n}m\right\rceil = \left\lfloor \frac{n+m-1}{m}\right\rfloor\;,$$

where $n,m$ are integers`

So I've come across this article (PDF) which gives a nice method of proving the above expression from page $10$ onwards. I understand pretty much the entire proof, except for the definition on page $10$.

It states that

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

I've never encountered the $\{\}$ symbols before in maths, but given that any real quotient can be expressed as the floor of the quotient (the integer part) summed with the fractional part, I'm guessing that the $\{\}$ symbols state that this is the fractional part of the real number $\frac{n}m$?

That's all fine by me, but what I can't understand is the next line. If I wanted to get rid of the $m$ on the L.H.S I'd multiply both sides by $m$. But somehow, according to the pdf, it's true to say that

$$m\left\{\frac{n}m\right\} = n \bmod m\;.$$

Can someone explain why this is the case?

Thanks!

Answer 1

Your interpretation of $\{x\}$ is correct: this notation is quite often used for the fractional part, $\{x\}=x-\lfloor x\rfloor$.

We want to show that $m\left\{\frac{n}m\right\}=n\bmod m$, i.e., that

$$m\left(\frac{n}m-\left\lfloor\frac{n}m\right\rfloor\right)=n\bmod m\;.$$

This is clearly equivalent to showing that

$$n-m\left\lfloor\frac{n}m\right\rfloor=n\bmod m\;.$$

By definition $\left\lfloor\frac{n}m\right\rfloor\le\frac{n}m<\left\lfloor\frac{n}m\right\rfloor+1$, so

$$m\left\lfloor\frac{n}m\right\rfloor\le n<m\left\lfloor\frac{n}m\right\rfloor+m\;,$$ and after subtracting $m\left\lfloor\frac{n}m\right\rfloor$ throughout, we have

$$0\le n-m\left\lfloor\frac{n}m\right\rfloor<m\;.$$

Thus $n-m\left\lfloor\frac{n}m\right\rfloor$ is an integer in the correct range. Finally,

$$n-\left(n-m\left\lfloor\frac{n}m\right\rfloor\right)=m\left\lfloor\frac{n}m\right\rfloor$$

is clearly divisible by $m$, so

$$n-m\left\lfloor\frac{n}m\right\rfloor=n\bmod m\;,$$

as desired.

Answer 2

If $n=mq+r$ where $0 \le r \le m-1,$ then $n/m=q+r/m.$ So the fractional part is $\{n/m\}=r/m,$ and then $m$ times fractional part gives back the remainder $r$.