# The ExtendedEuclidean 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:

• 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

IMPORTANT NOTE:If GCD(a,b) = 1, this means that a and b are relatively prime. This is important because in this case:
• s is the inverse of a (modulo b), which means that a s = 1 (modulo b)
• If s is negative, then it is a multiplicative inverse of a (modulo b). However, since it's not in the range from 0 to b, we take b + s to be the multiplicative inverse of a (modulo b)
• t is the inverse of b (modulo a), which means that b t = 1 (modulo a)
• If t is negative, then it is a multiplicative inverse of b (modulo a). However, since it's not in the range from 0 to a, we take a + t to be the multiplicative inverse of b (modulo a)
For example:
• a=21, b=16: from above we know that GCD(21,16) = 1, s=-3 and t=4.
• -3 is negative, so it is an inverse of 21 (modulo 16). However, since it's not in the range from 0 to 16, we take 13 to be the inverse of 21 (modulo 16), since -3 + 16 = 13.
• 13 is the inverse of 21 (modulo 16), which means that 21(13) = 1 (modulo 16). Sure enough, we can see that 21(13) / 16 = 17 + 1.
• 4 is the inverse of 16 (modulo 21), which means that 16(4) = 1 (modulo 21). Sure enough, we can see that 16(4) / 21 = 3 + 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 = 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!