Skip to main content
🔗

Section 5.2 Using Cases with the Division Algorithm

🔗
An important result for the set of integers is known as the Division Algorithm. This is somewhat of a misnomer since it is stated in terms of addition and multiplication. The reason for this is that the set of integers is closed under addition and multiplication but is not closed under division. However, we have known for some time that when we divide one integer by another nonzero integer, we get a quotient and a remainder. For example, when we divide 337 by 6, we often write

3376=56+16.

🔗
When we multiply both sides of this equation by 6, we get

337=6⋅56+1.

🔗
When we are working within the system of integers, the second equation is preferred over the first since the second one uses only integers and the operations of addition and multiplication, and the integers are closed under addition and multiplication. Following is a complete statement of the Division Algorithm.

🔗

The Division Algorithm.

For all integers a and b with b>0, there exist unique integers q and r such that

a=bq+r and 0≤r<b.

🔗
So when we speak of the quotient and the remainder when we “divide an integer a by the positive integer b,” we will always mean the quotient (q) and the remainder (r) guaranteed by the Division Algorithm. So the remainder r is the least nonnegative integer such that there exists an integer (quotient) q with a=bq+r.

🔗
The Division Algorithm can sometimes be used to construct cases that can be used to prove a statement that is true for all integers. We have done this when we divided the integers into the even integers and the odd integers since even integers have a remainder of 0 when divided by 2 and odd integers have a remainder of 1 when divided by 2.

🔗
Sometimes it is more useful to divide the integer a by an integer other than 2. For example, if a is divided by 3, there are three possible remainders: 0, 1, and 2. If a is divided by 4, there are four possible remainders: 0, 1, 2, and 3. The remainders form the basis for the cases.

🔗
If the hypothesis of a proposition is that “n is an integer,” then we can use the Division Algorithm to claim that there are unique integers q and r such that

n=3q+r and 0≤r<3

🔗
We can then divide the proof into the following three cases: (1) r=0; (2) r=1; and (3) r=2. This is done in Proposition 5.2.

🔗

Proof.

Let n be an integer. We will show that 3 divides n3−n by examining the three cases for the remainder when n is divided by 3. By the Division Algorithm, there exist unique integers q and r such that

n=3q+r and 0≤r<3

This means that we can consider the following three cases: (1) r=0; (2) r=1; and (3) r=2.

In the case where r=0, we have n=3q. By substituting this into the expression n3−n, we get

n3−n=(3q)3−(3q)=27q3−3q=3(9q3−q)

Since 9q3−q is an integer, the last equation proves that 3|n3−n.

In the second case, r=1 and n=3q+1. When we substitute this into (n3−n), we obtain

n3−n=(3q+1)3−(3q+1)=(27q3+27q2+9q+1)−(3q+1)=27q3+27q2+6q=3(9q3+9q2+2q)

Since 9q3+9q2+2q is an integer, the last equation proves that 3|(n3+n).

The last case is when r=2. The details for this case are part of Exercise 5.3.2. Once this case is completed, we will have proved that 3 divides n3−n in all three cases. Hence, we may conclude that if n is an integer, then 3 divides n3−n.