3.
Sistemas algebraicos
3.2 La aritmética de residuos en las computadoras
3.2.1 Aritmética de residuos
Aritmética modular
• Sean 𝑎, 𝑏, 𝑐, 𝑑, 𝑚 enteros para 𝑚 > 1. Si 𝑎 ≡ 𝑐 𝑚𝑜𝑑 𝑚 y 𝑏 ≡ 𝑑 𝑚𝑜𝑑 𝑚
• 𝑎 + 𝑏 ≡ (𝑐 + 𝑑) 𝑚𝑜𝑑 𝑚
• 𝑎 − 𝑏 ≡ (𝑐 − 𝑑) 𝑚𝑜𝑑 𝑚
• 𝑎𝑏 ≡ (𝑐𝑑) 𝑚𝑜𝑑 𝑚
• 𝑎𝑛 ≡ 𝑐 𝑛 𝑚𝑜𝑑 𝑚 , 𝑛 ∈ ℤ
Aritmética modular
• Sean 𝑎, 𝑏, 𝑚 enteros para 𝑚 > 1
• Si 𝑎𝑏 ≡ [ 𝑎 𝑚𝑜𝑑 𝑚 𝑏 𝑚𝑜𝑑 𝑚 ](𝑚𝑜𝑑 𝑚)
• Igualmente 𝑎𝑏 𝑚𝑜𝑑 𝑚 = [ 𝑎 𝑚𝑜𝑑 𝑚 𝑏 𝑚𝑜𝑑 𝑚 ](𝑚𝑜𝑑 𝑚)
• 𝑎𝑛 ≡ 𝑎 𝑚𝑜𝑑 𝑚 𝑛 𝑚𝑜𝑑 𝑚 ; 𝑛 ∈ ℤ+
Ecuación de congruencia lineal
• 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚)
• Suponga que 𝑎 y 𝑚 son coprimos. Entonces 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) tiene solución
única
• Si 𝑠 es la única solución de 𝑎𝑥 ≡ 1(𝑚𝑜𝑑𝑚), entonces la solución única es
𝑥 = 𝑏𝑠
Ejemplo
• 3𝑥 ≡ 5(𝑚𝑜𝑑8)
Ejemplo
• 3𝑥 ≡ 5(𝑚𝑜𝑑8)
• Se prueban con los enteros 0,1, … , 7
• 𝑥 = 7 y es la única solución dado que 3 y 8 son coprimos
Ejemplo
• 33𝑥 ≡ 38(𝑚𝑜𝑑280)
Ejemplo
• 33𝑥 ≡ 38(𝑚𝑜𝑑280)
• Aplicar algoritmo de Euclides a 33𝑥 ≡ 1(𝑚𝑜𝑑280)
• Se encuentra 𝑠 = 17
• 𝑠𝑏 = 17 ∗ 38 = 646
• Se obtiene el residuo x = 86 al dividir 646 entre 280
• La solución general es x = 86 + 280𝑘, 𝑘 ∈ ℤ o equivalente 𝑥 ≡ 86(𝑚𝑜𝑑280)
Teorema
• Sea la ecuación 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) y 𝑑 = 𝑚𝑐𝑑(𝑎, 𝑚)
i. Suponga que 𝑑 no divide a 𝑏, entonces 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) no tiene solución
ii. Suponga que 𝑑 divide a 𝑏, entonces entonces 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) tiene 𝑑 soluciones,
todas congruentes módulo 𝑀 con la solución única de
𝑎 𝑏 𝑚
𝐴𝑥 ≡ 𝐵 𝑚𝑜𝑑𝑀 , 𝐴 = 𝐵 = 𝑀 =
𝑑 𝑑 𝑑
Ejercicios
• Resuelva las congruencias
• 4𝑥 ≡ 9 𝑚𝑜𝑑14
• 8𝑥 ≡ 12(𝑚𝑜𝑑28)
Teorema chino del residuo
• Considere el sistema de ecuaciones de congruencia lineal
𝑥 ≡ 𝑟1 𝑚𝑜𝑑𝑚1 , 𝑥 ≡ 𝑟2 𝑚𝑜𝑑𝑚2 , … , 𝑥 ≡ 𝑟𝑘 𝑚𝑜𝑑𝑚𝑘
• Donde 𝑚𝑘 son coprimos por pares. El sistema tiene una solución única
módulo 𝑀 = 𝑚1 𝑚2 … 𝑚𝑘
Teorema chino del residuo
𝑀 𝑀 𝑀
𝑀1 = , 𝑀2 = , … , 𝑀𝑘 =
𝑚1 𝑚2 𝑚𝑘
• Cada par 𝑀𝑖 𝑦 𝑚𝑖 son coprimos. Sean 𝑠1 , 𝑠2, … , 𝑠𝑘 las soluciones de las
ecuaciones de congruencia
𝑀1 𝑥 ≡ 1 𝑚𝑜𝑑𝑚1 , 𝑀2 𝑥 ≡ 1 𝑚𝑜𝑑𝑚2 , … , 𝑀𝑘 𝑥 ≡ 1 𝑚𝑜𝑑𝑚𝑘
Teorema chino del residuo
• La siguiente es una solución del sistema
𝑥0 = 𝑀1 𝑠1 𝑟1 + 𝑀2 𝑠2 𝑟2 + ⋯ + 𝑀𝑘 𝑠𝑘 𝑟𝑘
• Se divide entre 𝑀 y el residuo es la solución del sistema
Acertijo chino
• ¿Hay algún entero positivo 𝑥 tal que cuando 𝑥 se divide entre 3 se obtiene
un resido igual a 2, cuando 𝑥 se divide entre 5 se obtiene un resido igual a 4
y cuando 𝑥 se divide entre 7 se obtiene un resido igual a 6
Ejemplo
𝑥 ≡ 2 𝑚𝑜𝑑3 , 𝑥 ≡ 4 𝑚𝑜𝑑5 , 𝑥 ≡ 6(𝑚𝑜𝑑7)
• 𝑀 = 3 ∙ 5 ∙ 7 = 105, 𝑀1 = 105
3
= 35, 𝑀2 =
105
5
= 21, 𝑀𝑘 =
105
7
= 15
• 35𝑥 ≡ 1 𝑚𝑜𝑑3 , 21𝑥 ≡ 1 𝑚𝑜𝑑5 , 15𝑥 ≡ 1 𝑚𝑜𝑑7
• Resolviendo
• 𝑠1 = 2, 𝑠2 = 1, 𝑠3 = 1
Ejemplo
• 𝑥0 = 35 ∙ 2 ∙ 2 + 21 ∙ 1 ∙ 4 + 15 ∙ 1 ∙ 6 = 314
• Se divide entre el 𝑀 = 105 y se obtiene el residuo 𝑥 = 104
• Forma general 𝑥 = 104 + 105𝑘
• Equivalente 𝑥 ≡ 104𝑚𝑜𝑑105
Ejercicio
• Un proveedor de PC’s efectuó un pedido de entre 1000 y 1500 equipos a un
fabricante que se los envió en contenedores de capacidad para 68 PC’s. El
proveedor los repartió en las diferentes tiendas usando vehículos con
capacidad para 20 PC’s, dejando 32 equipos sin repartir en su bodega.
¿Cuántas PC’s pidió el proveedor al fabricante?
Solución
• 1292 PC’s
Ejercici0
• Se dispone de una cantidad par de monedas menor que 600. Se quieren
acomodar en filas. Si ordenan en filas de 17 monedas, sobran 8. Si se
consideran la mita de las modenas iniciales y se ordenan en filas de 7
monedas, sobran 3. ¿Cuántas monedas hay? ¿Es la solución única?
Solución
• 76, 314 o 552 monedas
Ejercicio
• Se reparten 4 cajetillas de cigarros entre tres grupos de estudiantes. En el
primer grupo de cinco estudiantes, se reparten dos cajetillas y sobra un
cigarro. En el segundo grupo de seis estudiantes, se reparte una cajetilla y
sobran dos cigarros. En el tercer grupo de siete estudiantes, se reparte una
cajetilla y sobran 3 cigarros. El número de cigarros es menor a 500, ¿Cuántos
cigarros tiene cada cajetilla?
Solución
• 38 cigarros
3.2.2 Aplicaciones en las computadoras
Criptografía
• Simétrica
• Asimétrica
Simétrica
Asimétrica
Referencias
• LIPSCHUTZ, Seymour. LIPSON, Marc Lars
Matemáticas discretas
3a. Edición. Mc Graw Hill, 2009
• VEERARAJAN, T.
Matemáticas discretas con teoría de gráficas y combinatoria
México McGraw-Hill Interamericana, 2008
