extended euclidean algorithm

The extended Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers, as well as the coefficients that satisfy Bézout's identity. Bézout's identity states that for any two integers a and b, there exist integers x and y such that ax + by = gcd(a, b).

The algorithm is based on the observation that if (x, y) is a solution to ax + by = gcd(a, b), then (y, x % y) is a solution to b(y) + (a % b)(x % y) = gcd(b, a % b), where % denotes the modulo operation.

Here is a step-by-step explanation of the extended Euclidean algorithm:

  1. Initialization: We start with the given integers a and b, where a > b. We set r0 = a, r1 = b, x0 = 1, x1 = 0, y0 = 0, and y1 = 1.

  2. Euclidean Division: We compute the remainder ri (r_i = r_{i-2} % r_{i-1}) using the modulo operation until we obtain a remainder of 0. Let's say we reach a remainder rk = 0.

  3. Termination: We stop when we find rk = 0. The previous remainder, rk-1, is the GCD of a and b.

  4. Back Substitution: Starting from rk-1, we perform back substitution to find the coefficients x and y that satisfy ax + by = gcd(a, b). We use the following formulas:

  5. xi = xi-2 - (ri-2 / ri-1) * xi-1
  6. yi = yi-2 - (ri-2 / ri-1) * yi-1

We continue this process until we reach i = 1, where x = x1 and y = y1.

  1. Output: The GCD of a and b is rk-1, and the coefficients x and y satisfy ax + by = gcd(a, b).

By following these steps, you can use the extended Euclidean algorithm to find the GCD of two integers and the coefficients that satisfy Bézout's identity.