The Division Algorithm
First, let me state that I find the name Division Algorithm to be entirely misleading. An algorithm tells you how to do something. The Division Algorithm is a statement about existence, not a statement about method. Now that I have that little rant out of my system, let's see the Division Algorithm.
- Division Algorithm:
- For any two integers a and b with b > 0, there are unique integers q and r with a = q b + r and with 0 <= r < b. q is called the quotient and r is called the remainder.
A bit on notation here. I hope that everyone is familiar with the notation a = q b + r meaning that a is equal to the product of q and b summed with r. Additionally, I am using the symbol pair (digraph) of <= to mean "less-than-or-equal-to". Similarly, I shall use >= to mean "greater-than-or-equal-to".
The proof of this theorem can be found in Burton on pages 17 and 18. I'm just going to sketch the proof quickly here. First, he shows that for any integers a and b with b >0, one can find at least one number x for which a - b x >= 0. He does this by letting x = -|a|. From there, he applies the Well-Ordering Principle to find the smallest such integer. Then, he shows that this least element is less than b.
Another notation note. Vertical bars around an expression indicate the absolute value. So |-5| = |5| = 5.
I'll say more about the Well-Ordering Principle in a moment. First, I want to hit some examples with the Division Algorithm. Consider the number a = 43 and b = 17. We can express a as 2 b + 7. The Division Algorithm is just like the game show The Price Is Right. You're looking for the q b that's the closest to a without going over. Suppose we had guessed that q = 3 was going be the closest, then we'd come out with r = -10. So, we'd know that we guessed too high. Similarly, if we had guessed that q = -1 was going to come the closest, then we'd have come out with r = 60. Since, r is supposed to be less than b, we know we guessed too low with q.
The Well-Ordering Principle
For our purposes, it's a fairly intuitive statement about sets of nonnegative integers.
- Well-Ordering Principle
- Every nonempty set of nonnegative integers contains a least element.
The Well-Ordering Principle appears frequently in mathematical proofs. There are more general versions of it than this specific case for integers. But, it would be a huge diversion to get into that here.
For the moment, let me just say a bit about how the Well-Ordering Principle is typically used in proofs. Typically, one shows that a set of non-negative integers has at least one element. Then, one uses the Well-Ordering to say that there must be a least element. Then, one assumes they have this least element. After that, one uses that element to show a contradiction with some other result or to show that this least element is a solution to the problem.
Oi, that was sufficiently obfuscated by vagueness. Here is an example:
- Archimedean Property:
- If a and b are any positive integers, then there exists a positive integer n such that n a >= b.
Assume that the theorem is not true. Then, for some a and b, n a < b for every positive integer n.
Now, consider the set S of all integers b - n a where n is positive. Every element in that set is positive because n a < b for all positive n. Additionally, the set is not empty because b - 1 a is in S.
The Well-Ordering Principle guarantees that there will be a least element in this set. Let's say that b - m a is that least element.
A little algebra shows that b - (m+1) a < b - m a. So, now we're in a conundrum. If m is positive, so is m+1 so b - (m+1) a has to be in S. At the same time, it's smaller than the smallest element of S. Thus, it was a contradiction to assume that n a < b for every positive integer n.
So, if I told you that a was five greater than a multiple of eight and that b was one greater than a multiple of eight. What could you tell me about a + b? That one's probably simple enough to do in your head. a + b is six greater than a multiple of eight. Similarly, a - b is four greater than a multiple of eight. In fact, you can even tell me that a - b is a multiple of four.
Let's make that a bit more rigorous. Let's say that a1 = q1 b + r1 with r1 < b and that a2 = q2 b + r2 with r2 < b. Then,
a1 + a2 = (q1 + q2) b + (r1 + r2)
From this, it is clear to see that a1 + a2 is some multiple of b plus r1 + r2. If the sum of the remainders is less than b, then the Division Algorithm assures us this is the unique representation of a1 + a2 as a multiple of b with a remainder greater or equal to 0 and less than b.
What if the sum of the remainders is greater than or equal to b? In that case, we can subtract b from the sum of the remainders and add it in with the (q1 + q2) b). We'll never have to take more than one b out of the sum of the remainders because r1 and r2 were both less than b, the highest their sum can be is 2 (b - 1). For example, 8 = 2*3 + 2 and 23 = 7*3 + 2. This means that 8 + 23 = (2 + 7)*3 + (2+2). But 4 is bigger than 3, so we need to move a 3 over to the other part to see that 8 + 23 = (2+7+1)*3 + 1.
A similar sort of thing happens when subtracting a1 - a2. You can use some simple algebra to express the difference as a difference of the multiples of b and a difference of the remainders. The caveat here is that the difference of remainders can be negative and we wish our remainders to be greater than or equal to zero. The smallest that the difference of the remainders can be is 1 - b so we can take one b away from the (q1 - q2) b term to bump the remainder up over zero. As an example, 17 = 2*7 + 3 and 12 = 1*7 + 5. Thus, 17 - 12 = (2 - 1)*7 + (3 - 5). Since 3 - 5 is less than zero, we have to take another 7 away from the first term, to bump up the remainder and we get (2 - 1 - 1)*7 + (3 - 5 + 7).
We'll get to multiplication and exponentiation in moment. First, we're going to abstract the stuff above a little bit.
Suppose that we only cared about the remainder (when dividing by b) ofthe sum a1 + a2. From what we saw above, we could find the remainder of the sum without having to know q1 or q2. Armed with this knowledge, we may wish to consider all numbers with the same remainder (when dividing by b) to be equivalent for our purposes.
This is called Modulo Equivalence or Modular Equivalence. If a1 and a2 both have the same remainder when dividing by b, we write a1 == a2 (mod b). One says that "a1 is equivalent to a2 modulo b".
Where I used the symbol "==", one traditionally use a triple-equal sign (an equal sign "=" with a third horizontal bar). However, that character isn't well-support across web-browsers. Additionally, some people spell out "modulo" in place of "mod". Others take out the "mod" entirely and just leave (b). I will never leave it out entirely as I find that to be a confusing notation.
Another useful way of considering Modulo Equivalence is that two numbers are equivalent modulo b iff (where "iff" means "if and only if") their difference is a multiple of b. For example, 8 == 29 (mod 7). Because they both have the same remainder 1, their difference is a multiple of seven. Conversely, because their difference is a multiple of seven, they both have the same remainder modulo 7.
Modulo equivalence helps us simplify a bunch of arithmetic when we're only concerned about the remainder when we are done. For example, if one were purchasing items priced 25, 46, and 61 dollars, one could calculate how many bills smaller than a twenty dollar bill would be needed to make the purchase with exact change. We could approach this problem in two ways. We could add together the three numbers and come up with 132. Then, we could figure out how many twenties we'll need and finally that 12 dollars is leftover. On the other hand, we could figure this out more easily in our head if we note that:
- 25 == 5 (mod 20)
- 46 == 6 (mod 20)
- 61 == 1 (mod 20)
Then, we can easily add 5 + + 6 + 1 = 12 in our head. If we had come out with a number bigger than 20, we would still have to take the result modulo 20. However, we greatly simplified the initial summation and the final calculation.
Another bit of notation that is often used when doing modulo arithmetic is that one defines a % b to be a's remainder when divided by b. With that notation, we can sum up the trick that we did with the money above as follows:
- (a1 + a2) % b = ( (a1 % b) + (a2 % b) ) % b
The final "% b" is just to make sure that the final sum doesn't end up being larger than b.
Unsurprisingly, subtraction works the same way.
- (a1 - a2) % b = ( (a1 % b) - (a2 % b) ) % b
What is multiplication? It's just a shorthand notation for repeated addition. As such, it shouldn't come as much of a surprise to you that multiplication obeys the same basic rule.
- (a1 * a2) % b = ( (a1 % b) * (a2 % b) ) % b
To verify this, multiply together q1 b + r1 and q2 b + r2. Once you ignore all of the terms which obviously contain b's, you will be left with r1 * r2. As an example, we can figure out how many bills smaller than a twenty we will need to buy 7 items which each cost 23 dollars. Since 7 % 20 = 7 and 23 % 20 = 3, we know that (7 * 23) % 20 = (7 * 3) % 20 which is one. We'll need some number of twenties and then one more dollar to buy seven of these items.
Hopefully, it will not be a surprise to you to say that exponentiation follows a similar rule. It's simply repeated multiplication.
(a^n) % b = ( (a % b)^n ) % b
Notational note: I am combining both the a^n and the
an conventions in an attempt not to alienate those
whose browsers do not support the
<sup> tag. I
hope it isn't too much of an inconvenience on the rest of
This identity is a bit harder to verify. If you're keen on doing it, you can either do it by induction or by doing the binomial expansion of (q b + r)^n to see that all of the terms contain explicit multiples of b except for the final r^n.
Let's quickly calculate 17^8 % 4. Since 17 % 4 = 1, we get that 17^8 % 4 = 1^8 % 4 = 1.
Here are some problems to try. Answers will be posted on Tuesday (and linked here). Reply to this article on LiveJournal if you have specific questions about the content of this lecture or these problems.
- Calculate two different ways:
- (3 + 11 + 8) % 2
- (3 * 11 + 8) % 2
- (4^4 +7) % 3
- Calculate: ( (241 * 36)^14 + (32 * 15 + 5)^11) % 5
Next week, we'll go through some more shortcuts on how to do calculations like these. We'll also get into the Euclidean Algorithm (which, mercy me, is actually an algorithm) for calculating the greatest common divisor of two numbers. And, we may do a touch more, but I'm not sure yet.