MHB What is meant by the unique integers Q and R in the quotient remainder theorem?

[tmt1]

Given any integer A, and a positive integer B, there exist unique integers Q and R such that
$$A= B * Q + R$$ where $$ 0 ≤ R < B$$.

When is says that $$Q$$ and $$R$$ are unique, what does that mean? That they are different from each other?

 

[Ackbach]

It means that, if $Q'$ and $R'$ are any two integers such that $A=Q' B+R'$, with $0\le R'<B$, then $Q=Q'$ and $R=R'$. That is, there's only one way to find a quotient and remainder.

 

[Deveno]

If something is true, we ought to be able to *prove* it. A proof of this type breaks down into two parts:

a) Existence
b) Uniqueness

For existence, I will consider only $A > 0$. The case $A = 0$ is trivial:

$0 = 0B + 0$.

I urge you to try to adapt my proof for $A > 0$ to the $A < 0$ case (you'll have to make a small adjustment, since we want the remainder $R$ to be positive, and so multiplying through by $-1$ won't work.

However, if $A,Q < 0$, and:

$A = QB + R$ where $B < R \leq 0$, you may find it profitable to consider:

$A = (Q - 1)B + (R + B)$).

The trick here lies in the fact that the integers are TOTALLY ORDERED. In other words, given two integers $k,m$, exactly one of the following holds:

1. $k = m$
2. $k > m$
3. $k < m$.

Now, it may seem like I'm "passing the buck." This is true. To prove the integers are, in fact, totally ordered, I would have to prove a similar fact about natural numbers. And to prove the natural numbers are totally ordered, I would have to go deeper into facts about "well-orderedness" and induction which are often just assumed "axiomatically" (that is-whatever we conceive "natural numbers" to be, we want them to be totally ordered). That's a big can of worms.

So, I will take as given the "trichotomy rule" (1 - 3) above. This is, at least, intuitively plausible.

So, first, let's compare $A$ to $B$. If $A < B$, then we can write:

$A = 0B + A$, (that is $Q = 0$ and $R = A$), and this satisfies our requirements for $Q$ and $R$.

If $A = B$, we can write:

$A = 1B + 0$ (that is, $Q = 1$ and $R = 0$), which also fits our restrictions on $Q$ and $R$.

So the only "interesting" case, is when $A > B$.

Consider the set $S = \{B,2A,3A,\dots\}$ of all positive integral multiples of $B$. We want to focus on the SUBSET:

$T = \{nB \in S: nB > A\}$.

The point being, here, that $T$ is non-empty, for if *every* multiple of $B$ were less than or equal to $A$, we would have:

$A > nB \geq n$, for every natural number $n$, because $B > 0$, and thus $B \geq 1$.

Since $A$ is, in fact, a natural number (a positive integer always is), and $A < A + 1$ (and $A + 1$ is *also* a natural number), $A$ cannot simultaneously be greater than *every* natural number and *also* less that some *particular* natural number. So $A > nB$ for every $n$ cannot be true, as it leads to a contradiction. This proves the set $T$ is non-empty.

Since $T$ is a non-empty set of natural numbers, it has a least element (again, we are leveraging the "total order" on the natural numbers, and the fact that the natural numbers are bounded below by $0$). This least element of $T$ is of the form:

$kB$, for some positive integer $k$. Pick $Q = k-1$.

Now $QB \leq A < (Q+1)B$, by our choice of $Q$.

(What we have done, in naive terms, is: keeping adding $B$ to itself, until we find a multiple $QB$ with:

$QB \leq A < (Q+1)B$, which is what you would do in actual practice if you actually had to find a specific $Q$).

It follows that $0 \leq A - QB < B$, so we may take $R = A - QB$, and thus:

$QB + R = QB + (A - QB) = A$.

This may be hard for you to follow-existence proofs are often "vague" in this way-we seemed to have proven something, but it seems all very far-removed from reality. This is the nature of the beast. There is a select few mathematicians, who only believe a thing exists if you can "make" it, out of other "known" things. This is not such an indefensible view, but I must warn you-it is not the majority opinion. If you feel you belong to this breed, refer to the section where I say: "What we have done, in naive terms..."

That's really the hard part, producing at least ONE $Q,R$. For example, with $A = 21$ and $B = 5$, we find that:

$4 \cdot 5 = 20 < 21$
$5 \cdot 5 = 25 > 21$,

so we take $Q = 4$, and thus $R = 21 - 20 = 1$.

With existence established, uniqueness is easy:

Suppose $A = Q'B + R' = QB + R$. We will suppose $R \geq R'$ (if not, just switch which $Q,R$ pair has the "primes").

Thus $0 = (Q - Q')B + (R - R')$.

Now $R - R' = (Q' - Q)B$ is a multiple of $B$, but $0 \leq R - R' < R < B$, so we conclude that $R - R' = 0$, in which case, from:

$0 = (Q' - Q)B$, and the fact that $B > 0$ we have immediately that $Q' - Q = 0$, that is $Q = Q'$, and we have uniqueness.

 

[johng1]

Deveno's reply is certainly a good proof. Here's another way to look at it. When you were taught to do division of $A$ by $B$, you learned that you first found the quotient $Q$ and then the remainder $R$ is $A-BQ$. Example: 16 divided by 5 has quotient 3 and then remainder $16-3\cdot 5=1$. So the only problem is the quotient $Q$.
If you've studied calculus, you probably ran into the greatest integer function, also called the floor function. I will assume this function exists (as in Deveno's post, this can be proved using properties of the real numbers). For any $x\in R$, the floor function is defined by $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$; i.e. floor(x) is less than or equal to x, but floor(x) + 1 is not less than or equal to x or x < floor(x) + 1. In symbols, $\lfloor x\rfloor\leq x<\lfloor x\rfloor+1$
Back to the problem of finding $Q$. Set $Q=\lfloor A/B\rfloor$, an integer. Then we have
$$Q\leq A/B<Q+1$$
Multiply this inequality by $B>0$
$$BQ\leq A<BQ+B \text{ and so }0\leq A-BQ<B$$
As above, $$\text{Set }R=A-BQ\text{, an integer, }\text{ and then }A=BQ+R\text{ with }0\leq R<B$$
One advantage of the above existence proof is that it is valid for any $A$, positive, negative or zero. Finally, I can't improve on Deveno's uniqueness proof.