Maa Questions 23 Post Write

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 < |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)
\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_2<a$, and $�221�r_1 {\leq} r_2$, it follows that $0{\leq}r_2 - r_1<a$. 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}

As $b{\neq}0$:

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

Comments - Andrew Furash
Great job!

page revision: 7, last edited: 09 Apr 2018 17:43
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License