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 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_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