Now we will look at two examples of division in clock arithmetic. In both examples we will just consider dividing by 2, but we will change the modulus in the examples.
Example 1: modulus 7.
Let's try to answer the question 2 ×? mod 7 = 5. The answer to this question, if it exists, would be the value of (5 ÷ 2) mod 7. One way to find the answer would be to write out the "2 ×" table for multiplication mod 7. This table is (check my clock arithmetic!):
| 2 × 0 mod 7 = 0 |
| 2 × 1 mod 7 = 2 |
| 2 × 2 mod 7 = 4 |
| 2 × 3 mod 7 = 6 |
| 2 × 4 mod 7 = 1 |
| 2 × 5 mod 7 = 3 |
| 2 × 6 mod 7 = 5 |
Example 2: modulus 8
Now we'll do the same thing with the modulus 8, that is we'll try to answer the question 2 × ? mod 8 = 5. The table this time is:
| 2 × 0 mod 8 = 0 |
| 2 × 1 mod 8 = 2 |
| 2 × 2 mod 8 = 4 |
| 2 × 3 mod 8 = 6 |
| 2 × 4 mod 8 = 0 |
| 2 × 5 mod 8 = 2 |
| 2 × 6 mod 8 = 4 |
| 2 × 7 mod 8 = 6 |
We are now faced with two problems. First, how can we decide, before trying all these computations, whether or not a division problem can be done? And secondly, how can we determine the answer to a division problem without having to write out these multiplication tables? As we shall see, the first problem has an easy solution, but the second one is a bit more difficult to deal with.
Look at the following two complete multiplication (clock arithmetic!) tables. The first one is with modulus 5 and the second one with modulus 6. We are not writing the row and column which corresponds to multiplication by 0 since these only have 0's in them and we can remember that.
|
|
If the question number1 × ? = number2 is to have an answer, then number2 must appear in the row that is labeled by number1. To always be able to divide by number1, every possible non-zero value for number2 must appear in the row labeled with number1 (and just once!). By looking at these tables, we see that in the modulus 5 table, every row has all the numbers in it (mixed up, but they're all there), and this means that we can divide by any of the row labels. In the modulus 6 table however, only the rows 1 and 5 have this property, so these are the only numbers that we can divide by. Another observation that you can make in the modulus 6 table is that when a row doesn't work, there is always at least one 0 in the row. This is always true. It is easy to see that if a row contains a 0, then there isn't enough room in the row to contain all the non-zero numbers, so that row can not work.
The question now is, how can we figure out if a 0 will appear in a number's row in the multiplication table (without working out the entire row)? The answer involves a property of numbers in "regular" arithmetic. An integer which evenly divides each of two integers is called a common divisor of the two numbers. Thus, 3 is a common divisor of 6 and 12 since 3 divides 6 and 3 divides 12. 2 is also a common divisor of 6 and 12 since 2 divides 6 and 2 divides 12. 4 is not a common divisor of 6 and 12 because 4 does not divide 6 without remainder, even though it does divide 12. Because 1 divides any integer, 1 will be a common divisor of any two integers. The answer to our question about when a 0 will appear in a number's row is: if the number and the modulus have a common divisor bigger than 1, then a 0 will appear in the row of that number. Look at the modulus 6 table again. A 0 appears in row 2 because 2 and 6 have a common divisor of 2. A 0 appears in row 3 because 3 and 6 have a common divisor of 3. A 0 appears in row 4 because 4 and 6 have a common divisor of 2. No 0 appears in row 5 because the biggest common divisor of 5 and 6 is 1.
So, we can divide by an integer n in clock arithmetic with modulus q only when 1 is the only common divisor of the numbers n and q.
In the next section we will look at way to find the answers to these division questions without writing out the multiplication tables. But before we do that I would like to leave you with a question to think about. When 0's appear in a row of the multiplication table, can you figure out where they will appear (that is, in which columns will you find 0's)? As a hint, the answer has something to do with common divisors. If you want to look at a bigger example with lots of 0's try the multiplication table with modulus 12.
| 3 × 0 mod 5 = 0 |
| 3 × 1 mod 5 = 3 |
| 3 × 2 mod 5 = 1 |
| 3 × 3 mod 5 = 4 |
| 3 × 4 mod 5 = 2 |
| 3 × 0 mod 6 = 0 |
| 3 × 1 mod 6 = 3 |
| 3 × 2 mod 6 = 0 |
| 3 × 3 mod 6 = 3 |
| 3 × 4 mod 6 = 0 |
| 3 × 5 mod 6 = 3 |
| 5 × 0 mod 6 = 0 |
| 5 × 1 mod 6 = 5 |
| 5 × 2 mod 6 = 4 |
| 5 × 3 mod 6 = 3 |
| 5 × 4 mod 6 = 2 |
| 5 × 5 mod 6 = 1 |