Proving a mod b < a/2 when a > b > 0

Question

Suppose that $a \gt b \gt 0$. How can one prove that $a$ mod $b \lt a/2$?

I understand why is that happening: if $a$ mod $b \gt a/2$ that means that $a/b \lt a/2$ and $a/b$ has enough "space" to get inside the $a$ mod $b$ one more time, since $a$ mod $b \gt a/2$. This is a contradiction to the division result.

What is the formal proof for that? I couldn't find it anywhere.

Answer 1

Hint: Use the facts that $(a \mod b)<b$ and that $(a\mod b)\le a-b$ (this second inequality holds in the case that $a\ge b$).

Answer 2

Let $a>b>0$ and write $a\bmod b=r$. This means $0\le r<b$ and $a=bq+r$ for some $q>0$. Suppose $r>a/2$; then you have $$ a<2r<2b $$ that can be written $$ a<2a-2bq<2b $$ because $r=a-bq$. This in turn gives $$ \begin{cases} a>2bq\\ a<b(q+1) \end{cases} $$ What condition on $q$ can you derive?

Answer 3

Let $a=bk+r$ with ($a$ mod $b$)$=r$. We have to prove $r \lt a/2$ or we can change it to:

$$a-bk \lt a/2 \iff bk \gt a/2 \iff bk \gt (bk+r)/2 \iff bk>r \quad \text{ (1) } $$

Because $r \lt b$, so (1) is correct. (QED)