In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor (gcd) of integers a and b, the coefficients of Bezout's identity, that is integers x and y such that
ax + by = gcd(a,b)
The greatest common divisor (gcd) of two or more non-zero integers is the largest positive integer that divides the numbers without a remainder. For example, the gcd of 24 and 84 is 12.
∑
| Value of a and b | GCD(a,b) | Bezout Coefficients (x, y) |
|---|---|---|
| (2415, 3289) | 23 | x = -64, y = 47 |
| (4278, 8602) | 46 | x = -2, y = 1 |
| (963, 657) | 9 | x = -15, y = 22 |
| (24, 54) | 6 | x = -2, y = 1 |
| (36, 99) | 9 | x = 3, y = -1 |
| (624129, 2061517) | 18913 | x = -33, y = 10 |
| (1131, 741) | 39 | x = 2, y = -3 |
| (105, 252) | 21 | x = 5, y = -2 |
| (1406700, 164115) | 23445 | x = 2, y = -17 |
| (1368, 339) | 3 | x = -28, y = 113 |
| (55534, 434334) | 2 | x = 95057, y = -12154 |
| (30315475, 24440870) | 31415 | x = 337, y = -418 |
| (12345678912, 123456) | 192 | x = 97, y = -9700062 |