Get it on Google Play Get it on Apple Store



CALCULATE GREATEST COMMON DIVISOR
multiplying,dividing,adding,subtracting integers,pre-algebra ratio formula,quadratic equation extracting square root,convert decimal to square root fraction,quadratic equations square root property calculator,Simplifying a sum of radical expressions calculator,simplifying cube root fractions,solving multiple variable polynomial equation,adding, subtracting, multiplying, dividing integers,online factoring of complex quadratic equations with variables only,solving addition and subtraction equations worksheet,how do you divide and times add subtract integers worksheet,solving 2nd order differential equations,multiplying and dividing powers cheat,converting base 8 to decimal calculator,Adding, subtracting, multiplying and dividing Integer worksheets,how do i convert a basic algebraic equation,prealgebra solving equations by multiplying and dividing worksheet,simultaneous nonlinear equation solver,simplify square root of difference of two squares,Like Terms Simplifying Algebraic Expressions Junior High,value for variable expression radicals roots,finding least common denominator to equations,quadratic equation graph hyperbola,how use my Casio Calculator for solving linear equations,adding subtracting multiplying dividing integers,how do you do the square root on the TI-83 plus graphic calculator?,solving quadratic equations completing the square,Like Terms Simplifying Algebraic Expressions Activities Lessons,greatest common divisor calculator,Java method Convert Decimal Numbers to time,greatest common factor for three number with variables,distributions,partial differential equations,difference between evaluation and simplification of an expression,adding and subtracting fractions with like denominators worksheet,worksheet on adding,subtracting,multiplying,dividing integers,adding subtracting dividing multiplying integers games,integers adding, subtracting, multiplying, dividing worksheet,simplifying exponents and square root calculator,multiply and divide rational expressions calculator,free advanced algebra add subtract rational expressions,practice worksheets on adding, subtracting,multiplying,and dividing decimals. for 6th grade,worksheets on add subtract multiply divide fractions
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
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.

  1. 102 and 25
  2. 198 and 243
  3. 7469 and 2464
  4. 1109 and 4999
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.

  1. (6 ÷ 9) mod 17, if you know that (1 ÷ 9) mod 17 = 2.
  2. (12 ÷ 5) mod 24, if you know that (1 ÷ 5) mod 24 = 5.
  3. (8 ÷ 6) mod 35, if you know that (1 ÷ 6) mod 35 = 6.
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. (1 ÷ 9) mod 17 = .
  2. (1 ÷ 5) mod 24 = .
  3. (1 ÷ 6) mod 35 = .
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.

  1. (2 ÷ 3) mod 5 =
  2. (5 ÷ 3) mod 6 =
  3. (2 ÷ 5) mod 6 =
  4. (13 ÷ 6) mod 18 =
  5. (12 ÷ 7) mod 25 =
to see the answers.

In the next section we will see how we can use clock arithmetic (including division) to create secret messages.

  1. 1; 102/25 = 4 + 2/25; 25/2 = 12 + 1/2; 2/1 = 2 + 0.
  2. 9; 243/198 = 1 + 45/198; 198/45 = 4 + 18/45; 45/18 = 2 + 9/18; 18/9 = 2 + 0.
  3. 77; 7469/2464 = 3 + 77/2464; 2464/77 = 32 + 0.
  4. 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.

  1. 12; since 6 × 2 mod 17 = 12. Check: 9 × 12 mod 17 = 108 mod 17 = 6.
  2. 12; since 12 × 5 mod 24 = 60 mod 24 = 12. Check: 5 × 12 mod 24 = 60 mod 24 = 12.
  3. 13; since 8 × 6 mod 35 = 48 mod 35 = 13. Check: 6 × 13 mod 35 = 78 mod 35 = 8.

  1. 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.

  2. 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.

  3. 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.

  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.

  2. Can not be done, since the greatest common divisor of 3 and 6 is 3.
  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.
  4. Can not be done, since the greatest common divisor of 6 and 18 is 6.
  5. 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.