## And Yet More Clock Arithmetic

#### Which of the following "regular" arithmetic problems can not be done if we insist that all answers must be integers?

1. 144 ÷ 3
2. 102 ÷ 25
3. 231 ÷ 11
4. 12 ÷ 0
5. 0 ÷ 12

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
We can see from the table that 2 × 6 mod 7 = 5, so (5 ÷ 2) mod 7 = 6. We can also read off the the answers to other division problems such as: (1 ÷ 2) mod 7 = 4, (6 ÷ 2) mod 7 = 3, etc.

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
This time 5 does not appear in the table as an answer. So, (5 ÷ 2) mod 8 does not exist! We also can not divide 1, 3 or 7 by 2 since they don't appear in the table either. What about the numbers that do appear? What is the answer to the question 2 × ? = 4. We now run into a different problem, there isn't just one answer, there are two, both 2 and 6 would be answers. Thus, (4 ÷ 2) mod 8 doesn't have a single value that we can give it ... this is unacceptable. Dividing by 2 mod 8 just can't be done!

#### By writing out a multiplication table like those above, answer these division problems

1. (1 ÷ 3) mod 5 =
2. (1 ÷ 3) mod 6 =
3. (1 ÷ 5) mod 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.
× mod 51234
11234
22413
33142
44321

× mod 61234 5
112345
224024
330303
442042
554321

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.

#### Decide whether or not the following division problems can be done, without finding the answers

1. (1 ÷ 3) mod 5 =
2. (1 ÷ 3) mod 6 =
3. (1 ÷ 5) mod 6 =
4. (3 ÷ 6) mod 18 =
5. (4 ÷ 5) mod 30 =
6. (2 ÷ 7) mod 25 =
7. (3 ÷ 6) mod 27 =

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.

Answers to Can Not Be Done Questions

1. Can be done: 144 ÷ 3 = 48
2. Can not be done: 102 ÷ 25
3. Can be done: 231 ÷ 11 = 21
4. Can not be done: 12 ÷ 0
5. Can be done: 0 ÷ 12 = 0

1.  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
Thus, (1 ÷ 3) mod 5 = 2.

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
Thus, (1 ÷ 3) mod 6 = Can not be done.

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
Thus, (1 ÷ 5) mod 6 = 5.