Remainder is less than divisor

Question

I'm reading a book and it says the equation $$ a \bmod n = a - n \left\lfloor\frac{a}{n}\right\rfloor$$ follows that $$ 0 \leq a \bmod n \lt n. $$

I understand that the remainder is less than divisor, but I can't understand how the author got it from the first equation. Could someone, please, explain it to me?

Suggestion: look at definition of greatest integer function – J. W. Tanner Jul 02 '19 at 22:00 — J. W. Tanner, Jul 02 '19 at 22:00

score 3 · Accepted Answer · answered Jul 02 '19 at 22:01

3

As $\lfloor x\rfloor \le x<\lfloor x\rfloor +1$, we have $$ 0\le \frac an-\left\lfloor \frac an\right\rfloor <1$$ and after multiplication with $n$ the claim.

answered Jul 02 '19 at 22:01

Hagen von Eitzen

374,180

Oh, thank you very much for very easy explanation :) – E. Shcherbo Jul 02 '19 at 22:14

score 1 · Answer 2 · answered Jul 02 '19 at 22:02

1

Since we have that $$\frac{a}n-1\lt\left\lfloor\frac{a}n\right\rfloor\le\frac{a}n$$ Then we can bound the RHS by $$a-n\left(\frac{a}n\right)\le a-n\left\lfloor\frac{a}n\right\rfloor\lt a-n\left(\frac{a}n-1\right)$$ $$0\le a-n\left\lfloor\frac{a}n\right\rfloor\lt n$$

answered Jul 02 '19 at 22:02

Peter Foreman

19,947

Now I got it. Thanks much! – E. Shcherbo Jul 02 '19 at 22:15

Remainder is less than divisor

2 Answers2