¿es para AHORA! teorema chino del resto...?
la cosa es asi tengo que hacer un trabajo y llege a una parte donde habla sobre congruencuas y el teorema chino del resto, me lei toda la explicacion y la entiendo pero en una parte me trabo asi que busque en internet si habia algo mas facil y siiiii encontre esto:
"La forma de encontrar la solución nos la da la demostración del teorema. En ella se calculan los números Mi = (m1.m2...mk) / mi (o equivalentemente el producto de todos los módulos excepto el i-simo y los enteros Yi que son los inversos de Mi módulo mi. A continuación se demuestra que el número
x = a1.M1.Y1 + a2.M2.Y2 + ... + ak.Mk.Yk
es la solución buscada"
la cosa es que cuando se refiere a sacar el inverso del modulo no se como se hace? si alguien entiende esto por favor que me ayude...es muy urgente y necesario.
Answers & Comments
Verified answer
HAY TE VA EL INVERSO DEL MODULO:
DE TODAS FORMAS TE ENVIO ENLACES.
Entrada: a un entero, m el modulo, inv contendra el resultado
* Salida : 0-->Ok, 1-->Error, no inversible
* Efecto : *inv contiene el inverso de a modulo m cuando sea posible
*/
int invmod(long a, long m, long *inv)
{
long alfa, beta, r;
mcd_aux(a,m,&alfa,&beta,&r);
if (r!=1) return 1;
*inv = alfa;
if (*inv<0) *inv += m;
return 0;
}
/*
* funcion mcd_aux()
* Descrip: calcula el mcd de dos enteros y los coeficientes que
* permiten expresar dicho mcd como combinacion lineal
* de dichos enteros.
* Entrada: a y b enteros long, alfa, beta y m punteros a long
* Salida : ninguna
* Efecto : *m contendra el mcd de a y b
* *alfa y *beta los enteros tales que m=alfa*a+beta*b
*/
void mcd_aux(long a, long b, long *alfa, long *beta, long *m)
{
long s0,t0,s1,t1,s,t,q,r=1;
if (a<b) return mcd_aux(b,a,beta,alfa,m);
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 ;
}
*m=a;
*alfa=s0;
*beta=t0;
return;
}
COMO YO NO LO ENTENDÍ TE ENVIO ENLACES DONDE LO EXPLICAN ESPECIFICAMENTE Y MEJOR.
a los chinos nunca les sobra nada.