# Homework Help: Proof of Altered Division Algorithm

1. Jan 29, 2012

### tylerc1991

1. The problem statement, all variables and given/known data

Show that, for positive integers $a$ and $b$, there exists unique integers $q$ and $r$ such that

$a = bq + r$ and $-b/2 < r \leq b/2$.

2. Relevant equations

We can assume the standard division algorithm holds. That is, for integers $a$ and $b$, there exists unique integers $q$ and $r$ such that

$a = bq + r$ and $0 \leq r < b$.

Let $[\cdot]$ represent the floor function.

3. The attempt at a solution

Suppose $a$ and $b$ are positive integers. By the division algorithm, there exists unique integers $q$ and $r$ such that

$a = bq + r$ and $0 \leq r < b$.

At this point, I let $r' = [b/2] - r$. Since $0 \leq r$, we have that $-r \leq 0$, which implies $[b/2] - r = r' \leq [b/2] \leq b/2$ by the definition of the floor function. Also, since $r < b$, we see that $-r > -b$, which implies $[b/2] - r > [b/2] - b = [-b/2] \geq -b/2$.

This is where I get stuck. I have found an integer $r'$ that gives $-b/2 < r' \leq b/2$, but now I have to find an integer $q'$ to satisfy $a = bq' + r'$. Any ideas?

Last edited: Jan 29, 2012
2. Jan 29, 2012

### SammyS

Staff Emeritus
The r' you have, will not work as the remainder of the altered algorithm. I don't know if that's what you intended or not.

3. Jan 29, 2012

### tylerc1991

Right. The solution above doesn't work. I ended up choosing r' depending on what r - b was, which gives the desired result. Hopefully that helps anyone who has this problem in the future.

4. Jan 29, 2012

### SammyS

Staff Emeritus
Right !

or ...
Let r ' = r , q ' = q

If r ' > b/2 then: r ' = r - b and q ' = q + 1 .