Thank you for visiting our site! You landed on this page because you entered a search term similar to this: calculate greatest common divisor, here's the result:
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
25 4 -- = 3 + - , 7 7
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
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.
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.
- 17 = 1 × 9 + 8, so 8 = 17 - 1 × 9.
- 9 = 1 × 8 + 1, so 1 = 9 - 1 × 8.
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
Use this method to find the answers to these division problems.
- (1 ÷ 9) mod 17 = .
- (1 ÷ 5) mod 24 = .
- (1 ÷ 6) mod 35 = .
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
- 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
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 =
In the next section we will see how we can use clock arithmetic (including division) to create secret messages.
- 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.
- 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.
- 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.
- 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.