Thank you for visiting our site! You landed on this page because you entered a search term similar to this:

__how to calculate greatest common divisor__, here's the result:

gcd(15, 5) = 5, | gcd(7, 9) = 1, | gcd(12, 9) = 3, | gcd(81, 57) = 3. |

The gcd of two integers can be found by repeated application of the division algorithm, this is known as the ** Euclidean Algorithm**. You repeatedly divide the divisor by the remainder until the remainder is 0. The gcd is the last non-zero remainder in this algorithm. The following example shows the algorithm.

Finding the gcd of 81 and 57 by the Euclidean Algorithm:

57 = 2(24) + 9

24 = 2(9) + 6

9 = 1(6) +

**3**

6 = 2(3) + 0.

It is well known that if the gcd(a, b) = r then there exist integers p and s so that:

Starting with the next to last line, we have:

**3**= 9 -1(6)

**3**= 9 - 1(24 - 2(9)) = 3(9) - 1(24).

**3**= 3( 57 - 2(24)) - 1(24) = 3(57) - 7(24).

**3**= 3(57) - 7( 81 - 1(57)) = 10(57) -7(81).

The procedure we have followed above is a bit messy because of all the back substitutions we have to make. It is possible to reduce the amount of computation involved in finding p and s by doing some auxillary computations as we go forward in the Euclidean algorithm (and no back substitutions will be necessary). This is known as the ** extended Euclidean Algorithm**.

Before presenting this extended Euclidean algorithm, we shall look at a special application that is the most common usage of the algorithm. We will give a form of the algorithm which only solves this special case, although the general algorithm is not much more difficult.

Consider the problem of setting up the Hill cryptosystem. We were forced to do arithmetic modulo 26, and sometimes we had to find the inverse of a number mod 26. This turned out to be a difficult task (and not always possible). We observed that a number x had an inverse mod 26 (i.e., a number y so that xy = 1 mod 26) if and only if gcd(x, 26) = 1. There is nothing special about 26 here, so let us consider the general case of finding inverses of numbers modulo n. The inverse of x exists if and only if gcd(x, n) = 1. We now know that if this is true, there exist integers p and s so that

### The Extended Euclidean Algorithm for finding the inverse of a number mod n.

We will number the steps of the Euclidean algorithm starting with step 0. The quotient obtained at step i will be denoted by q_{i}. As we carry out each step of the Euclidean algorithm, we will also calculate an auxillary number, p

_{i}. For the first two steps, the value of this number is given: p

_{0}= 0 and p

_{1}= 1. For the remainder of the steps, we recursively calculate p

_{i}= p

_{i-2}- p

_{i-1}q

_{i-2}(mod n). Continue this calculation for one step beyond the last step of the Euclidean algorithm.

The algorithm starts by "dividing" n by x. If the last non-zero remainder occurs at step k, then if this remainder is 1, x has an inverse and it is p_{k+2}. (If the remainder is not 1, then x does not have an inverse.) Here is an example:

#### Find the inverse of 15 mod 26.

Step 0: | 26 = 1(15) + 11 | p_{0} = 0 |

Step 1: | 15 = 1(11) + 4 | p_{1} = 1 |

Step 2: | 11 = 2(4) + 3 | p_{2} = 0 - 1( 1) mod 26 = 25 |

Step 3: | 4 = 1(3) + 1 | p_{3} = 1 - 25( 1) mod 26 = -24 mod 26 = 2 |

Step 4: | 3 = 3(1) + 0 | p_{4} = 25 - 2( 2) mod 26 = 21 |

p_{5} = 2 - 21( 1) mod 26 = -19 mod 26 = 7 |