CONGRUENCIAS: inverso modular y cómo resolver ax ≡ b, 4 ejercicios | Mat. Discreta y Lógica 48

Práctica 20: cuatro ejercicios de examen de aritmética modular. La receta: reduce primero y opera después; a tiene inverso módulo n si y solo si mcd(a, n) = 1, y sale con Euclides extendido; en una congruencia nunca se divide, se multiplica por el inverso. Uno: operar reduciendo. Hoy es martes; dentro de 1000 días será lunes, porque 1000 = 7·142 + 6. El resto de 123·456 entre 9 sin multiplicar: 123 ≡ 6 y 456 ≡ 15 ≡ 6 por la suma de cifras (10 ≡ 1 mód 9), así que 6·6 = 36 ≡ 0 (y en efecto 123·456 = 56088, cuyas cifras suman 27). Y 2026 = 7·289 + 3, resto 3. Dos: el inverso de 11 módulo 26, la clave de un cifrado afín. Euclides: 26 = 11·2 + 4, 11 = 4·2 + 3, 4 = 3·1 + 1; subiendo, 1 = 3·26 − 7·11, así que 11⁻¹ ≡ −7 ≡ 19 (11·19 = 209 = 8·26 + 1). El 13 no tiene inverso: mcd(13, 26) = 13. Tres: 11x ≡ 5 (mód 26). No se divide entre 11: se multiplica por 19 y x ≡ 95 ≡ 17 (11·17 = 187 = 7·26 + 5). Cuatro: cuando el mcd no es 1. ax ≡ b (mód n) tiene solución si y solo si d = mcd(a, n) divide a b, y entonces hay exactamente d soluciones módulo n. 6x ≡ 4 (mód 10): d = 2 divide a 4, se divide todo entre 2, 3x ≡ 2 (mód 5), x ≡ 4 (mód 5), es decir x ≡ 4 o x ≡ 9 (mód 10). 6x ≡ 3 (mód 10) no tiene solución: 6x es siempre par y 10k + 3 es impar. Es el nivel 48 de la lista «Matemática Discreta y Lógica», pensada para primero de los grados en Inteligencia Artificial, Ciencia de Datos e Ingeniería Informática. Anterior, Nivel 47 (congruencias y aritmética modular):    • CONGRUENCIAS Y ARITMÉTICA MODULAR: por qué...   Siguiente, teoría (el pequeño teorema de Fermat):    • PEQUEÑO TEOREMA DE FERMAT: el resto de 2¹⁰...   Capítulos: 0:00 ¿Qué día será dentro de 1000 días? 0:24 La receta de la aritmética modular 0:56 Ejercicio 1: operar reduciendo 2:16 Ejercicio 2: el inverso de 11 módulo 26 3:42 Ejercicio 3: 11x ≡ 5 (mód 26) 4:41 Ejercicio 4: cuando el mcd no es 1 6:11 La receta para el examen Gradiente: el grado en Inteligencia Artificial, paso a paso. Teoría muy visual y ejercicios resueltos.