Decimos que dos números (enteros positivos) [matemática] a [/ matemática] y [matemática] b [/ matemática] son relativamente primos (primos entre sí), si no tienen factores primos comunes.
Decimos que los números [matemáticas] m_ {1}, m_ {2}, … m_ {r} [/ math], par sabio relativamente primo si dos números distintos en esa colección son relativamente primos.
El teorema del resto chino dice que dado cualquier [matemático] r [/ matemático] par sabio relativamente números primos [matemático] m_ {1}, m_ {2}, …. m_ {r} [/ math], y cualquier número [math] b_ {1}, \; b_ {2}, \; b_ {3}, .. b_ {r} [/ math], siempre podemos encontrar un número [matemática] M [/ matemática] que deja los restos [matemática] b_ {1}, \; b_ {2}, \; b_ {3}, .. b_ {r} [/ math] cuando se divide entre [math] m_ {1}, \; m_ {2}, … m_ {r} \; \; [/ math] respectivamente.
Cualquier número entero [matemáticas] M \; + \; k. m_ {1} .m_ {2} .m_ {3}…. m_ {r} [/ math] ………………… .. (i)
tiene la misma propiedad para cualquier valor entero de k.
Por lo tanto, el teorema del resto chino discute la capacidad de solución y el método para resolver un sistema dado de congruencias lineales (módulo par sabio relativamente números primos)
Es un resultado estándar en teoría de números que
Si [math] a [/ math] y [math] m [/ math] son números primos entre sí, entonces existe un número [math] a ^ {‘} [/ math] tal que [math] a. [ / math] [math] a ^ {‘} [/ math] deja el resto [math] 1 [/ math] cuando se divide entre [math] m [/ math].
es decir, [matemáticas] [/ matemáticas] [matemáticas] aa ^ {‘} \; \ equiv \; 1 \; \ mod \; m [/ matemáticas]
Tenga en cuenta que [math] a ^ {‘} [/ math] es un módulo único [math] m [/ math].
- ¿Cuáles son los requisitos previos para comprender el teorema de incompletitud de Godel?
- ¿Se puede demostrar que de la lista de números compuestos entre cualquier intervalo X ^ 2 a X + 1 ^ 2 no hay al menos un semiprime 2 * y un semiprime 3 * z?
- Dado un subconjunto de dígitos no vacío, ¿cómo puede calcular eficientemente los números cuyos cuadrados solo tienen dígitos en el subconjunto dado?
- ¿Qué es un contraejemplo de lo siguiente?
- ¿Cuál es el mejor algoritmo para dividir dos enteros?
[math] \; \; a ^ {‘} [/ math] se llama el recíproco de [math] a [/ math] módulo [math] m [/ math].
El teorema del resto chino proporciona un método para resolver el problema (i)
Es decir, la solución de las congruencias lineales simultáneas:
[matemáticas] x \; \ equiv \; b_ {j} \; \ mod \; m_ {j}, \; \; \; j = 1,2,…, \; r, \; [/ matemáticas] donde [math] m_ {j} [/ math] son pares sabios relativamente primos.
…………… .. (*)
El número
[matemáticas] M = b_ {1}. M_ {1} .M_ {1} ^ {‘} + b_ {2} .M_ {2} .M_ {2} ^ {‘} +…. + \; b_ {r}. Señor}. M_ {r} ^ {‘} [/ matemáticas] ……………………………………… .. (ii)
donde [matemáticas] M_ {j} = \ frac {m_ {1}. m_ {2} … m_ {r}} {m_ {j}}, [/ math]
para cada [matemática] j \; = \; 1, \; 2,…, \; r \; \; [/ math] y [math] M_ {j} ^ {‘} [/ math] es el recíproco de [math] M_ {j} [/ math] módulo [math] m_ {j}. [/matemáticas]
es decir, la solución del sistema (*) es
[matemáticas] x \; \ equiv \; M \; \ mod N \; [/ matemáticas]
donde [matemáticas] \; N \; = \; m_ {1}. m_ {2} … señor} \; [/matemáticas]
Cada entero
[matemáticas] \; M \; + \; k. m_ {1}. m_ {2} … m_ {r} \; [/ math] es una solución para cualquier valor entero de [math] k. [/ math]
Vamos a ilustrar esto con dos ejemplos.
Problema 1:
Encuentre la solución del sistema de congruencias:
[matemáticas] \; \; x \; \ equiv \; 2 \; \ mod \; 4 \; \ ;, [/ matemáticas]
[matemáticas] \; \; x \; \ equiv \; 3 \; \ mod \; 5 \; \ ;, [/ matemáticas]
[matemáticas] \; \; x \; \ equiv \; 1 \; \ mod \; 3 \; \; [/ matemáticas]
(es decir, encontrar todos los enteros que dejan restos [matemática] 2,3,1 [/ matemática] cuando se divide entre [matemática] 4,5, 3 \; \; [/ matemática] respectivamente)
Aplicamos el teorema del resto chino.
Aquí [matemáticas] b_ {1} = 2, \; \; b_ {2} = 3, \; \; b_ {3} = 1. [/matemáticas]
[matemáticas] m_ {1} = 4, \; \; m_ {2} = 5, \; \; m_ {3} = 3. [/ matemáticas]
De ahí obtenemos
[matemáticas] M_ {1} = 5 \ veces 3 = 15 [/ matemáticas]
[matemáticas] M_ {2} = 4 \ veces 3 = 12 [/ matemáticas]
[matemáticas] M_ {3} = 4 \ veces 5 = 20 [/ matemáticas]
Tenga en cuenta que
[matemáticas] M_ {1} = \; 15 \; \ equiv \; 3 \; \ mod 4 [/ matemáticas]
[matemáticas] M_ {2} = \; 12 \; \ equiv \; 2 \; \ mod 5 [/ matemáticas]
[matemáticas] M_ {3} = \; 20 \; \ equiv \; 2 \; \ mod 3 [/ matemáticas]
Por lo tanto
[matemáticas] M_ {1} ^ {‘} \; \ equiv \; 3 \; \ mod 4 [/ matemáticas]
[matemáticas] M_ {2} ^ {‘} \; \ equiv \; 3 \; \ mod 5 [/ matemáticas]
[matemáticas] M_ {3} ^ {‘} \; \ equiv \; 2 \; \ mod 3 [/ matemáticas]
Por lo tanto
[matemáticas] M \; = \; 2 \ times15 \ times3 + 3 \ times12 \ times3 + 1 \ times20 \ times2 \; = \; 90 \; + \; 108 \; + \; 40 \; = \; 238 [/ matemáticas] ……………………. (Iii)
Aquí [matemáticas] m_ {1}. m_ {2} .m_ {3} \; = \; 4 \ times5 \ times3 \; = \; 60 [/ math]
Por lo tanto, de (iii) obtenemos, la solución es [matemáticas] x \; \ equiv \; 58 \; \ mod 60. [/ math]
es decir, cada número entero [math] 58 \; + \; k. \; 60 [/ math] para cualquier valor entero de [math] k [/ math] da una solución.
Problema 2 :
Encuentra los enteros que dejan los restos 4, 6, 7 cuando se dividen entre 5, 9 y 11 respectivamente.
Aplicamos el teorema del resto chino para resolver este problema.
Aquí [matemáticas] b_ {1} = 4, \; \; b_ {2} = 6, \; \; b_ {3} = 7. [/matemáticas]
[matemáticas] m_ {1} = 5, \; \; m_ {2} = 9, \; \; m_ {3} = 11. [/ matemáticas]
De ahí obtenemos
[matemáticas] M_ {1} \; = \; 9 \ veces 11 \; = \; 99 [/ matemáticas]
[matemáticas] M_ {2} \; = \; 5 \ veces 11 \; = \; 55 [/ matemáticas]
[matemáticas] M_ {3} \; = \; 5 \ veces 9 = 45 [/ matemáticas]
Tenga en cuenta que
[matemáticas] M_ {1} = \; 99 \; \ equiv \; 4 \; \ mod 5 [/ matemáticas]
[matemáticas] M_ {2} = \; 55 \; \ equiv \; 1 \; \ mod 9 [/ matemáticas]
[matemáticas] M_ {3} = \; 45 \; \ equiv \; 1 \; \ mod 11 [/ matemáticas]
Por lo tanto
[matemáticas] M_ {1} ^ {‘} \; \ equiv \; 4 \; \ mod 5 [/ matemáticas]
[matemáticas] M_ {2} ^ {‘} \; \ equiv \; 1 \; \ mod 9 [/ matemáticas]
[matemáticas] M_ {3} ^ {‘} \; \ equiv \; 1 \; \ mod 11 [/ matemáticas]
Por lo tanto
[matemáticas] M \; = \; 4 \ times99 \ times4 + 6 \ times55 \ times1 + 7 \ times45 \ times1 \; = \; 1584 \; + \; 330 \; + \; 315 \; = \; 2229 [/ matemáticas] ……………………. (Iv)
Aquí [matemáticas] m_ {1}. m_ {2} .m_ {3} \; = \; 5 \ times9 \ times11 \; = \; 495 [/ math]
Por lo tanto, de (iv) obtenemos, la solución es [matemáticas] x \; \ equiv \; 249 \; \ mod 495. [/ math]
es decir, cada número entero 249 [math] \; + \; k. \; 495 [/ math] para cualquier valor entero de [math] k [/ math] da una solución.
Por lo tanto, si estamos interesados en encontrar el número entero positivo más pequeño que deje los restos 4, 6, 7 cuando se dividen entre 5, 9 y 11 respectivamente, la respuesta es 249 .
Tenga en cuenta que el primer problema también puede considerarse como el problema de encontrar el número que deja el mismo resto: 2 cuando se divide entre 4, 5 y 3. Por lo tanto, la respuesta se puede encontrar fácilmente como k. L + – 2, donde L es el mínimo común múltiplo (MCM) de 4,5 y 3, k es cualquier número entero. Pero este método especial no funcionará en el segundo problema.
El teorema del resto chino tiene aplicaciones interesantes en varios campos.