The Extended
Euclidean Algorithm


The greatest common divisor (GCD) of two integers (a and b) is the largest integer that can evenly (without remainder) divide both. For example:

In the examples above, the largest integer that can evenly divide both a and b is easily found and emphasized in bold. We can make an observation and see that GCD(a,b) will also divide a - b. We generally write x | y to say that x "divides" y. So, using our examples above:

The Extended Euclidean Algorithm determines GCD(a,b) and integers s,t such that a s + b t = GCD(a,b). For example:

IMPORTANT NOTE:If GCD(a,b) = 1, this means that a and b are relatively prime. This is important because in this case: For example:

PUTTING IT TO THE TEST

You can use the form below to specify your own values for a and b. Make sure that both integers are positive and different:

a =
b =

A FINAL NOTE

You may be wondering what in the world all this information can be used for. It has its multitude of applications, especially in the area of cryptology. My goal here is not to discuss cryptology, but rather to share with you a little of what I learned. I find it beneficial to put together something like this. It helps me understand the material better... and remember it. My hope is that you receive something from my efforts. If you have any questions, criticism or suggestions, feel free to send them my way. Use this information and enjoy it, but above all, share it with someone else!


Last modified on:
Copyright 2003, Jean Gourd (Jean.Gourd@usm.edu)