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 q_{1}, r_{1} and q_{2}, r_{2} 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$.

\begin{equation} q_1b + r_1=q_2b + r_2 \end{equation}

(2)
\begin{equation} q_1b + r_1 - q_2b - r_1 = q_2b + r_2 - q_2b - r_1 \end{equation}

(3)
\begin{equation} q_1b - q_2b = r_2 - r_1 \end{equation}

(4)
\begin{equation} b(q_1 - q_2) = r_2 - r_1 \end{equation}

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)\begin{equation} b(q_1 - q_2) = 0 \end{equation}

(6)
\begin{align} q_1 - q_2 = 0 as b{\neq}0 \end{align}

(7)
\begin{equation} q_1 = q_2 \end{equation}

page revision: 6, last edited: 26 Mar 2018 22:03