/****************************************************************************/ /* Solucion de congruencias lineales ax = b (mod m) */ /* */ /* Jaime Suarez <mcripto@bigfoot.com> 2003 */ /* en http://elparaiso.mat.uned.es */ /****************************************************************************/ #include <stdio.h> long mcd(long a, long b, long *alfa, long *beta); int main() { long a,b,m,d,alfa,beta,x0; int t; printf("Solución de la congruencia lineal ax = b (mod m)\n"); printf("a= "); scanf("%ld",&a); printf("b= "); scanf("%ld",&b); printf("m= "); scanf("%ld",&m); d=mcd(a,m, &alfa, &beta); if ((float)b/d != b/d) { printf("La congruencia no tiene solución.\n"); return 0; } /* Solucion particular */ x0 = (alfa*b/d)%m; /* Todas las soluciones son ...*/ printf("Hay %ld soluciones no congruentes entre sí:\n",d); if (d>6) { for (t=0; t<6; t++) printf("x=%ld ",x0+m/d*t); printf("..."); } else for (t=0; t<d; t++) printf("x=%ld ",x0+m/d*t); printf("\n"); return 0; } /* ------------------------------------------------------------------ * Entrada: a y b enteros long, alfa, beta y m punteros a long * Salida : ninguna * Efecto : *m contendrá el mcd de a y b * *alfa y *beta los enteros tales que m=alfa*a+beta*b --------------------------------------------------------------------*/ long mcd(long a, long b, long *alfa, long *beta) { long s0,t0,s1,t1,s,t,q,r=1; if (a<b) return mcd(b,a,beta,alfa); s0=1; t0=0; s1=0; t1=1; while (r != 0) { q = a/b; r = a%b; s = s0 - q*s1; t = t0 - q*t1; s0=s1; t0=t1; s1=s ; t1=t ; a =b ; b =r ; } *alfa=s0; *beta=t0; return a; }