Proof of Altered Division Algorithm

[tylerc1991]

Homework Statement

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$.

Homework 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.

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?

 

[SammyS]

Homework Statement

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$.

Homework 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.

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?

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.

 

[tylerc1991]

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.

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.

 

[SammyS]

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.

Right !

or ...

Spoiler

Let r ' = r , q ' = q

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