The greatest common divisor (GCD) of two integers (a and b) is the largest integer that can evenly (without remainder) divide both. For example:
GCD(10,5) = 5 --> The factors of 5 are 1,5 and the factors of 10 are 1,2,5,10
GCD(12,9) = 3 --> The factors of 9 are 1,3,9 and the factors of 12 are 1,2,3,4,6,12
GCD(21,16) = 1 --> The factors of 16 are 1,2,4,8,16 and the factors of 21 are 1,3,7,21
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:
GCD(10,5) = 5 --> 5 | (10 - 5) --> 5 | 5
GCD(12,9) = 3 --> 3 | (12 - 9) --> 3 | 3
GCD(21,16) = 1 --> 1 | (21 - 16) --> 1 | 5
The Extended Euclidean Algorithm determines GCD(a,b) and integers s,t such that a s + b t = GCD(a,b). For example:
a=10, b=5: from above, we know that GCD(10,5) = 5, and by doing the Extended Euclidean Algorithm, we also find that s=0 and t=1 --> 10(0) + 5(1) = 5
a=12, b=9: from above, we know that GCD(12,9) = 3, and by doing the Extended Euclidean Algorithm, we also find that s=1 and t=-1 --> 12(1) + 9(-1) = 3
a=21, b=16: from above, we know that GCD(21,16) = 1, and by doing the Extended Euclidean Algorithm, we also find that s=-3 and t=4 --> 21(-3) + 16(4) = 1
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 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!