¿Cuál es el número mínimo que dividido por 4, por 7 y por 11 deja los restos 1, 2 y 3, respectivamente?
Usaremos el Teorema del resto chino para responder esta pregunta. [1]
Dados enteros coprimos positivos por pares [matemática] n_1, n_2,…, n_k [/ matemática] y enteros arbitrarios [matemática] a_1, a_2,…, a_k, [/ matemática] el sistema de congruencias simultáneas
[matemáticas] \ qquad \ left \ {\ begin {align} x & \ equiv a_1 \ quad (\ text {mod} n_1) \\ x & \ equiv a_2 \ quad (\ text {mod} n_2) \\ & ~~ \ vdots \\ x & \ equiv a_k \ quad (\ text {mod} n_k) \ end {align} \ right. [/ math]
tiene una solución, y la solución es un módulo único [matemáticas] N = n_1 n_2 … n_k. [/ matemáticas]
La siguiente es una construcción general para encontrar una solución a un sistema de congruencias utilizando el teorema del resto chino:
1. Calcular [matemáticas] N = n_1 \ veces n_2 \ veces \ cdots \ veces n_k [/ matemáticas]
2. Para cada [matemática] i = 1, 2,…, k, [/ matemática] calcule [matemática] y_i = \ dfrac {N} {n_i} [/ matemática]
3. Para cada [matemática] i = 1,2,…, k, [/ matemática] calcule [matemática] z_i \ equiv y_i ^ {- 1} \ text {mod} n_i, [/ matemática] es decir [matemática] z_i y_i \ equiv 1 \ text {mod} n_i, [/ math] usando el algoritmo extendido de Euclides ([math] z_i [/ math] existe ya que [math] n_1, n_2, …, n_k [/ math] son pares por pares)
4. El número entero [math] x = \ displaystyle \ sum_ {i = 1} ^ k a_i y_i z_i [/ math] es una solución para el sistema de congruencias, y [math] x \ text {mod} N [/ math ] es la solución única módulo [matemática] N [/ matemática].
[matemáticas] ~ [/ matemáticas]
Aquí vamos…
Paso 0: recuerda que los residuos, las a, son 1, 2 y 3, respectivamente.
Paso 1: el producto de las n: [matemáticas] N = 4 \ veces 7 \ veces 11 = 308 [/ matemáticas]
Paso 2: Las y son 77, 44 y 28, respectivamente.
Paso 3: Las z son 1, -3 y 2, respectivamente, porque
[math] \ qquad 1 \ times 77 \ equiv 1 \ text {(mod} 4), [/ math]
[math] \ qquad -3 \ times 44 \ equiv 1 \ text {(mod} 7), [/ math] y
[math] \ qquad 2 \ times 28 \ equiv 1 \ text {(mod} 11). [/ math]
Paso 4: [math] x [/ math] es la suma de los productos respectivos de [math] a’s \ times y’s \ times z’s. [/ Math] En otras palabras,
[matemáticas] \ qquad \ begin {align} x = & (1 \ times 77 \ times 1) \\ + & (2 \ times 44 \ times -3) \\ + & (3 \ times 28 \ times 2) \ end {align} [/ math]
[matemáticas] \ qquad x = -19 \ equiv 289 \ text {(mod} 308) [/ matemáticas]
Verificándolo, de hecho, las congruencias son correctas:
[matemáticas] \ qquad 289 \ equiv 1 \ text {(mod} 4) [/ matemáticas]
[matemáticas] \ qquad 289 \ equiv 2 \ text {(mod} 7) [/ matemáticas]
[matemáticas] \ qquad 289 \ equiv 3 \ text {(mod} 11) [/ matemáticas]
Notas al pie
[1] Teorema chino del resto | Wiki Brillante de Matemáticas y Ciencias