Question 23 PreWrite

23. Prove uniqueness of the quotient and remainder in the division algorithm.
Divison Algorithm: ${\forall} a, b {\in} {\mathbb{Z}}, b{\neq}0$, there exists unique integers q and r such that $0 {\leq} r {\leq} |a|$ $a= qb + r$
Proof: Suppose q1, r1 and q2, r2 satisfy the division algorithm. By definition, $a= q_1b + r_1$ and $a= q_2b + r_2$, so $q_1b + r_1=q_2b + r_2$.

(1)
$$q_1b + r_1=q_2b + r_2$$
(2)
$$q_1b + r_1 - q_2b - r_1 = q_2b + r_2 - q_2b - r_1$$
(3)
$$q_1b - q_2b = r_2 - r_1$$
(4)
$$b(q_1 - q_2) = r_2 - r_1$$

Thus, $r_2 - r_1$ must be some multiple of b. Without loss of generality, suppose $r_2 {\geq} r_1$. However, since $0{\leq}r_1, r_s<a, and �193� r_1{\leq}r_2$, it follows that $0{\leq}r_2 - r_1{\leq}b$. The only multiple of b that satisfies the inequality is 0 so $r_2-r_1 = 0, r_2=r_1$.

(5)
$$b(q_1 - q_2) = 0$$
(6)
\begin{align} q_1 - q_2 = 0 as b{\neq}0 \end{align}
(7)
$$q_1 = q_2$$
page revision: 6, last edited: 26 Mar 2018 22:03