#include <stdio.h>
#include <stdlib.h>

#define DEBUG

/* pocita najvacsi spolocny delitel cisel a a b, musi platit a > b */
/* ub + va = nsd(a,b) */
int nsd(int a, int b, int * U, int * V)
{
	/* budem si pamatat 2 posledne hodnoty postupnosti s_k, u_k a v_k */
	int s[2], u[2], v[2], q, temp;
	
	/* pociatocna inicializacia */
	s[0] = a; s[1] = b;
	u[0] = 0; u[1] = 1;
	v[0] = 1; v[1] = 0;
	
	while (s[1] > 0) {
		/* vypocitam dalsi clen postupnosti s_k */
		q = s[0] / s[1];
		temp = s[0] % s[1];
		/* pamatam posledne dva cleny */
		s[0] = s[1];
		s[1] = temp;
		
		/* vypocitam dalsi clen postupnosti u_k */
		temp = u[0] - q * u[1];
		/* opat si pamatam posledne dva cleny */
		u[0] = u[1];
		u[1] = temp;
		
		/* vypocitam dalsi clen postupnosti v_k */
		temp = v[0] - q * v[1];
		/* opat si pamatam posledne dva cleny */
		v[0] = v[1];
		v[1] = temp;

#ifdef DEBUG
		fprintf(stderr, "%3d %3d %3d %3d\n", s[0], q, u[0], v[0]);
#endif
		
	}
	
	if (U != NULL) *U = u[0];
	if (V != NULL) *V = v[0];
	
	return s[0];
}

int main(int argc, char * argv[])
{
	int a, b, u, v, d;

	if (argc == 3) {
		a = atoi(argv[1]);
		b = atoi(argv[2]);
	} else {
		a = 27;
		b = 8;
	}

	fprintf(stdout, "a = %d\n", a);
	fprintf(stdout, "b = %d\n\n", b);

	d = nsd(a, b, &u, &v);
	fprintf(stdout, "u * b + v * a = nsd(a,b)\n");
	fprintf(stdout, "%d * %d + %d * %d = %d\n\n", u, b, v, a, 
		u * b + v * a);

	if (d == 1) {
		printf("b^{-1} mod a = u\n");
		printf("%d^{-1} mod %d = %d\n\n", b, a, 
			(u % a) > 0 ? (u % a) : a + (u % a));
	}

	return 0;
}