bezout_coeffs.c

#include <stdio.h>


int xgcd(int a, int b) {
     int r = b, old_r = a;
     int t = 1, old_t = 0;
     int s = 0, old_s = 1;
     int quotient;
     int temp;
     
     while (r != 0) {
          quotient = old_r / r;

          // Update r and old_r
          temp = r;
          r = old_r - quotient * r;
          old_r = temp;

          // Update s's
          temp = s;
          s = old_s - quotient * s;
          old_s = temp;

          // Update t's
          temp = t;
          t = old_t - quotient * t;
          old_t = temp;
     }

     printf("Bezout's coefficients: (%d) * %d  + (%d) * %d\n", old_s, a, old_t, b);
     printf("gcd(%d, %d) = %d\n", a, b, old_r);

     if (old_r == 1) {
          if (old_t < 0)
               old_t += a;
          printf("Multiplicative inverse of %d mod %d = %d\n", b, a, old_t);
     }
}


int main(int ac, char *av[]) {
     int tests[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     int i;
     int j;
     
     for (i = 0; i < 10; ++i)
          for (j = 0; j < 10; ++j)
               xgcd(i, j);

     return 0;
}