Deje un número entero [matemática] x [/ matemática] [matemática] \ equiv [/ matemática] [matemática] r_1 [/ matemática] (mod [matemática] d_1 [/ matemática]), [matemática] \ equiv [/ matemática] [ matemática] r_2 [/ matemática] (mod [matemática] d_2 [/ matemática]), [matemática] \ equiv [/ matemática] [matemática] r_3 [/ matemática] (mod [matemática] d_3 [/ matemática]),…, [matemática] \ equiv [/ matemática] [matemática] r_n [/ matemática] (mod [matemática] d_n [/ matemática]). Dado [math] (r_i, d_i) \ forall i = 1 – n [/ math], ¿siempre es posible determinar [math] x [/ math] para cualquier [math] n [/ math]?

Answer 1

El teorema relevante se llama Teorema del resto chino, que debe buscar.

Dado:

[matemáticas] x \ equiv r_1 (\ hbox {mod} \, d_1) [/ matemáticas]
[matemáticas] \ vdots [/ matemáticas]
[matemáticas] x \ equiv r_n (\ hbox {mod} \, d_n) [/ matemáticas]

Entonces puede encontrar [math] r [/ math] tal que:

[matemáticas] x \ equiv r (\ hbox {mod} \, \ hbox {lcm} (d_1 \ cdots d_n)) [/ matemáticas]

Es decir, puede encontrar el módulo restante el mínimo común múltiplo de los módulos. El teorema del resto chino establece que siempre hay una solución si los módulos son coprimos.

La solución es muy simple; puedes hacerlo combinando pares de ecuaciones. Entonces, por ejemplo, suponga que:

[matemáticas] x \ equiv 1 (\ hbox {mod} \, 11) [/ matemáticas]
[matemáticas] x \ equiv 3 (\ hbox {mod} \, 13) [/ matemáticas]

El mínimo común múltiplo de 11 y 13 es 143.

Esto significa que [matemática] (x-1) [/ matemática] es divisible por [matemática] 11 [/ matemática] y [matemática] (x-3) [/ matemática] es divisible por [matemática] 13 [/ matemática] . Es decir, hay números enteros [matemática] \ alpha <13 [/ matemática] y [matemática] \ beta <11 [/ matemática] tales que:

[matemáticas] x \ equiv 11 \ alpha + 1 (\ hbox {mod} \, 143) [/ matemáticas]
[matemáticas] x \ equiv 13 \ beta + 3 (\ hbox {mod} \, 143) [/ matemáticas]

Resolver para [math] \ alpha [/ math] da:

[matemáticas] \ alpha = \ frac {13 \ beta + 2} {11} = \ beta + \ frac {2 (\ beta + 1)} {11} [/ matemáticas]

Entonces, si [math] 13 \ beta + 2 [/ math] es divisible por 11, [math] \ beta + 1 [/ math] también debe ser divisible por 11. Por lo tanto, [math] \ beta = 10 [/ math] y:

[matemáticas] x \ equiv 133 (\ hbox {mod} \, 143) [/ matemáticas]

Hemos combinado las dos ecuaciones en una. Ahora podemos hacer el siguiente paso:

[matemáticas] x \ equiv 133 (\ hbox {mod} \, 143) [/ matemáticas]
[matemáticas] x \ equiv 7 (\ hbox {mod} \, 17) [/ matemáticas]

El mcm de 143 y 17 es 2431. Por lo tanto, deben existir enteros [math] \ alpha <143 [/ math] y [math] \ beta <17 [/ math] de manera que:

[matemáticas] x \ equiv 143 \ alpha + 133 (\ hbox {mod} \, 2431) [/ matemáticas]
[matemáticas] x \ equiv 13 \ beta + 7 (\ hbox {mod} \, 2431) [/ matemáticas]

Resolver para [math] \ beta [/ math] esta vez da:

[matemáticas] \ beta = \ frac {143 \ alpha + 126} {17} = 8 \ alpha + 7 + \ frac {7 (\ alpha + 1)} {17} [/ matemáticas]

Una vez más, [math] \ alpha = 16 [/ math], y así:

[matemáticas] x \ equiv 2421 (\ hbox {mod} \, 2431) [/ matemáticas]

Entonces, la solución a su sistema de ecuaciones es [matemáticas] x = 2431n + 2421 [/ matemáticas] para cualquier número entero n.