The Division Alogrithm states that $\forall a, b \in \mathbb{N}$ where $b \neq 0$, $ \exists q,r\in \mathbb{N}$ such that $a=qb+r$ with $0 \leq r \lt b$. And one of the ways to prove it is to set $$ S = \{ a-kb \; \vert \; k \in \mathbb{N},\, 0 \leq a-kb \} \subset \mathbb{N} $$ and show that $S \neq \emptyset$ because $k=0$ gives $a \in S$. Therefore, by the smallest element axiom, S has a smallest element. Also we need to show that $r \lt b$ which can be done by contradiction assuming $r \geq b$ $$ r \geq b \implies r - b \geq 0 \implies (a-qb) - b \geq 0 \implies a - (q+1)b \geq 0 $$ and seeing how this assumption means that $r-b \in S$ which is a contradiction since $r-b \lt r$ and $r$ was the smallest element.
So this proof is fine, however, as a challenge I was asked to prove the following variant of the division algorithm: $$ \forall a, b \in \mathbb{Z} \text{ where } b \neq 0, \exists q,r \in \mathbb{Z} \text{ such that } a = qb + r \text{ with } 0 \leq |r| \leq \frac{|b|}{2} $$ I'm trying to use a similar idea but I haven't been successful. I would appreciate any hint or any suggestion about how to tackle this. Thanks in advance.
Use the result from the original theorem and just set
$r' = r - b$ and $q'=q+1$, if $r > \frac{b}{2}$.
Now $q', r'$ are the ones you're looking for.