/****************************************************************************/
/* Resuelve congruencias lineales en dos variables                          */
/* ax + by = c (mod m)                                                      */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>

long mcd(long,long,long *, long *);

main()
{
	long a,b,c,m,a1,b1,a2,b2,n,r,x0,y0;

	printf("Este programa resuelve ecuaciones ax + by = c (mod m)\n\n");
	printf("a= "); scanf("%ld",&a);
	printf("b= "); scanf("%ld",&b);
	printf("c= "); scanf("%ld",&c);
	printf("m= "); scanf("%ld",&m);

	/* La ecuacion tiene solucion si y solo si el mcd(a,b,m) divide a c */
	n=mcd(a,b,&a1,&b1);
	r=mcd(n,m,&a2,&b2);
	if (c/r != (float)c/r) {
		printf("La ecuacion no tiene solución.\n");
		return 1;
	}
	
	/* Encontrar una solucion particular */
	printf("\nLa solución de %ldx+%ldy = %ld (mod %ld) es:\n"
			,a,b,c,m);
	printf("x= %ld y= %ld\n",c/r*a2*a1,c/r*a2*b1);
	return 0;
}
	
	
/* ------------------------------------------------------------------
 * Entrada: a y b enteros long, alfa, beta y m punteros a long
 * Salida : ninguna
 * Efecto : *m contendrá el mcd de a y b
 *          *alfa y *beta los enteros tales que m=alfa*a+beta*b
 --------------------------------------------------------------------*/

long mcd(long a, long b, long *alfa, long *beta)
{
	long s0,t0,s1,t1,s,t,q,r=1;
	
	if (a<b) return mcd(b,a,beta,alfa);
	s0=1; t0=0;
	s1=0; t1=1;
	while (r != 0) {
		q = a/b;
		r = a%b;
		s = s0 - q*s1;
		t = t0 - q*t1;
		s0=s1; t0=t1;
		s1=s ; t1=t ;
		a =b ; b =r ;
	}
	*alfa=s0;
	*beta=t0;
	return a;
}