Cryptography: The Euclidean Algorithm

The Euclidean Algorithm finds the greatest common divisor of two integers a and b.

For example,
If we want to find gcd(287, 91), we divide 287 by 91:

                            287 = 91*3 + 14

We know that for integers a, b and c, if a | b and a | c, then a | (b + c).

Therefore, any divisor of 287 and 91 must also be a divisor of 287 - 91*3 = 14.

Consequently, gcd(287, 91) = gcd(14, 91).

In the next step, we divide 91 by 14:

91 = 14*6 + 7

This means that gcd(14, 91) = gcd(14, 7).

So we divide 14 by 7:

14 = 7*2 + 0
We find that 7 | 14, and thus gcd(14, 7) = 7.

Therefore, gcd(287, 91) = 7.

So, what is gcd( 70, 38 )?

------------------------------------------------------------------------------------------------------------------------
The Euclidean algorithm can be based on the following theorem: For any nonnegative integer a and any positive integer b,
            gcd(a, b) = gcd(b, a mod b)
        gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11