If $x>y$, then $x \bmod y < \frac{x}{2}$

Question

Given two natural numbers $x$ and $y$ such that $x > y$, prove that

$$x \bmod y < \frac{x}{2}.$$

I was planning on solving this proof by using the definition of mod; however, I was wondering if there was a better way of solving this. Maybe a proof by contradiction?

Answer 1

The number you denote by $x\bmod y$ is the unique integer $r$ such that

1. $x=yq+r$ for some integer $q$
2. $0\le r<y$

Suppose $r\ge x/2$; then $x=yq+r\ge yq+x/2$, so $$ 2x\ge 2yq+x $$ and so $$ x\ge 2yq $$ Hence $$ r=x-yq\ge yq\ge y $$ against the hypothesis. Note that $q>0$, otherwise $x=r<y$.

Answer 2

Based on your suggestions, we have

Strategy 1: $$ x\mod y=r\implies x=qy+r,\quad r<y $$ Since $x>y$ we have $q\geq 1$ and thus $x>(q+1)r\geq 2r$ implying $r<\frac x2$.

Strategy 2:

Assume $x\mod y=r\geq \frac x2$. Then $\frac x2\leq r<y$ together with $x>y$ implies $$ x\geq y+r>x $$ which is a contradiction.

Answer 3

By Division, $\,\ x>y\ \Rightarrow\ x\, =\,\overbrace{ q\,y}^{\large \ge\, 0}\, +\overbrace{ y}^{\large >\, r} + r\, >\, 2\,r\, =\, 2(x\ {\rm mod}\ y)$

Answer 4

Separate it into 2 cases, $x \ge 2y$ and $x < 2y$.

First case apply $x \mod y < y$.

Second case apply $y < x < 2y \Longrightarrow x \mod y = x - y$.