/****************************************************************************/
/* Uso del algoritmo de Euclides para el m.c.d. aplicado al teorema         */
/* de Bezout y al calculo de inversos modulo un entero.                     */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/* Corregido Sept 2004. El resultado del módulo debe ser positivo           */
/****************************************************************************/

#include <stdio.h>


int invmod(int,int);
int coef1(int,int);
int coef2(int,int);

main()
{
    int a,b,alfa,beta,inv;

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

    printf("\n\nTeorema de Bezout:  ");
    alfa=coef1(a,b);
    beta=coef2(a,b);
    printf("mcd(%d,%d)= %d = %d*%d + %d*(%d)",
            a,b,alfa*a+beta*b,a,alfa,b,beta );

    inv=invmod(a,b); 
    if (inv!=-1)
         printf("\n\nEl inverso de %d modulo %d es %d\n",a,b,inv);
    else printf("\n\n%d no es inversible modulo %d.\n",a,b);
    return 0;
}

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

int coef1(int a,int b)
{
    if (a%b==0) return (0);
    else return (coef2(b,a%b));
}
int coef2(int a, int 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.
----------------------------------------------------------------------*/

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

    a=coef1(m,n);
	  b=coef2(m,n);
     if (m*a+n*b != 1) return 0;
     while(a<0) a += n;
     return a;
}