/****************************************************************************/
/* Resuelve congruencias lineales ax=b (mod m) para valores de              */
/* a y m positivos y primos entre si.                                       */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>

#define PAR(x) !((x) & 1)


long mcd(long a, long b);

main()
{
	long a,b,m, a1,b1;
	
	printf("Solucion de congruencias ax = b (mod m)\n");
	printf("con a y m positivos y primos entre si.\n\n");
	printf("a= "); scanf("%ld",&a);
	printf("b= "); scanf("%ld",&b);
	printf("m= "); scanf("%ld",&m);
	if (a<=0 || m<=0) 
		{printf("a y m deben ser positivos\n");return 1;}
	if (mcd(a,m)!= 1) 
		{printf("a y m deben ser primos entre si.\n"); return 1;}
	
	/* ax=b (mod m) tiene las mismas soluciones que a'x= b' (mod m) */
	/* donde a'es m módulo a y b' es -b.[m/a]                       */
	while (a!=1) {
		a1= m%a;
		b1= -b*(m/a)%m;
		a=a1; b=b1;
	}
	printf("Solución: x= %ld\n",b);
	return 0;
}

long mcd(long a, long b)
{
	if (a==b) return a;
	else if (a<b) return mcd(b,a);
	else if ( PAR(a) &&  PAR(b))  return 2*mcd(a>>1,b>>1);
	else if ( PAR(a) && !PAR(b))  return mcd(a>>1,b);
	else if (!PAR(a) &&  PAR(b))  return mcd(a,b>>1);
	else return mcd(a-b,b);
}