Question:
Prove:
$a,b\in \Bbb Z^+\, \Rightarrow \exists q,r\, \ni a=bq+r\, :\, -\frac b2 \lt r \leq \frac b2$
My attempt:
Let $a$ to be an odd number and $b$ to be an even number. Then we can write $b=2r,\, r\in \Bbb N$ and $a=2x+1,x\in \Bbb N\cup \{0\}$. Since we know $\text{Odd $\times$ Odd $=$ Odd}$, we can write $a=2x+1=r(2q+1)$ and $r$ must be an odd number. Then we get $a=2rq+r = bq+r$.
I'm stuck at here. This is the best proof i can think, but i can't show how is $-\frac b2 \lt r \leq \frac b2$. Can you help me please? I have no idea to show the second part. Thanks in advance
Don't by distracted by even oddness.
This is just a restatement of the division theorem that there is unique $q,r$ so that $a=bq + r$ and $0 \le r < b$.
Case 1: $r \le \frac b2$. Then $a = bq + r$ and $-\frac b2 < 0 \le r \le \frac b2$.
Case 2: $\frac b2 < r < b$. (Note: $\frac b2$ can be a non-integer) The we have:
$a = bq + r = b(q+1) + (r -b)$. But $\frac b2 < r < b$ so $-\frac b2 < r-b < 0 < \frac b2$. So if we replace $q$ with $q' = q+1$ and $r$ with $r' = r -b$ then we have $a = bq' + r'$ and $-\frac b2 < r' < 0 < \frac b2$.
That's it.
......
Of course this does assume you have already proven the division algorithm. If not.... you can prove it from scratch be instead of shooting for a positive remainder, shoot for a remainder between $-\frac b2$ and $\frac b2$.
Do you need to see how to do that?
=====
I don't know what class you are taking or to what degree I should rely on induction of well ordered principal of natural numbers is.
But first note: $b > 0$ so $0*b < 1*b < 2*b < 3*b < 4*b <.......$ is an infinite chain of inequalities that is unbounded. $a > 0$ and $a$ is a finite value so $a$ has to fit in there somewhere so there is some $m*b$ where $m*b \le a < (m+1)b$. ($m$ could be zero if $a < b$.)
(That's actually too informal for a basic number theory class but is the most intuitive and obvious explaination. To say the same thing formally would be to let $A= \{n\in \mathbb N| nb > a\}$. We know $A$ is non-empty as $ab \ge a$ so $(a+1)b > a$ and $a+1 \in A$. So by well-ordered principal $A$ has a least element $L$. Let $m = L-1$. Then $m \not \in L$ so $mb \not > a$ so $mb \le a$. And $m+1 = L\in A$ so $(m+1)a > a$.)
(Alternatively, if $B = \{w\in \mathbb Z| wb \le a\}$ we know $B$ is not empty because $0 \in B$ and that if $k \ge a+1$ then $kb=(a+1)a > a$ so $k \not \in B$ so $B$ is bounded above. So $\sup B$ exists. If $\sup B$ is not in $B$ we get a contradiction: Between $\sup B -\frac 12$ and $\sup B$ there must be an integer $w$ in $B$. But $w < \sup B$ so there must be another element $w'$ in $B$ between $w$ and $\sup B$. so $\sup B-\frac 12 \le w < w'< \sup B$ but we can't have two integers withing a half unit of each other. So $\sup B\in B$ so $m=\sup B$ is the integer we want.)
Let $d= a- mb$. Then $0 \le d < b$.
If $0\le d \le \frac b2$ then let $q=m$ and let $r= d$. Then $a=qb +r; -\frac b2 < r \le \frac b2$.
If $b> d > \frac b2$ then let $q = m+1$ and $r = d-b$ os $0> r >-\frac b2$. Then $a=qb + r$ and $-\frac b2 < r \le \frac b2$.