You probably know that division can be defined in terms of multiplication. If m and n are integers and , m divides n if for some integer k. In this section, I'll look at properties of the divisibility relation.
I'll begin by discussing the Division Algorithm, which tells you something you've known since grade school --- namely, that you can divide one integer by another. Note that this isn't the {\it long-division algorithm}, which tells you how to divide one integer by another. The Division Algorithm follows from the Well-Ordering Axiom for the nonnegative integers.
Well-Ordering Axiom. The positive integers are well-ordered --- that is, every nonempty subset of the positive integers has a smallest element.
Even though your experience with the integers may lead you to think this is obvious, it's actually an axiom of the positive integers . It has many important consequences; mathematical induction is one, and the Division Algorithm is another.
Note that Well-Ordering applies to nonempty subsets of the {\it nonnegative} integers as well. If such a subset contains 0, then 0 is the smallest element; if the subset doesn't contain 0, then it consists of only positive integers, and Well-Ordering for the positive integers implies that it has a smallest element.
Example. ( Applying the Well-Ordering Axiom) Show that there is no positive integer less than 1.
In this proof, I'm going to assume familiar facts about inequalities involving integers, since the point is to illustrate how you might use Well-Ordering.
Suppose that there is a positive integer less than 1. Let S be the set of positive integers less than 1. Then S is nonempty, so by Well-Ordering, S has a smallest element.
Suppose that x is the smallest element of S. Now , so multiplying by x, I get
Thus, is a positive integer less than 1 which is smaller than x. This is a contradiction. Therefore, there is no positive integer less than 1.
Theorem. ( The Division Algorithm) Let a and b be integers, with . There are unique integers q and r such that
Of course, q is the quotient and r is the remainder.
Proof. What is division? Division is successive subtraction. Therefore, you ought to be able to find r by subtracting multiples of b from a until the result becomes negative. For example, if you're dividing 23 by 7, you'd do this:
The quotient is 3 --- the last multiple of 7 which gave a nonnegative result. The last nonnegative result is the remainder, which is 2.
To do the proof, I have to take the idea exhibited in this example and write it out in general (with a, b, q, and r instead of specific numbers).
Look at the set of integers
If I choose (as I can --- there's always an integer less than any number), then , so . This choice of n produces a positive integer in S. So the subset T consisting of nonnegative integers in S is nonempty.
Since T is a nonempty set of nonnegative integers, I can apply Well-Ordering. It tells me that there is a smallest element . Thus, , and for some q (because , , and everything in S has this form).
Moreover, if , then , so
So , but . This contradicts my assumption that r was the smallest element of T.
All together, I now have r and q such that
To show that r and q are unique, suppose and also satisfy these conditions:
Then
But r and are two nonnegative numbers less than b, so they are both in the range . Therefore, they have to be less than b units apart. But the last equation says they are units apart --- a multiple of b).
The only way r and can be less than b units apart and a multiple of b units apart is if the multiple in question is 0. That is, . Since , this means that , or . If I plug back into , I find that , so . This proves that r and q are unique.
Example. ( Applying the Division Algorithm) (a) Find the quotient and remainder when the Division Algorithm is applied to divide 99 by 13.
The quotient is 7 and the remainder is 8. According to the proof of the theorem, 8 should be the smallest positive number of the form . In this case,
Clearly, adding multiples of 13 to will give numbers larger than 8, whereas subtracting multiples of 13 from will give negative numbers.
(b) Find the quotient and remainder when the Division Algorithm is applied to divide -99 by 13.
Note that . I don't write (even though the equation is correct), because -8 is not between 0 and 13. The Division Algorithm always produces a nonnegative remainder.
Definition. If m and n are integers and , then m divides n if for some integer k.
The notation means that m divides n; means that m does not divide n.
If , then . k is unique, by the Division Algorithm; it's the quotient of n by m. Note that without the stipulation that , the quotient of 0 by 0 is not unique: , but as well.
Remark. Be careful not to write " ", " ", or " " when you mean " "!
" ", " ", and " " all mean "n {\it divided by} m". Notice that this isn't a statement, since it's not a complete sentence that can be true or false --- it's an {\it expression}. On the other hand, " " means "m divides n", which is a statement.
Lemma.
(a) Let . If and , then .
(b) Let . If , then for all .
(c) Let . If and , then .
(d) Let . If and , then for all .
(e) If and , then .
Proof. The idea in divisibility proofs is often to translate statements like " " into equations like " ", then work with the equations.
(a) implies for some k. implies for some j. Substituting the first equation into the second gives
so .
(b) implies for some k. Then , and so .
(c) implies for some k, and implies for some j. Then
(d) Since , by (b); since , by . Therefore, by (c).
(e) Suppose and . implies for some ; k must be a positive integer, since m and n are positive integers. Thus, , and multiplying both sides of this inequality by m gives
Example. ( Illustrating divisibility for specific numbers) , since . , since .
If n is any integer, , since .
Likewise, if n is a nonzero integer, then , since .
Warning: and , so and do not imply that --- only that .
Example. ( Proving a divisibility property) Prove that if m and n are positive integers, , and , then .
One approach is to use property (e) of the preceding lemma. Since m and n are positive integers, implies , and implies . The two inequalities imply that .
Here's another proof which uses the definition of divisibility.
Since , for some . Since , for some . Hence, . Since , I may cancel it from both sides to obtain .
a and b are integers, so either or . But if , then , which is impossible since m and n are positive. Therefore, , so .
Example. ( Even and odd integers) An integer is even if . An integer is odd if it is not even.
(a) Prove that even integers can be written in the form for some , and odd integers can be written in the form for some .
If n is even, then , so for some .
Suppose n is odd. Use the Division Algorithm to divide n by 2, obtaining a quotient of m and a remainder of r:
Now implies that or . If , the equation says , which means that n is even. But n was odd, so this is a contradiction. Therefore, , and .
(b) Prove that if is even, so is .
Suppose is even. By (a), for some . Then
Therefore, , and is even.
Note: It would not be a good proof to stop with " " and say " must be even, because I know that is even". While it's true that is even, you haven't proved that yet. All you know at the moment is that even numbers are numbers that are divisible by 2. So you have to write as , which shows {\it explicitly} that it's divisible by 2.
Copyright 2008 by Bruce Ikenaga