#include <stdio.h>

void  quasi_inverse ( int a, int b )
{
  int x, y, xo, yo, c, d, t, q, r;
  c = a; d = b;  x = 0; yo = 0;  y = 1; xo = 1;
  while ( (r = c%d) > 0 ) {
    q = c/d;
    c = d; d = r;
    t = xo; xo = x; x = t-q*x;
    t = yo; yo = y; y = t-q*y;
  }
  printf("Inputs a=%d, b=%d;  Outputs x=%d, y=%d, and gcd(a,b)=d=%d\n",
	 a, b, x, y, d );
  return;
}

main ( void )
{
  int a, M;
  printf("Compute the quasi-inverse of an integer a modulo M\n");
  printf("Enter a: "); scanf("%d", &a);
  printf("Enter M: "); scanf("%d", &M);
  quasi_inverse ( a, M );
  exit(0);
}