Podemos responder esto con bastante facilidad usando el Teorema del resto chino cuando a, byc son pares primos relativamente (no comparten factores).
Queremos una solución para este conjunto de ecuaciones en enteros:
[matemáticas] n \ equiv d \ mod a [/ matemáticas]
[matemáticas] n \ equiv e \ mod b [/ matemáticas]
[matemáticas] n \ equiv f \ mod c [/ matemáticas]
Deje [math] M = abc [/ math]. Además, permita que se calculen las siguientes variables con el algoritmo euclidiano extendido:
[matemáticas] i_a \ equiv (M / a) ^ {- 1} \ mod a [/ matemáticas]
[matemáticas] i_b \ equiv (M / b) ^ {- 1} \ mod b [/ matemáticas]
[matemáticas] i_c \ equiv (M / c) ^ {- 1} \ mod c [/ matemáticas]
- Un cierto número ‘C’ cuando se divide por N1 deja un resto de 13 y cuando se divide por N2 deja un resto de 1, donde N1 y N2 son los enteros positivos. ¿Cuál sería el valor de N1 + N2 si N1 / N2 = 5/4?
- [matemáticas] x ^ 2 [/ matemáticas] se puede escribir como [matemáticas] x \ cdot x [/ matemáticas] (‘[matemáticas] x [/ matemáticas] veces [matemáticas] x [/ matemáticas]’), pero ¿cómo puede [matemáticas] x ^ {1.5} [/ matemáticas] se escribirá?
- ¿Por qué es (4 ^ -3) (2 ^ -3) = 8 ^ -3 y no 8 ^ -6?
- Cómo evaluar: [matemáticas] \ sum_ {n = 0} ^ {\ infty} (1/2) ^ {n + 1} \ ln (2 ^ n) [/ matemáticas]
- ¿Por qué [math] \ log ^ {*} {(\ log {n})} = \ log ^ {*} {n} – 1 [/ math]?
Luego tenemos que [matemáticas] n \ equiv d * i_a * \ frac {M} {a} + e * i_b * \ frac {M} {b} + f * i_c * \ frac {M} {c} \ mod M [/ matemáticas]. La fórmula funciona para cualquier cantidad de residuos, la extensión se da en el enlace en la parte superior.
Cuando a, byc no son primos en pares, se vuelve un poco más complicado. Separe cada ecuación [math] n \ equiv x \ mod y [/ math] en un conjunto de ecuaciones, [math] n \ equiv x \ mod p ^ k [/ math] para cada potencia principal [math] p ^ k [ / math] que divide [math] y [/ math]. Si hay números primos repetidos, primero asegúrese de que no se contradicen entre sí (es decir, x = 0 mod 3 yx = 1 mod 9). Si lo hacen, no hay solución. Si no lo hacen, deshazte de todos menos del poder más alto. Finalmente, solo aplique el algoritmo en las ecuaciones restantes.