Discrete Mathematics An Active Approach to Mathematical Reasoning

In this section we will learn another proof technique, proof by cases. We will also see another big discrete math theorem, the Quotient-Remainder Theorem.

In the last section, we looked at the idea of divisibility. Remember, this is a relationship between two integers, not actual division. We will continue to focus on integers. One of the issues with division of integers is that if you divide two integers, you no longer necessarily have an integer. What if the only numbers we are allowed to use are integers? Can we still somehow think of division? Well, yes, this is in fact how you were probably introduced to division long ago. When you were first learning arithmetic, you only worked with integers.

Suppose you want to divide 10 by 5. This is easy, \(10\div 5=2\text{.}\) But what if you want to divide 10 by 4? Now 4 does not “go evenly” into 10 (in other words, 4 does not divide 10). In this case, we get a remainder. In particular, 4 “goes into” 10 two times with a remainder of 2. Or, \(10\div 4\) has quotient 2 and remainder 2.

OK, we want to formalize this idea of division, making sure we are only using integers. We know 5 divides 10, since \(10=5(2)\text{.}\) Can we do the same sort of thing for 10 and 4? Almost. In this case, \(10=4(2)+2\text{.}\)

In general, given any integers \(n, d\) with \(d\neq 0\text{,}\) we can find integers \(q, r\) with \(n=dq+r\text{.}\) In general, \(q, r\) are not unique. For example, \(10=4(1)+6\text{,}\) and \(10=4(-2)+18\text{,}\) and \(10=4(4)-6\text{.}\) But as we noted, we want to think of \(r\) as the remainder. If we are more specific about conditions on the remainder, then \(q\) and \(r\) are unique.

We say \(q\) is the quotient and \(r\) is the remainder when \(n\) is divided by \(d\text{.}\)

We will see the existence part of the proof in Section 5.4.

This theorem is usually called the Division Algorithm. We won’t use that name here since it can be confusing. In particular, the Division Algorithm is not really an algorithm.

Some important observations: the remainder must be nonnegative. It can be 0. This is what happens when \(d\mid n\text{.}\) Although \(n\) can be any integer, we will limit \(d\) to being positive. The Quotient-Remainder Theorem can be extended to any \(d\neq 0\text{,}\) but we will just need \(d>0\) in this class.

We can use the Quotient-Remainder Theorem to find representations of the integers by grouping integers with the same remainder.

For example, if we let \(d=2\text{,}\) what are the possible remainders? In this case, \(r=0\) or \(r=1\text{.}\) Thus, there are two possible forms for \(n\text{:}\) \(n=2q+0\) or \(n=2q+1\text{.}\) We see that these are the two forms corresponding to \(n\) being even or odd. Now, as a corollary of the Quotient-Remainder, we have that every integer must be even or odd.

We can use the Quotient-Remainder Theorem to get other forms, as well. For example, if \(d=4\text{,}\) the possible forms are \(n=4q+0, n=4q+1, n=4q+2\) or \(n=4q+3\text{.}\) We can use these forms to get different cases for the integers.

In choosing your subsets, make sure you cover all the elements of \(D\text{.}\) Your subsets do not need to be similar. For example, one set could be all the nonzero integers and the other just the set with 0.

We saw an example in Theorem 4.3.5, where we broke \(D\) into the set of primes and the set of composites.