1

I'm trying to understand a proof of the uniqueness of the quotient in the division algorithm, but the proof almost seems rather trivial to me, so it must be that I'm not understanding it. I've rewritten it somewhat.

For reference, the notation $\mathbb{N}_0$ is used to represent the set $\mathbb{N}\cup \{0\}$. This may be unique to this textbook.

Theorem: If $a = bq + r$ and $a = bq' + r$, for $a, b, q, q', r \in \mathbb{N}_0$ and $0 \leq r < b$, then $q = q'$.

Proof: This seems to follow from simple algebra. Since this chapter precedes establishing the rationals as an equivalence relation on $\mathbb{Z} \times \mathbb{Z}$, I assume that I cannot use division. But I believe all of the properties of the integers apply.

Equating the two expressions for $a$ gives us \begin{equation} bq + r = bq' + r. \end{equation} The cancellation law, since $\mathbb{N}_0 \subset \mathbb{Z}$, applies, so $bq = bq'$, which implies that $bq - bq' = b(q - q') = 0$, so either $b = 0$ or $q - q' = 0$. Since $0 \leq r < b$, and thus $b > 0$, meaning that $b \neq 0$, so $q - q' = 0$, and thus $q = q'$.

How does this look? Thanks in advance.

  • no. Your clause $a = bq' + r$ should introduce a new letter with $a = bq' + r'$, – Will Jagy Jun 25 '18 at 01:04
  • I agree with you that this would be customary, as it would also establish uniqueness of the remainder. However, the problem in the textbook only asks that I establish the uniqueness of $q$. (In fact, the assumption that $a = bq + r$ and $a = bq' + r$ is right out of the author's write-up.) I suppose it takes the uniqueness of $r$ for granted. But, I do think generalizing the proof to establish the uniqueness of $r$ makes sense. –  Jun 25 '18 at 01:07
  • I think you are correct that uniqueness is easy to prove given some algebriac tools. Now existence is otherwise since it depends on a fundamental property of N. – Somos Jun 25 '18 at 01:31
  • Well, you could prove that $bq' + r = bq + r$ proves that $q = q'$ but then you can not assume $bq + r= bw + r'$ where $0\le r,r' < b$ are unique. Frankly I'd be very dubious of the textbook as proving the $q$ is unique for a given $r$ is practically useless if you don't also prove the $r$ is unique. – fleablood Jun 25 '18 at 02:33

1 Answers1

0

It's almost as easy to show, under the assumption $b > 0$, that

$bq + r = bq' + r' \Longrightarrow r = r', \; q = q'; \tag 1$

for if $r \ne r'$, we may without loss of generality assume

$r' > r; \tag 2$

then

$b(q - q') = r' - r > 0; \tag 3$

also, since

$0 \le r, r' < b, \tag 4$

we have

$r' - r < b \tag 5$

as well. Now (3) implies

$b > 0, \; q - q' > 0, \tag 6$

which in turn implies, also via (3), since $r, r' < b$,

$r' - r = b(q - q') > r' \ge r' - r, \tag 7$

a contradiction. Thus

$r' = r, \tag 8$

whence

$bq = bq', \tag 9$

whence by cancellation,

$q = q'. \tag{10}$

Robert Lewis
  • 71,180