/****************************************************************************/ /* 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); }