And Yet More Clock Arithmetic

We have looked at addition, subtraction and multiplication in clock arithmetic. Now, we want to consider division in clock arithmetic (not to be confused with the division method used in the last section, that was division in "regular" arithmetic). However, this operation is not as easy as the others! The problem is that in clock arithmetic we always want our answers to be whole numbers (integers). When doing addition, subtraction or multiplication this is always true; when you start with integers the result is always an integer. But, when you divide integers, this doesn't always happen. For example, when we consider a question like: 2 × ? = 6, the answer is 6 ÷ 2 = 3, and in this case the answer is an integer. But if the question was: 2 × ? = 5, the answer (in regular arithmetic) is 5 ÷ 2 = 2½ which is not an integer. If we were to enforce the rule that ALL ANSWERS MUST BE INTEGERS!, then the division problem 5 ÷ 2 would have no answer ... or as we would normally say, it can not be done! (If you are thinking that this is a pretty dumb rule ... just wait, we will see that there are situations in which this rule is very useful.) Saying that a division problem can not be done isn't really all that strange ... it happens in regular arithmetic; for example, what is the answer to the question 0 × ? = 4. Since this question has no answer, we can not do the division 4 ÷ 0. In this situation, we usually say that "division by 0 is not allowed" or "division by 0 can not be done!" As we shall see, in clock arithmetic there will sometimes be several numbers that we can not divide by.

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
Click here to see the answers.

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 =
Click here to see the answers.

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 =
Click here to see the answers.

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
Return to Questions
Answers to Division Questions

  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.
Return to Questions
Answers to Can These Be Done Questions

  1. (1 ÷ 3) mod 5 = Can be done since 1 is the only common divisor of 3 and 5.
  2. (1 ÷ 3) mod 6 = Can not be done since 3 is a common divisor of 3 and 6.
  3. (1 ÷ 5) mod 6 = Can be done since 1 is the only common divisor of 5 and 6.
  4. (3 ÷ 6) mod 18 = Can not be done, 2 is a common divisor of 6 and 18.
  5. (4 ÷ 5) mod 30 = Can not be done, 5 is a common divisor of 5 and 30.
  6. (2 ÷ 7) mod 25 = Can be done, 1 is the only common divisor of 7 and 25.
  7. (3 ÷ 6) mod 27 = Can not be done, 3 is a common divisor of 6 and 27.
Return to Questions