GMAT QUANT y la aritmética modular ¿qué significa y ≡ z mod w?

By Claudio Hurtado clases, cursos y tutorías GMAT QUANT +56937780070

«y ≡ z mod w»: Esto quiere decir que cuando divides y entre w, el residuo es z.

Así: x ≡ 2 mod 5:

Esto quiere decir que cuando divides x entre 5, el residuo es 2.
Por ejemplo, números como 2, 7, 12, 17, etc., cumplen esto
porque 7 dividido entre 5 es 1 con residuo 2,
12 dividido entre 5 es 2 con residuo 2, y así sucesivamente.

¿qué significa x ≡ 2 mod 5, x ≡ 3 mod 7, x ≡ 1 mod 4?

Esta situación se llama sistema de congruencias.

Debemos saber encontrar un número x que satisfaga las tres condiciones simultáneamente. Esto se conoce como un sistema de congruencias, y para resolverlo, se puede utilizar el Teorema Chino del Resto, que es un método para encontrar soluciones a sistemas de congruencias con módulos coprimos.

Primero, necesito verificar si los módulos (5, 7, 4) son coprimos entre sí. En este caso, 5 y 7 son primos, pero 4 y 5 comparten un divisor común (1), y 4 y 7 también son coprimos. Sin embargo, 4 y 5 son coprimos (mcd=1), 5 y 7 son coprimos, y 4 y 7 son coprimos. Por lo tanto, los módulos son coprimos dos a dos, lo que significa que el Teorema Chino del Resto garantiza una solución única módulo el producto de los módulos, que es 5*7*4 = 140. Esto significa que habrá una solución única cada 140 números.

Resolviendo el sistema de congruencia paso a paso:

Paso 1. **Resolver las dos primeras congruencias**:

– Encontrar x tal que x ≡ 2 mod 5 y x ≡ 3 mod 7.

– Expresar x como x = 5k + 2.

– Sustituir en la segunda congruencia: 5k + 2 ≡ 3 mod 7 ⇒ 5k ≡ 1 mod 7.

– Encontrar el inverso multiplicativo de 5 módulo 7. El inverso de 5 mod 7 es 3 porque 5*3 = 15 ≡ 1 mod 7.

– Entonces, k ≡ 3*1 ≡ 3 mod 7 ⇒ k = 7m + 3.

– Sustituir de nuevo en x: x = 5*(7m + 3) + 2 = 35m + 17.

– Ahora, x ≡ 17 mod 35.

Paso 2. **Incorporar la tercera congruencia**:

– Ahora tenemos x ≡ 17 mod 35 y x ≡ 1 mod 4.

– Expresar x como x = 35n + 17.

– Sustituir en la tercera congruencia: 35n + 17 ≡ 1 mod 4.

– Simplificar 35 mod 4: 35 ≡ 3 mod 4, y 17 ≡ 1 mod 4.

– Entonces, 3n + 1 ≡ 1 mod 4 ⇒ 3n ≡ 0 mod 4 ⇒ n ≡ 0 mod 4.

– Por lo tanto, n = 4p.

– Sustituir de nuevo en x: x = 35*(4p) + 17 = 140p + 17.

– La solución general es x ≡ 17 mod 140.

Finalmente, la solución más pequeña positiva es x = 17, y las soluciones subsiguientes se obtienen sumando 140 cada vez (17, 157, 297, …).

Resolvamos nuevamente: Si x ≡ 2 mod 5, x ≡ 3 mod 7, x ≡ 1 mod 4, entonces x = ?

1. x ≡ 2 mod 5

• Interpretación: Al dividir x entre 5, el residuo es 2.
• Ejemplos de números que cumplen:
  • 2, 7, 12, 17, 22, 27, …
  • Por ejemplo:
    • 7 ÷ 5 = 1 con residuo 2 → 7 ≡ 2 mod 5.
    • 12 ÷ 5 = 2 con residuo 2 → 12 ≡ 2 mod 5.

---

2. x ≡ 3 mod 7

• Interpretación: Al dividir x entre 7, el residuo es 3.
• Ejemplos de números que cumplen:
  • 3, 10, 17, 24, 31, 38, …
  • Por ejemplo:
    • 10 ÷ 7 = 1 con residuo 3 → 10 ≡ 3 mod 7.
    • 17 ÷ 7 = 2 con residuo 3 → 17 ≡ 3 mod 7.

---

3. x ≡ 1 mod 4

• Interpretación: Al dividir x entre 4, el residuo es 1.
• Ejemplos de números que cumplen:
  • 1, 5, 9, 13, 17, 21, …
  • Por ejemplo:
    • 5 ÷ 4 = 1 con residuo 1 → 5 ≡ 1 mod 4.
    • 17 ÷ 4 = 4 con residuo 1 → 17 ≡ 1 mod 4.

---

¿Qué significa resolver todas juntas?

Buscamos un número x que cumpla las tres condiciones al mismo tiempo.
Por ejemplo, 17 cumple:

• 17 ≡ 2 mod 5 (porque 17 ÷ 5 = 3 con residuo 2).
• 17 ≡ 3 mod 7 (porque 17 ÷ 7 = 2 con residuo 3).
• 17 ≡ 1 mod 4 (porque 17 ÷ 4 = 4 con residuo 1).

---

¿Cómo encontrar todas las soluciones?

Usamos el Teorema Chino del Resto, que garantiza una solución única módulo 5×7×4=140, ya que los módulos son coprimos dos a dos.

Paso a Paso:

1. Resuelve las dos primeras congruencias:
   • Queremos x ≡ 2 mod 5 y x ≡ 3 mod 7.
   • Expresamos x como x = 5k + 2.
   • Sustituimos en la segunda congruencia:

     5k+2 ≡ 3 mod 7   ⟹   5k ≡ 1 mod 7

   • Encontramos el inverso de 5 mod 7 (es 3, porque 5×3=15 ≡1 mod 7).
   • Multiplicamos ambos lados:

     k ≡ 3×1 ≡ 3 mod 7 ⟹ k=7m+3

   • Sustituimos en x:

     x=5(7m+3) + 2 = 35m + 17

   • Solución parcial: x ≡ 17 mod 35.
2. Incorpora la tercera congruencia (x ≡1 mod 4):
   • Expresamos x como x = 35n + 17.
   • Sustituimos en x ≡1 mod 4:

     35n+17 ≡ 1 mod 4 ⟹ 35n ≡ −16 mod 4 ⟹ 35n ≡ 0 mod 4

   • Simplificamos 35 mod 4 = 3:

     3n ≡ 0 mod 4 ⟹ n ≡ 0 mod 4 ⟹ n=4p

   • Sustituimos en x:

     x=35(4p) + 17 = 140p +17

   • Solución final: x ≡17 mod140.

---

Conclusión

• La solución más pequeña: x = 17.
• Todas las soluciones: 17, 157, 297, 437, … (sumando 140 cada vez).

Verificación:

• 17 ÷ 5 = 3 residuo 2 ✅
• 17 ÷ 7 = 2 residuo 3 ✅
• 17 ÷ 4 = 4 residuo 1 ✅

---

¿Para qué sirve esto?

• En matemáticas y criptografía, resolver sistemas como este es clave para algoritmos como RSA.
• En programación, se usa para optimizar cálculos con restricciones modulares.

 

Clases GMAT QUANT

Nuestras clases y cursos

Nuestras clases y cursos preparación GMAT QUANT, están orientadas a profesionales que requieran nivelar sus competencias en matemáticas, desde lo conceptual, para luego aplicar técnicas y tips para enfrentar con ventaja las preguntas de alta puntuación del GMAT QUANT. +56937780070