/****************************************************************************/
/* Sistemas de congruencias lineales de dos ecuaciones con dos              */
/* incognitas:                                                              */
/*  | ax+by = e (mod m)                                                     */
/*<                                                                         */
/*  | cx+dy = f (mod m)                                                     */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>

long invmod(long,long);
long coef1(long,long);
long coef2(long,long);

int main(void)
{
	long  a,b,c,d,e,f,m,delta,invdelta;

	printf("Soluciones de sistemas de congruencias\n");
	printf(" | ax+by = e (mod m)\n");
	printf(" | cx+dy = f (mod m)\n\n");

	printf("Primera ecuación:\n");
	printf("a= ");scanf("%ld",&a);
	printf("b= ");scanf("%ld",&b);
	printf("e= ");scanf("%ld",&e);
	printf("Segunda ecuación:\n");
	printf("c= ");scanf("%ld",&c);
	printf("d= ");scanf("%ld",&d);
	printf("f= ");scanf("%ld",&f);
	printf("Módulo m= ");scanf("%ld",&m);

	delta=a*d-b*c;
	invdelta=invmod(delta,m);
	if (invdelta==-1) {
		printf("El sistema no tiene solución.\n");
		return 1;
	}
	
	printf("Solucion: \n");
	printf("x= %ld\n",(invdelta*(d*e-b*f))%m);
	printf("y= %ld\n",(invdelta*(a*f-c*e))%m);

	return 0;
}


/*---------------------------------------------------------------------
  Teorema de Bezout: si c=mcd(a,b) entonces existen enteros
  alfa y beta tales que c= alfa*a + beta*b
----------------------------------------------------------------------*/

long coef1(long a,long b)
{
    if (a%b==0) return (0);
    else return (coef2(b,a%b));
}
long coef2(long a, long b)
{
    if (a%b==0) return(1);
    else return (coef1(b,a%b)- a/b *coef2(b,a%b));
}

/*----------------------------------------------------------------------
  Calculo del inverso modulo un entero.
  Suponiendo que 1=mcd(m,n) entonces existen enteros a y b tales que
  1=m.a+n.b y por tanto a es un inverso de a modulo n

  Devuelve el inverso de m modulo n o -1 si no es inversible.
----------------------------------------------------------------------*/

long invmod(long m,long n)
{
	long a,b;

    a=coef1(m,n);
	b=coef2(m,n);
	if (m*a+n*b!=1) return -1;
	else return a;
}