I'm the GREATEST common divisor
Our aim is to obtain a method for answering division problems in clock arithmetic. However, this turns out to be complicated, so we will gradually develop the method.
As we have seen, in order to decide if a division problem can be done, we need to find out if the biggest common divisor of the number we are dividing by and the modulus is 1. The biggest common divisor of two numbers is generally called the greatest common divisor of the two numbers. Finding the greatest common divisor of small numbers is easy to do by inspection ... looking at all the divisors of one number and seeing whether or not they divide the other number, and picking the largest divisor which does. However, when the numbers are large, this can take a lot of time. You would probably look for quite a while before finding out that the greatest common divisor of 378 and 3465 is 63. Fortunately, there is a method for finding the greatest common divisor of two integers, which does not involve any guessing. The method is very old and is called the Euclidean Algorithm. It is named after the Greek mathematician Euclid who lived around 200 B.C. Euclid is most famous for his work in Geometry, but he also did a lot of work with numbers. The word "Algorithm" is just a fancy way of saying method. So the Euclidean Algorithm is just Euclid's Method for finding greatest common divisors.
To describe this method, let's recall the terms we use when we do a division problem (in ordinary arithmetic). A number (the dividend) when divided by a second number (the divisor) gives an integer answer (the quotient) plus a fractional part (the remainder/the divisor):
dividend remainder
-------- = quotient + --------- .
divisor divisor
So, in the division 25/7 we have:
25 4
-- = 3 + - ,
7 7
and 25 is the dividend, 7 the divisor, 3 the quotient and 4 the remainder. Now Euclid's method involves doing a series of divisions. To find the greatest common divisor of two numbers, first divide the larger one by the smaller, writing the problem as above. The next division to do is the one you get by "flipping" the fractional part of the last division - that is the new dividend is the old divisor and the new divisor is the old remainder. When this is done, repeat the process (i.e., flip the new fractional part to get the next division). Keep doing this until you have to stop because a remainder becomes 0. The last non-zero remainder is the greatest common divisor of the original two numbers. For example, let's use this method to find the greatest common divisor of 7 and 25 (which we can easily see is 1). The first step was done above. The next division is 7/4 (the flip of 4/7). This gives 7/4 = 1 + 3/4. Next we do, 4/3 = 1 + 1/3. Next we do, 3/1 = 3 + 0, so we stop here. The last non-zero remainder is the bold 1 of the next to last step, and this is the greatest common divisor. What a lot of work to get an answer we knew from the beginning! Maybe this next example will convince you that this might be worth the effort. Let's use Euclid's method to find the greatest common divisor of 378 and 3465.
3465/378 = 9 + 63/378
378/63 = 6 + 0.
So the greatest common divisor is 63. Now that was easy!
Use Euclid's method to find the greatest common divisor of these pairs of numbers.
- 102 and 25
- 198 and 243
- 7469 and 2464
- 1109 and 4999
Click here to see the answers.
There are two things we need to say about this method. If in the first step there is no remainder, then the greatest common divisor is the smaller of the two numbers. The second thing is to notice that the quotients that are obtained in each division step don't play any role in finding the greatest common divisor ... but don't ignore them, we will be using them later.
When we are trying to do a clock arithmetic division, like finding (5 ÷ 7) mod 25, we do it in two steps since (5 ÷ 7) mod 25 = 5 × (1 ÷ 7) mod 25. That means that we can first find the value of (1 ÷ 7) mod 25 and then just multiply that by 5 (mod 25). In this example, (5 ÷ 7) mod 25 is the answer to the question 7 × ? = 5 mod 25. If we knew that (1 ÷ 7) mod 25 = 18, then we get the answer to our question by calculating 5 × 18 mod 25 = 90 mod 25 = 15. Notice that 7 × 15 mod 25 = 105 mod 25 = 5, so 15 is the right answer to our division problem. This means that whenever we do a clock arithmetic division, we can always do the division with dividend 1 instead of the actual dividend, and then multiply by the real dividend of the problem. As we shall see, our method for doing these divisions works only if we do our division problems this way.
Use the given information to find the answers to these division problems.
- (6 ÷ 9) mod 17, if you know that (1 ÷ 9) mod 17 = 2.
- (12 ÷ 5) mod 24, if you know that (1 ÷ 5) mod 24 = 5.
- (8 ÷ 6) mod 35, if you know that (1 ÷ 6) mod 35 = 6.
Click here to see the answers.
We have gotten to the point where we have to find values like (1 ÷ 9) mod 17. This is the answer to the question 9 × ? mod 17 = 1. Now, in ordinary arithmetic, 9 × ? will not be 1, we only get 1 after we subtract a certain number of 17's from this product. That is, 1 = 9 × ? - 17 × ??. In this easy problem you could probably guess that ? = 2 and ?? = 1, since 9 × 2 - 17 × 1 = 18 -17 = 1. The secret to doing this type of division problem, i.e., (1 ÷ divisor) mod (modulus), is to find two integers (either positive or negative) which I'll call ? and ??, so that in ordinary arithmetic we have 1 = (divisor) × ? + (modulus) × ??. The answer to the division problem will be the ?. If we can guess the values of ? and ??, then we are done. However, there is no need to guess these values, since we can find them from the calculations we perform in Euclid's method, by working backwards. To see how this is done, first use Euclid's method to find the greatest common divisor of 9 and 17.
- 17/9 = 1 + 8/9.
- 9/8 = 1 + 1/8.
- 8/1 = 8 + 0.
Now, we rewrite each of these divisions, except the last one, by multiplying both sides by the divisor and then subtracting to get the remainder alone on one side. That is, we are rewriting the divisions so that they are in the form : remainder = dividend - (quotient × divisor). In our example:
- 17 = 1 × 9 + 8, so 8 = 17 - 1 × 9.
- 9 = 1 × 8 + 1, so 1 = 9 - 1 × 8.
Now we start with the last equation, 1 = 9 - 1 × 8. The 8 that appears here is the remainder of the previous equation. We replace the 8 in the last equation with the expression for 8 of the previous equation to get 1 = 9 - 1 ×(17 - 1 × 9). We now simplify, but not too much ... we have to make sure that no 9's or 17's disappear. Thus, we would write 1 = 9 - 1 ×17 + 1 × 9 = 9 -17 + 9 = 9 × 2 - 17 × 1. From this we see that ? = 2 and ?? = 1.
Let's do this again with a longer example, say finding (1 ÷ 7) mod 25. First go through Euclid's method to find the greatest common divisor of 7 and 25:
- 25/7 = 3 + 4/7 ===> 4 = 25 - 3 × 7
- 7/4 = 1 + 3/4 ===> 3 = 7 - 1 × 4
- 4/3 = 1 + 1/3 ===> 1 = 4 - 1 × 3
- 3/1 = 3 + 0
Now starting with the next to last equation, 1 = 4 - 1 × 3, we replace the 3 by the previous equation, 1 = 4 - 1 ×(7 - 1 × 4), and now replace the 4's by the first equation, 1 = (25 - 3 × 7) - 1 × (7 - 1 ×(25 - 3 × 7)). Finally, we simplify by grouping the 25's and 7's together. 1 = 25 - (3 × 7) - 1 × (7 - 1 × 25 + 3 × 7) = 25 - (3 × 7) - (1 × 7) + (1 × 25) - (3 × 7) = 25 × 2 - 7 × 7. So this time ? = -7 and ?? = 2. Since - 7 = 18 mod 25, we have found that (1 ÷ 7) mod 25 = 18.
Use this method to find the answers to these division problems.
- (1 ÷ 9) mod 17 = .
- (1 ÷ 5) mod 24 = .
- (1 ÷ 6) mod 35 = .
Click here to see the answers.
We can now put this all together to answer our division problems. Let's find (4 ÷ 9) mod 21. We start by finding (1 ÷ 9) mod 21.
- 21/9 = 2 + 3/9 ===> 3 = 21 - 2 × 9
- 9/3 = 3 + 0
We stop here because we have found that the greatest common divisor of 9 and 21 is 3. Since this is not 1, we know that this problem can not be done! Now, let's find (4 ÷ 9) mod 25. We start by finding (1 ÷ 9) mod 25.
- 25/9 = 2 + 7/9 ===> 7 = 25 - 2 × 9
- 9/7 = 1 + 2/7 ===> 2 = 9 - 1 × 7
- 7/2 = 3 + 1/2 ===> 1 = 7 - 3 × 2
Since the greatest common divisor of 9 and 25 is 1 we know that there will be an answer. We find it by making the backward substitutions, 1 = 7 - 3 ×(9 - 1 ×(25 - 2 × 9)) = (25 - 2 × 9) - (3 × 9) + (3 × 25) - (6 × 9) = -11 × 9 + 4 × 25 = 9 × -11 + 25 × 4. So, (1 ÷ 9) mod 25 = -11 mod 25 = 14. Finally, (4 ÷ 9) mod 25 = (4 × 14) mod 25 = 56 mod 25 = 6. As a check, we calculate that 9 × 6 mod 25 = 54 mod 25 = 4.
Use this method to find the answers to these division problems.
- (2 ÷ 3) mod 5 =
- (5 ÷ 3) mod 6 =
- (2 ÷ 5) mod 6 =
- (13 ÷ 6) mod 18 =
- (12 ÷ 7) mod 25 =
Click here to see the answers.
In the next section we will see how we can use clock arithmetic (including division) to create secret messages.
Answers to Greatest Common Divisors Questions
- 1; 102/25 = 4 + 2/25; 25/2 = 12 + 1/2; 2/1 = 2 + 0.
- 9; 243/198 = 1 + 45/198; 198/45 = 4 + 18/45; 45/18 = 2 + 9/18; 18/9 = 2 + 0.
- 77; 7469/2464 = 3 + 77/2464; 2464/77 = 32 + 0.
- 1; 4999/1109 = 4 + 563/1109; 1109/563 = 1 + 546/563; 563/546 = 1 + 17/546; 546/17 = 32 + 2/17; 17/2 = 8 + 1/2; 2/1 = 2 + 0.
Return to Questions
Answers to Division Questions
- 12; since 6 × 2 mod 17 = 12. Check: 9 × 12 mod 17 = 108 mod 17 = 6.
- 12; since 12 × 5 mod 24 = 60 mod 24 = 12. Check: 5 × 12 mod 24 = 60 mod 24 = 12.
- 13; since 8 × 6 mod 35 = 48 mod 35 = 13. Check: 6 × 13 mod 35 = 78 mod 35 = 8.
Return to Questions
Answers to Division Questions
- 2;
17/9 = 1 + 8/9 ===> 8 = 17 - (1 × 9)
9/8 = 1 + 1/8 ===> 1 = 9 - (1 × 8)
1 = 9 - (1 ×(17 - (1 × 9))) = 9 -17 + 9 = 9 × 2 - 17 × 1.
- 5;
24/5 = 4 + 4/5 ===> 4 = 24 - (4 × 5)
5/4 = 1 + 1/4 ===> 1 = 5 - (1 × 4)
1 = 5 - (1 ×(24 - (4 × 5))) = 5 - 24 + (4 × 5) = 5 × 5 - 24 × 1.
- 6;
35/6 = 5 + 5/6 ===> 5 = 35 - (5 × 6)
6/5 = 1 + 1/5 ===> 1 = 6 - (1 × 5)
1 = 6 - (1 ×(35 - (5 × 6))) = 6 - 35 + (5 × 6) = 6 × 6 - 35 × 1.
Return to Questions
Answers to Division Questions
- 4;
5/3 = 1 + 2/3 ===> 2 = 5 - (1 × 3)
3/2 = 1 + 1/2 ===> 1 = 3 - (1 × 2)
1 = 3 - (1 ×(5 - (1 × 3))) = 3 -5 + 3 = 3 × 2 - 5 × 1.
So, (1 ÷ 3) mod 5 = 2 and therefore (2 ÷ 3) mod 5 = 2 × 2 mod 5 = 4.
- Can not be done, since the greatest common divisor of 3 and 6 is 3.
- 4;
6/5 = 1 + 1/5 ===> 1 = 6 - (1 × 5)
So, (1 ÷ 5) mod 6 = -1 mod 6 = 5 and therefore (2 ÷ 5) mod 6 = 2 × 5 mod 6 = 10 mod 6 = 4.
- Can not be done, since the greatest common divisor of 6 and 18 is 6.
- 16;
25/7 = 3 + 4/7 ===> 4 = 25 - (3 × 7)
7/4 = 1 + 3/4 ===> 3 = 7 - (1 × 4)
4/3 = 1 + 1/3 ===> 1 = 4 - (1 × 3)
1 = 4 - (1 ×(7 - (1 × (25 - (3 × 7)))) = 25 - (3 × 7) - (1 × 7) + (1 × 25) - (3 × 7) = 7 × -7 + 25 × 2.
So, (1 ÷ 7) mod 25 = -7 mod 25 = 18, and therefore, (12 ÷ 7) mod 25 = 12 × 18 mod 25 = 216 mod 25 = 16.
Return to Questions