Mg Problem 23

PRELIMINARY

23. Prove the uniqueness of the output of the quotient algorithm. That is, if $a=qb+r$ with $a,b,q,r \in \mathbb{Z}$ and $0\leq r < |b|$ and $a=\tilde{q}b+\tilde{r}$ with $a,b,\tilde{q},\tilde{r} \in \mathbb{Z}$ and $0\leq \tilde{r} < |b|$, $q=\tilde{q}$ and $r=\tilde{r}$.

Pf: Suppose toward contradiction and without loss of generality that $q < \tilde{q}$. Since $q,\tilde{q} \in \mathbb{Z}$, we can say that $\tilde{q} = q+k$ for some positive integer $k$. We can then say that $a=(q+k)b+\tilde{r} = qb + kb +\tilde{r} = qb + r$. By cancellation, we can say that $kb+\tilde{r} = r$. From the definition of the division algorithm, it must be true that $0\leq r < |b|$. For the sake of this argument, assume that $b>0$.

If $k=0$, then $\tilde{q}=(q+0)=q$, so suppose that $k\neq 0$. Then, either $k<0$ or $k>0$. If $k<0$, and $0\leq \tilde{r} < |b|$, the greatest $kb+\tilde{r} = r$ can be is $-1$, since $kb \leq -|b|$ and $\tilde{r} \leq |b|-1$. This would violate $0 \leq r < |b|$.

If $k>0$, then the least $kb+\tilde{r}=r$ can be is $|b|$, since $kb\geq{|b|}$ and $\tilde{r}\geq 0$. This also violates $0 \leq r < |b|$. Therefore, by contradiction, we can conclude that $q=\tilde{q}$.

Similar logic proves $q=\tilde{q}$ if $b<0$.

It remains to prove that $r=\tilde{r}$. Since $q=\tilde{q}$ and $a=qb+r=\tilde{q}b+\tilde{r}$, $qb+r=qb+\tilde{r}$. By cancellation, $r=\tilde{r}$. $QED$

FINAL

Prove the uniqueness of the output of the quotient algorithm. That is, if $a=qb+r$ with $a,b,q,r \in \mathbb{Z}$ and $0\leq r < |b|$ and $a=\tilde{q}b+\tilde{r}$ with $a,b,\tilde{q},\tilde{r} \in \mathbb{Z}$ and $0\leq \tilde{r} < |b|$, $q=\tilde{q}$ and $r=\tilde{r}$.

Pf: Since $q,\tilde{q}\in \mathbb{Z}$, we may write $\tilde{q} = q + k$ for some integer $k$. Now, we substitute this value for $\tilde{q}$ to get $a = (q+k)b+\tilde{r} = qb + kb + \tilde{r}$. Since we also have $a = qb + r$, by cancellation, we may by cancellation determine that $r = kb + \tilde{r}$.

Now, suppose toward contradiction $kb > 0$. Then, since $k,b \in \mathbb{Z}$, $kb \leq |b|$. We also know that $\tilde{r} < |b|$, and since $|b| \in \mathbb{Z}$, this is the same as $0 \leq \tilde{r}$. Therefore, $kb + \tilde{r} \leq 0 + |b| = |b|$. But this is impossible, since we have $kb + \tilde{r} = r$ and $0\leq r < |b|$. Therefore, we know that $kb$ is not positive.

Then suppose $kb < 0$. In this case, the maximum possible value of $kb$ is $-|b|$. We also know that $\tilde{r} < |b|$. Since $\tilde{r} \in \mathbb{Z}$, this is the same as $\tilde{r} \leq |b|-1$. Therefore, we can say that $r = kb + \tilde{r} \leq -|b| + |b| - 1 = -1$. But since $0 \leq r < |b|$, we know this is impossible.

Therefore, we conclude that $kb = 0$. Since, by definition, $b \neq 0$, this can only be the case if $k = 0$. Therefore, we have $\tilde{q} = q + k = q + 0 = q$.

Since $\tilde{q} = q$, $\tilde{q}b = qb$. Thus, we have $\tilde{q}b + \tilde{r} = qb + \tilde{r} = qb + r$. By cancellation, we get $\tilde{r} = r$. $QED$

Comments - Andrew Furash
This proof is a little bit round-about. There are simpler ways to accomplish this proof.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License