/****************************************************************************/
/* Aplicación del pequeño teorema de Fermat a la resolución de              */
/* ecuaciones lineales con congruencias.                                    */
/*                                                                          */
/* Pequeño teorema de Fermat: sean p un número primo y 'a' un               */
/* entero que no es multiplo de p, entonces a^(p-1)=1 (mod p)               */
/*                                                                          */
/* Por tanto a^(p-2)*a = a^(p-1) = 1 (mod p)                                */
/* Asi que la ecuacion ax = b (mod p) puede resolverse asi:                 */
/* a^(p-2)*ax = a^(p-2)*b ==> x = a^(p-2)*b (mod p)                         */                               */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>

void uso(void);

int main()
{
	unsigned long a,b,c=1,p,i;

	printf("Este programa resuelve congruencias del tipo ax = b\n");
	printf("a,b enteros positivos, p primo y p no divide a 'a'.\n");

	printf("a= "); scanf("%ld",&a);
	printf("b= "); scanf("%ld",&b);
	printf("p= "); scanf("%ld",&p);

	if ((float)a/p == a/p) {
		printf("p no debe dividir a 'a'\n");
		return 1;
	}
	for (i=0; i<p-2; i++) c= (c*a)%p;

	printf("\n %ldx = %ld mod %ld ; ",a,b,p);
	printf("x= %ld\n",(c*b)%p);

	return 0;
}